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

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

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

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

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

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

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

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

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

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

1. An (дерево превращается в связный список)
2. B1
3. Clog₂ n
4. D√n

Чему равно значение постфиксного выражения 3 4 + 2 * ?

1. A14
2. B10
3. C11
4. D24

Какую проблему линейного пробирования в основном уменьшает двойное хеширование?

1. AСтоимость O(n) чтения значения по ключу
2. BПервичную кластеризацию, при которой образуются длинные серии занятых ячеек
3. CНеобходимость в хеш-функции
4. DНеобходимость хранить ключи в таблице

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

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