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

Что делает хеш-функция в хеш-таблице?

1. AШифрует значения в таблице
2. BОтображает ключ в индекс таблицы
3. CСортирует ключи в таблице
4. DПодсчитывает, сколько ключей хранится

Что такое свойство max-кучи?

1. AКлючи отсортированы слева направо
2. BКлюч каждого родителя больше или равен ключам его потомков
3. CКлюч каждого левого потомка больше или равен ключу его правого соседа
4. DВсе листья содержат максимальный ключ

Что такое цикл в графе?

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

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

1. AВ динамическом массиве
2. BВ односвязном списке
3. CВ отсортированном массиве
4. DВ двусвязном списке

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков прямой обход (preorder)?

1. A1 2 4 5 3
2. B1 2 3 4 5
3. C4 5 2 3 1
4. D4 2 5 1 3

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

1. AСтек
2. BХеш-таблица
3. CСбалансированное двоичное дерево поиска
4. DНеотсортированный связный список

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

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

Какая структура данных обеспечивает кэш LRU (least recently used) с операциями get и put за O(1)?

1. AХеш-таблица в сочетании с двусвязным списком
2. BОдин отсортированный массив
3. CТолько двоичное дерево поиска
4. DТолько стек