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

В каком порядке обратный обход (postorder) двоичного дерева посещает узлы?

1. AУзел, затем левое поддерево, затем правое поддерево
2. BЛевое поддерево, затем правое поддерево, затем узел
3. CПравое поддерево, затем узел, затем левое поддерево
4. DЛевое поддерево, затем узел, затем правое поддерево

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

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

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

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

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

1. AХеш-таблица
2. BНеотсортированный связный список
3. CСтек
4. DСбалансированное двоичное дерево поиска

Сколько памяти занимают списки смежности для графа с V вершинами и E рёбрами?

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

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

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

Какая структура позволяет вычислить максимум каждого окна размера k в массиве за общее время O(n)?

1. AMin-куча, перестраиваемая для каждого окна
2. BОдносвязный список элементов окна
3. CДек, хранящий индексы в порядке убывания значений
4. DОтсортированный массив, обновляемый сдвигами

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

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