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

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

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

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

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

В каком порядке прямой обход (preorder) двоичного дерева посещает узлы?

1. AЛевое поддерево, затем правое поддерево, затем узел
2. BУзел, затем левое поддерево, затем правое поддерево
3. CЛевое поддерево, затем узел, затем правое поддерево
4. DПо уровням сверху вниз

Чему равно значение постфиксного выражения 3 4 + 2 * ?

1. A10
2. B14
3. C24
4. D11

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

1. A2i и 2i + 1
2. B2i + 1 и 2i + 2
3. Ci + 1 и i + 2
4. Di/2 и i/2 + 1

Как в кольцевой очереди, хранящейся в массиве ёмкостью n, вычисляется следующая позиция после индекса i?

1. A(i − 1) mod n
2. Bi + 1
3. C(i + 1) mod n
4. D2i + 1

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

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

Какое утверждение о пирамидальной сортировке (heapsort) верно?

1. AОна устойчива и требует O(n) дополнительной памяти
2. BОна работает за O(n) на любых входных данных
3. CЕй нужно двоичное дерево поиска как дополнительное хранилище, поэтому она использует O(n) дополнительной памяти
4. DОна сортирует на месте за O(n log n) в худшем случае, но не является устойчивой