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

Что такое корень дерева?

1. AУзел без потомков
2. BУзел с наибольшим значением
3. CВерхний узел, у которого нет родителя
4. DЛюбой узел в середине

Где находится наименьший элемент двоичной min-кучи?

1. AВ самом левом листе
2. BВ корне
3. CВ каком-то листе, который придётся искать
4. DВ последней позиции массива

Какая структура данных работает по принципу «первым пришёл — первым ушёл» (FIFO)?

1. AКуча
2. BОчередь
3. CСтек
4. DБинарное дерево

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков прямой обход (preorder)?

1. A4 2 5 1 3
2. B1 2 4 5 3
3. C4 5 2 3 1
4. D1 2 3 4 5

Как работает extract-min в двоичной min-куче?

1. AИщут новый минимум среди всех листьев
2. BУдаляют корень и сдвигают все элементы на одну позицию влево
3. CУдаляют последний элемент массива
4. DПоследний элемент перемещают в корень и опускают вниз (sift down)

Очередь реализована двумя стеками: push в стек «in», pop из стека «out», который при опустошении заполняется из «in». Какова амортизированная стоимость одной операции?

1. AO(1)
2. BO(n)
3. CO(log n)
4. DO(n²)

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

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

Какое утверждение о пирамидальной сортировке (heapsort) верно?

1. AОна сортирует на месте за O(n log n) в худшем случае, но не является устойчивой
2. BЕй нужно двоичное дерево поиска как дополнительное хранилище, поэтому она использует O(n) дополнительной памяти
3. CОна устойчива и требует O(n) дополнительной памяти
4. DОна работает за O(n) на любых входных данных