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