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

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

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

Что такое степень вершины в неориентированном графе?

1. AЕё позиция в списке смежности
2. BДлина самого длинного пути из неё
3. CЧисло инцидентных ей рёбер
4. DЧисло вершин графа

Какая операция выполняется за O(1) для массива, но за O(n) для односвязного списка?

1. AУдаление головного элемента
2. BЧтение первого элемента
3. CДоступ к элементу с индексом i
4. DВставка в начало

Почему двоичную кучу можно хранить в массиве без каких-либо указателей?

1. AВ кучах никогда не бывает больше 100 элементов
2. BЭто полное двоичное дерево, поэтому позиции подчиняются простым формулам индексов
3. CВсе ключи в куче равны
4. DМассивы автоматически хранят ключи в отсортированном порядке, поэтому указатели не нужны

Ключи 50, 30, 70, 20, 40 вставляются в таком порядке в пустое двоичное дерево поиска. Кто левый потомок 30?

1. A70
2. B40
3. C50
4. D20

Какую структуру данных использует поиск в глубину (DFS, итеративная версия)?

1. AСтек
2. BТолько хеш-таблицу
3. CКучу
4. DОчередь

Чем radix-дерево (сжатое префиксное дерево) лучше обычного trie?

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

Для каждого элемента массива нужно найти следующий больший элемент справа за общее время O(n). Какая структура поможет?

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