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

Сколько рёбер в дереве с n узлами?

1. An + 1
2. Bn − 1
3. C2n
4. Dn

Что хранит отображение (map, словарь)?

1. AЗначения, отсортированные по размеру
2. BПары ключ–значение с уникальными ключами
3. CТолько значения в порядке вставки
4. DПары одинаковых ключей

Какая структура данных работает по принципу «последним пришёл — первым ушёл» (LIFO)?

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

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

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

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

1. A2^h+1 − 1
2. Bh²
3. C2^h
4. D2h + 1

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

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

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

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

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

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