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

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

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

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

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

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

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

Какое условие балансировки поддерживает АВЛ-дерево в каждом узле?

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

Сколько узлов в идеальном (perfect) двоичном дереве высоты h, если высота считается в рёбрах?

1. A2^h
2. B2h + 1
3. Ch²
4. D2^h+1 − 1

Каков максимально возможный коэффициент заполнения хеш-таблицы с открытой адресацией?

1. A0,5
2. BМаксимума нет
3. C1
4. D2

Какова стоимость одной операции find в худшем случае в структуре union-find с n элементами без объединения по рангу и сжатия путей?

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

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

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