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

Какая структура данных лучше всего подходит для функции «отменить» (undo) в текстовом редакторе?

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Граф, хранящийся на диске

Симметричный обход (in-order) двоичного дерева поиска посещает ключи:

1. AПо уровням
2. BВ порядке возрастания (отсортированно)
3. CВсегда в порядке убывания
4. DВ порядке вставки

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков прямой обход (preorder)?

1. A4 2 5 1 3
2. B1 2 3 4 5
3. C4 5 2 3 1
4. D1 2 4 5 3

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

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

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

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

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

1. A40
2. B60
3. C70
4. D80