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

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

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

В чём главное отличие статического массива от динамического?

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

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

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

Сколько времени занимает проверка существования ребра (u, v) с помощью матрицы смежности?

1. AO(1)
2. BO(V)
3. CO(log V)
4. DO(E)

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

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

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

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

Структура union-find (система непересекающихся множеств) с объединением по рангу и сжатием путей имеет амортизированную стоимость операции:

1. AРовно O(log n)
2. BO(α(n)), обратная функция Аккермана, практически константа
3. CO(n²)
4. DO(n)

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

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