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

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

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

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

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

Как элементы массива хранятся в памяти?

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

Ключи 50, 30, 70, 20, 40 вставляются в таком порядке в пустое двоичное дерево поиска. Кто левый потомок 30?

1. A40
2. B70
3. C20
4. D50

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

1. Ah²
2. B2h + 1
3. C2^h
4. D2^h+1 − 1

Хеш-таблица размера 7 использует h(k) = k mod 7 и линейное пробирование. Где окажется 17 после вставки 10?

1. AВ индексе 0
2. BВ индексе 4
3. CВ индексе 3
4. DВ индексе 6

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

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

Ключи 5, 3, 8, 1 вставляются в таком порядке в пустую двоичную min-кучу на массиве. Каков итоговый массив?

1. A[1, 3, 5, 8]
2. B[3, 1, 8, 5]
3. C[1, 3, 8, 5]
4. D[1, 5, 8, 3]