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

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

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

Какова определяющая особенность множества как абстрактного типа данных?

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

Какая структура данных используется для обхода дерева по уровням (level-order)?

1. AХеш-таблица
2. BОчередь
3. CСтек
4. DОчередь с приоритетом

Приложению нужен быстрый поиск, а также вывод ключей в отсортированном порядке и запросы по диапазону. Какая структура подходит лучше всего?

1. AНеотсортированный связный список
2. BХеш-таблица
3. CСтек
4. DСбалансированное двоичное дерево поиска

Ключи 50, 30, 70, 20, 40 вставляются в таком порядке в пустое двоичное дерево поиска. Кто левый потомок 30?

1. A50
2. B20
3. C40
4. D70

Как работает extract-min в двоичной min-куче?

1. AУдаляют последний элемент массива
2. BПоследний элемент перемещают в корень и опускают вниз (sift down)
3. CУдаляют корень и сдвигают все элементы на одну позицию влево
4. DИщут новый минимум среди всех листьев

Какая структура позволяет вычислить максимум каждого окна размера k в массиве за общее время O(n)?

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

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

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