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

Высота дерева обычно определяется как:

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

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

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

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

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

Где в двоичной куче, хранящейся в массиве с индексацией от 0, находится родитель узла с индексом i?

1. AВ индексе ⌊i / 2⌋ + 1
2. BВ индексе ⌊(i − 1) / 2⌋
3. CВ индексе 2i + 1
4. DВ индексе i − 1

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

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

В дорожной сети 100 000 перекрёстков, каждый соединён примерно с 4 другими. Какое представление подходит лучше всего?

1. AДвоичная куча рёбер
2. BОдин отсортированный массив вершин
3. CМатрица смежности
4. DСписки смежности

Для чего используется структура union-find в алгоритме Краскала построения минимального остовного дерева?

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

Алгоритм Кана для топологической сортировки многократно удаляет вершины с полустепенью захода 0. Какая структура хранит эти вершины?

1. AMax-куча, упорядоченная по полустепени исхода
2. BСтек всех посещённых рёбер
3. CМатрица смежности, фиксирующая, какие вершины уже удалены
4. DОчередь (или любая коллекция) вершин с полустепенью захода 0