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

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

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

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

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

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

1. An + 1
2. Bn
3. Cn − 1
4. D2n

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

1. AВ односвязном списке
2. BВ двусвязном списке
3. CВ динамическом массиве
4. DВ отсортированном массиве

Какое условие балансировки поддерживает АВЛ-дерево в каждом узле?

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

Каков максимально возможный коэффициент заполнения хеш-таблицы с открытой адресацией?

1. A1
2. B2
3. CМаксимума нет
4. D0,5

Динамический массив удваивается при заполнении. Почему многие реализации уменьшают его, только когда он заполнен на четверть, а не наполовину?

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

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

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