2001-gre-vs-practice.pdf/Q09 — различия между версиями
Материал из DISCOPAL
(→Вопрос: Q09-e5724f) |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q09-e5724f == | == Вопрос: Q09-e5724f == | ||
Рассмотрим односвязный список, где F это указатель на начало списка, а L на конец. Время выполнения каких операций из предложенных зависит от длины списка? | Рассмотрим односвязный список, где F это указатель на начало списка, а L на конец. Время выполнения каких операций из предложенных зависит от длины списка? | ||
| − | [[Файл:List single.png]] | + | |
| + | [[Файл:List single.png|480px|center]] | ||
=== Ответы === | === Ответы === | ||
| Строка 16: | Строка 16: | ||
{{cstest-source|2001-gre-vs-practice.pdf|16|9}} | {{cstest-source|2001-gre-vs-practice.pdf|16|9}} | ||
| − | Чтобы удалить последний элемент списка, нам нужно обновить указатель L на предпоследний элемент, но | + | Чтобы удалить последний элемент списка, нам нужно обновить указатель L на предпоследний элемент, но так как список односвязный, то чтобы узнать адрес предпоследнего элемента, придется идти от начала до конца списка. |
| − | + | ||
| − | + | Остальные операции можно выполнить за O(1), зная F и L. | |
| − | {{ | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 16:24, 12 января 2025 (UTC)}} |
| − | + | ||
| − | [[Категория: | + | [[Категория:Структуры данных]] |
Версия 16:24, 12 января 2025
Вопрос: Q09-e5724f
Рассмотрим односвязный список, где F это указатель на начало списка, а L на конец. Время выполнения каких операций из предложенных зависит от длины списка?
Ответы
- Правильный ответ: Удаление последнего элемента списка
- Удаление первого элемента списка
- Добавление элемента в конец
- Добавление элемента в начало
- Поменять местами первые 2 элемента списка
Объяснение
Исходники — вопрос 9 на 16 странице книги «2001-gre-vs-practice.pdf»
Чтобы удалить последний элемент списка, нам нужно обновить указатель L на предпоследний элемент, но так как список односвязный, то чтобы узнать адрес предпоследнего элемента, придется идти от начала до конца списка.
Остальные операции можно выполнить за O(1), зная F и L.