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

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

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

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

1. AВставка в начало
2. BЧтение первого элемента
3. CДоступ к элементу с индексом i
4. DУдаление головного элемента

Хеш-таблица (hash table) хранит данные в виде:

1. AПар ключ–значение, расположение которых определяет хеш-функция
2. BДерева с упорядоченными ключами
3. CСтроки фиксированной длины
4. DТолько отсортированного списка

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

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

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

1. A2h + 1
2. B2^h+1 − 1
3. Ch²
4. D2^h

Почему двоичную кучу можно хранить в массиве без каких-либо указателей?

1. AВ кучах никогда не бывает больше 100 элементов
2. BМассивы автоматически хранят ключи в отсортированном порядке, поэтому указатели не нужны
3. CЭто полное двоичное дерево, поэтому позиции подчиняются простым формулам индексов
4. DВсе ключи в куче равны

Каково при простом равномерном хешировании ожидаемое время поиска в хеш-таблице с цепочками, n ключами и m корзинами?

1. AO(log n)
2. BO(1 + α), где α = n / m
3. CO(m)
4. DO(n)

Чем radix-дерево (сжатое префиксное дерево) лучше обычного trie?

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