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

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

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

В каком порядке прямой обход (preorder) двоичного дерева посещает узлы?

1. AЛевое поддерево, затем правое поддерево, затем узел
2. BЛевое поддерево, затем узел, затем правое поддерево
3. CПо уровням сверху вниз
4. DУзел, затем левое поддерево, затем правое поддерево

Где находится наименьший элемент двоичной min-кучи?

1. AВ последней позиции массива
2. BВ корне
3. CВ каком-то листе, который придётся искать
4. DВ самом левом листе

Префиксное дерево (trie) особенно эффективно для:

1. AХранения матриц
2. BПоиска по префиксу, например автодополнения
3. CПоиска кратчайших путей
4. DСортировки чисел

Почему обход массива на практике часто гораздо быстрее обхода связного списка той же длины?

1. AЭлементы массива расположены непрерывно, поэтому хорошо используют кэш процессора
2. BОбход массива занимает в сумме O(1), а связного списка — O(n)
3. CСвязные списки всегда хранят элементы на диске
4. DМассивы требуют меньше инструкций для сравнения значений

Какая структура данных используется, чтобы проверить, сбалансированы ли скобки в «{[()]}»?

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

Ключи 5, 3, 8, 1 вставляются в таком порядке в пустую двоичную min-кучу на массиве. Каков итоговый массив?

1. A[1, 3, 8, 5]
2. B[3, 1, 8, 5]
3. C[1, 5, 8, 3]
4. D[1, 3, 5, 8]

Какая пара обходов всегда однозначно определяет двоичное дерево с различными ключами?

1. AПрямой и обратный (preorder и postorder)
2. BПрямой и симметричный (preorder и inorder)
3. CОдин только обход по уровням
4. DОдин только прямой