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

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

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

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

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

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

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

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

1. A5 4 3 2 1
2. B4 5 2 3 1
3. C4 2 5 1 3
4. D1 2 4 5 3

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

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

Какова временная сложность поиска ключа в сбалансированном двоичном дереве поиска?

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

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

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

Временная сложность операции decrease-key в двоичной куче (при известной позиции элемента) составляет:

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