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

Какая структура данных используется для обхода дерева по уровням (level-order)?

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

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

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

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

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

Сколько времени занимает проверка существования ребра (u, v) с помощью матрицы смежности?

1. AO(V)
2. BO(1)
3. CO(E)
4. DO(log V)

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

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

Сколько времени занимает поиск слова длины L в префиксном дереве (trie) с фиксированным алфавитом?

1. AO(L), независимо от числа хранимых слов
2. BO(n), где n — число слов
3. CO(L × n)
4. DO(log n), где n — число слов

Какая пара обходов всегда однозначно определяет двоичное дерево с различными ключами?

1. AОдин только прямой
2. BОдин только обход по уровням
3. CПрямой и симметричный (preorder и inorder)
4. DПрямой и обратный (preorder и postorder)

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

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