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

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

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

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

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

Что такое цикл в графе?

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

Префиксное дерево (trie) особенно эффективно для:

1. AПоиска кратчайших путей
2. BХранения матриц
3. CПоиска по префиксу, например автодополнения
4. DСортировки чисел

Сколько узлов в идеальном (perfect) двоичном дереве высоты h, если высота считается в рёбрах?

1. A2h + 1
2. Bh²
3. C2^h+1 − 1
4. D2^h

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

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

Алгоритм Кана для топологической сортировки многократно удаляет вершины с полустепенью захода 0. Какая структура хранит эти вершины?

1. AМатрица смежности, фиксирующая, какие вершины уже удалены
2. BОчередь (или любая коллекция) вершин с полустепенью захода 0
3. CСтек всех посещённых рёбер
4. DMax-куча, упорядоченная по полустепени исхода

Нужно хранить k наименьших значений из потока n чисел, используя O(k) памяти. Какой подход работает за время O(n log k)?

1. AОтсортированный массив всех n значений
2. BMax-куча размера k, корень которой заменяется, когда приходит меньшее значение
3. CMin-куча, хранящая все n значений, из которой в конце извлекаются k наименьших
4. DОчередь FIFO последних k значений