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

Где находится наименьший элемент двоичной min-кучи?

1. AВ самом левом листе
2. BВ корне
3. CВ каком-то листе, который придётся искать
4. DВ последней позиции массива

Хеш-таблица (hash table) хранит данные в виде:

1. AДерева с упорядоченными ключами
2. BПар ключ–значение, расположение которых определяет хеш-функция
3. CСтроки фиксированной длины
4. DТолько отсортированного списка

Что хранит отображение (map, словарь)?

1. AТолько значения в порядке вставки
2. BПары одинаковых ключей
3. CЗначения, отсортированные по размеру
4. DПары ключ–значение с уникальными ключами

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

1. A4 2 5 1 3
2. B1 2 4 5 3
3. C1 2 3 4 5
4. D4 5 2 3 1

АВЛ-деревья (AVL) и красно-чёрные деревья гарантируют:

1. AХранение ключей в порядке вставки
2. BВысоту O(log n) благодаря перебалансировке
3. CПоиск за константное время в любом случае
4. DЧто ни у одного узла нет двух потомков

Сколько памяти занимают списки смежности для графа с V вершинами и E рёбрами?

1. AO(V²)
2. BO(V + E)
3. CO(V × E)
4. DO(E²)

Удаление узла с двумя потомками из двоичного дерева поиска обычно выполняют так:

1. AМеняют его местами с корнем
2. BПерестраивают поддерево под ним с нуля и заново вставляют каждый содержавшийся в нём ключ
3. CУдаляют всё поддерево
4. DЗаменяют его in-order преемником (или предшественником) и удаляют тот узел

Почему в хеш-таблице с открытой адресацией удаление часто выполняют с помощью метки «надгробие» (tombstone)?

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