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

Что такое дек (deque, двусторонняя очередь)?

1. AОчередь, отсортированная по приоритету
2. BОчередь, допускающая удаление только с конца
3. CДве отдельные очереди в одном массиве
4. DСтруктура, допускающая вставку и удаление с обоих концов

Что такое коллизия в хеш-таблице?

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

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

1. APush
2. BEnqueue
3. CPeek
4. DPop

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

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

Какой абстрактный тип данных использует алгоритм Дейкстры для выбора следующей обрабатываемой вершины?

1. AСтек
2. BОчередь с приоритетом по минимуму
3. CМножество без упорядочения
4. DОчередь FIFO

Зачем нужен сторожевой (фиктивный, sentinel) узел в связном списке?

1. AЧтобы хранить число элементов
2. BЧтобы список был отсортирован
3. CЧтобы упростить код, убрав особые случаи в голове или хвосте
4. DЧтобы список не мог вырасти сверх фиксированного максимального числа узлов

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

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

Зачем серверу выбирать хеш-функцию случайно из универсального семейства?

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