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

Что такое лист дерева?

1. AУзел ровно с одним потомком
2. BУзел с наибольшим значением
3. CУзел без родителя
4. DУзел без потомков

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

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

Что содержит указатель next последнего узла односвязного списка?

1. AАдрес первого узла
2. BЧисло узлов в списке
3. CАдрес предыдущего узла
4. DNull (узла нет)

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

1. A20
2. B70
3. C40
4. D50

Как найти минимальный ключ в двоичном дереве поиска?

1. AИдти от корня по левым потомкам, пока левого потомка не окажется
2. BПосмотреть только на корень
3. CОбойти все листья и сравнить их
4. DИдти от корня по правым потомкам, пока правого потомка не окажется

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

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

Что делает косое дерево (splay tree) после каждого обращения?

1. AПоворотами поднимает узел, к которому обращались, в корень
2. BПерестраивает всё дерево в сбалансированном виде
3. CПерекрашивает узлы на пути поиска
4. DПеремещает узел, к которому обращались, в лист

Каково время работы поиска в ширину на графе с V вершинами, хранящемся в виде матрицы смежности?

1. AO(E log V)
2. BO(V)
3. CO(V + E)
4. DO(V²)