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

Что такое взвешенный граф?

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

В двоичном дереве поиска значения в левом поддереве узла:

1. AБольше значения узла
2. BМеньше значения узла
3. CРавны значению узла
4. DРасположены в случайном порядке

Что делает хеш-функция в хеш-таблице?

1. AСортирует ключи в таблице
2. BШифрует значения в таблице
3. CОтображает ключ в индекс таблицы
4. DПодсчитывает, сколько ключей хранится

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

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

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

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

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

1. A5 4 3 2 1
2. B4 5 2 3 1
3. C4 2 5 1 3
4. D1 2 4 5 3

Какие операции поддерживает за O(log n) дерево Фенвика (binary indexed tree) над массивом из n чисел?

1. AПоиск медианы за O(1)
2. BЗапросы префиксных сумм и обновления отдельного элемента
3. CСортировку массива и двоичный поиск
4. DВставку элементов в любую позицию

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

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