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

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

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

Как элементы массива хранятся в памяти?

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

Что такое лист дерева?

1. AУзел с наибольшим значением
2. BУзел без потомков
3. CУзел ровно с одним потомком
4. DУзел без родителя

Какой метод разрешения коллизий хранит конфликтующие ключи в списке в той же корзине?

1. AМетод цепочек (separate chaining)
2. BДвойное хеширование
3. CЛинейное пробирование
4. DКвадратичное пробирование

Какое условие балансировки поддерживает АВЛ-дерево в каждом узле?

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

В двоичной min-куче, хранящейся в массиве (индексация с 0), потомки узла с индексом i находятся на позициях:

1. A2i и 2i + 1
2. Bi + 1 и i + 2
3. Ci/2 и i/2 + 1
4. D2i + 1 и 2i + 2

Какому свойству должно удовлетворять красно-чёрное дерево?

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

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

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