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

Что такое взвешенный граф?

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

Что хранится для каждой вершины в представлении графа списками смежности?

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

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

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

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

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

Что верно для матрицы смежности неориентированного графа?

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

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

1. Ah²
2. B2^h
3. C2^h+1 − 1
4. D2h + 1

Объект хранится как ключ в хеш-отображении, а затем меняется поле, используемое его хеш-функцией. Каков вероятный результат?

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

Какому свойству должно удовлетворять красно-чёрное дерево?

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