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

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

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

Что определяет двоичное дерево?

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

Что такое свойство max-кучи?

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

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

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

Как в кольцевой очереди, хранящейся в массиве ёмкостью n, вычисляется следующая позиция после индекса i?

1. Ai + 1
2. B(i + 1) mod n
3. C(i − 1) mod n
4. D2i + 1

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

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

Какое утверждение о пирамидальной сортировке (heapsort) верно?

1. AЕй нужно двоичное дерево поиска как дополнительное хранилище, поэтому она использует O(n) дополнительной памяти
2. BОна сортирует на месте за O(n log n) в худшем случае, но не является устойчивой
3. CОна работает за O(n) на любых входных данных
4. DОна устойчива и требует O(n) дополнительной памяти

В BST с корнем 50, левым поддеревом 30 (потомки 20, 40) и правым поддеревом 70 (потомки 60, 80) корень удаляют с помощью in-order преемника. Какой ключ станет новым корнем?

1. A40
2. B60
3. C70
4. D80