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

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

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

В односвязном списке каждый узел содержит:

1. AДанные и ссылки на все остальные узлы
2. BТолько данные
3. CДанные и индекс
4. DДанные и ссылку на следующий узел

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

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

Где в двоичной куче, хранящейся в массиве с индексацией от 0, находится родитель узла с индексом i?

1. AВ индексе i − 1
2. BВ индексе ⌊(i − 1) / 2⌋
3. CВ индексе 2i + 1
4. DВ индексе ⌊i / 2⌋ + 1

Симметричный обход (in-order) двоичного дерева поиска посещает ключи:

1. AВ порядке вставки
2. BПо уровням
3. CВ порядке возрастания (отсортированно)
4. DВсегда в порядке убывания

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

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

Какая пара обходов всегда однозначно определяет двоичное дерево с различными ключами?

1. AОдин только прямой
2. BПрямой и симметричный (preorder и inorder)
3. CОдин только обход по уровням
4. DПрямой и обратный (preorder и postorder)

Объект хранится как ключ в хеш-отображении, а затем меняется поле, используемое его хеш-функцией. Каков вероятный результат?

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