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

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

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В индексе ⌊i / 2⌋ + 1
4. DВ индексе 2i + 1

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

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

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

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

Для чего используется структура union-find в алгоритме Краскала построения минимального остовного дерева?

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

Какую проблему линейного пробирования в основном уменьшает двойное хеширование?

1. AСтоимость O(n) чтения значения по ключу
2. BПервичную кластеризацию, при которой образуются длинные серии занятых ячеек
3. CНеобходимость хранить ключи в таблице
4. DНеобходимость в хеш-функции