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

Где находится наименьший элемент двоичной 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Его помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
2. BВсю кучу перестраивают с нуля
3. CЕго вставляют в отсортированную позицию, сдвигая все бо́льшие элементы на одно место вправо
4. DЕго помещают в корень и опускают вниз

Кольцевой буфер (ring buffer) обычно используют для реализации:

1. AОбхода графа
2. BОчереди фиксированного размера
3. CДвоичного дерева поиска
4. DХеш-функции

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

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

В BST с корнем 50, левым поддеревом 30 (потомки 20, 40) и правым поддеревом 70 (потомки 60, 80) корень удаляют с помощью in-order преемника. Какой ключ станет новым корнем?

1. A60
2. B70
3. C40
4. D80

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

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