Структуры данных: лист заданий с ответами

Глубина узла в дереве — это:

1. AЧисло рёбер от корня до этого узла
2. BЧисло потомков этого узла
3. CЧисло рёбер от этого узла до самого глубокого листа
4. DЧисло узлов в его поддереве

Как называется операция стека, добавляющая элемент на вершину?

1. APop
2. BPeek
3. CPush
4. DEnqueue

Какая структура данных работает по принципу «первым пришёл — первым ушёл» (FIFO)?

1. AОчередь
2. BБинарное дерево
3. CСтек
4. DКуча

Какая структура данных используется, чтобы проверить, сбалансированы ли скобки в «{[()]}»?

1. AДвоичное дерево поиска
2. BСтек
3. CХеш-таблица
4. DОчередь

Кольцевой буфер (ring buffer) обычно используют для реализации:

1. AХеш-функции
2. BОчереди фиксированного размера
3. CОбхода графа
4. DДвоичного дерева поиска

Почему обход массива на практике часто гораздо быстрее обхода связного списка той же длины?

1. AЭлементы массива расположены непрерывно, поэтому хорошо используют кэш процессора
2. BСвязные списки всегда хранят элементы на диске
3. CОбход массива занимает в сумме O(1), а связного списка — O(n)
4. DМассивы требуют меньше инструкций для сравнения значений

Какое утверждение о пирамидальной сортировке (heapsort) верно?

1. AОна устойчива и требует O(n) дополнительной памяти
2. BОна работает за O(n) на любых входных данных
3. CОна сортирует на месте за O(n log n) в худшем случае, но не является устойчивой
4. DЕй нужно двоичное дерево поиска как дополнительное хранилище, поэтому она использует O(n) дополнительной памяти

Объект хранится как ключ в хеш-отображении, а затем меняется поле, используемое его хеш-функцией. Каков вероятный результат?

1. AОтображение выбрасывает ошибку в момент изменения поля
2. BПоиск объекта может не удаться, потому что он лежит в корзине своего старого хеша
3. CНичего не меняется, потому что хеш ключа вычисляется только один раз при запуске программы
4. DОтображение автоматически переносит ключ в новую корзину