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

Где находится наименьший элемент двоичной min-кучи?

1. AВ самом левом листе
2. BВ последней позиции массива
3. CВ корне
4. DВ каком-то листе, который придётся искать

Что такое коллизия в хеш-таблице?

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

Что такое корень дерева?

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

АВЛ-деревья (AVL) и красно-чёрные деревья гарантируют:

1. AПоиск за константное время в любом случае
2. BВысоту O(log n) благодаря перебалансировке
3. CХранение ключей в порядке вставки
4. DЧто ни у одного узла нет двух потомков

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

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

Сколько памяти занимают списки смежности для графа с V вершинами и E рёбрами?

1. AO(E²)
2. BO(V + E)
3. CO(V²)
4. DO(V × E)

Почему базы данных часто используют для индексов B+ деревья, а не обычные B-деревья?

1. AB+ деревья не нужно балансировать
2. BB+ деревья хранят данные только в корне
3. CB+ деревья используют двоичные внутренние узлы, что сокращает число чтений с диска
4. DВсе записи находятся в связанных листьях, что делает сканирование диапазонов эффективным

В чём главное преимущество списка с пропусками (skip list) перед отсортированным связным списком?

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