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

Что такое цикл в графе?

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

Глубина узла в дереве — это:

1. AЧисло потомков этого узла
2. BЧисло рёбер от корня до этого узла
3. CЧисло узлов в его поддереве
4. DЧисло рёбер от этого узла до самого глубокого листа

Что такое дек (deque, двусторонняя очередь)?

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

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

1. AВ двусвязном списке
2. BВ отсортированном массиве
3. CВ односвязном списке
4. DВ динамическом массиве

У узла двоичного дерева поиска есть правое поддерево. Где находится его in-order преемник?

1. AВсегда его родитель
2. BСамый левый узел его правого поддерева
3. CСамый правый узел его левого поддерева
4. DВсегда его правый потомок

Какова стоимость вставки элемента в середину массива из n элементов?

1. AO(1), потому что индекс известен
2. BO(log n) из-за двоичного поиска
3. CO(n), потому что последующие элементы нужно сдвинуть
4. DO(n²), потому что каждый элемент сдвигается n раз

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

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

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

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