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

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

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

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

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

Что такое коллизия в хеш-таблице?

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

Сколько времени занимает поиск слова длины L в префиксном дереве (trie) с фиксированным алфавитом?

1. AO(log n), где n — число слов
2. BO(L), независимо от числа хранимых слов
3. CO(L × n)
4. DO(n), где n — число слов

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

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

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

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

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

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

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

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