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

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

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

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

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

Что такое коэффициент заполнения (load factor) хеш-таблицы?

1. AЧисло хранимых элементов, делённое на число корзин
2. BЧисло корзин, делённое на среднюю длину хранимых ключей
3. CЧисло коллизий на данный момент
4. DВремя загрузки таблицы с диска

Зачем нужен сторожевой (фиктивный, sentinel) узел в связном списке?

1. AЧтобы хранить число элементов
2. BЧтобы список был отсортирован
3. CЧтобы упростить код, убрав особые случаи в голове или хвосте
4. DЧтобы список не мог вырасти сверх фиксированного максимального числа узлов

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

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

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

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

Каковы затраты времени и дополнительной памяти на разворот односвязного списка на месте?

1. AO(n log n) времени и O(1) дополнительной памяти
2. BO(n) времени и O(n) дополнительной памяти
3. CO(1) времени и O(1) дополнительной памяти
4. DO(n) времени и O(1) дополнительной памяти

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

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