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

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

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

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

1. APush
2. BPop
3. CEnqueue
4. DPeek

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

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

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

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

Симметричный обход (in-order) двоичного дерева поиска посещает ключи:

1. AПо уровням
2. BВ порядке возрастания (отсортированно)
3. CВ порядке вставки
4. DВсегда в порядке убывания

У узла двоичного дерева поиска есть правое поддерево. Где находится его in-order преемник?

1. AСамый правый узел его левого поддерева
2. BВсегда его правый потомок
3. CВсегда его родитель
4. DСамый левый узел его правого поддерева

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

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

Для каждого элемента массива нужно найти следующий больший элемент справа за общее время O(n). Какая структура поможет?

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