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

Граф состоит из:

1. AСтрок и столбцов
2. BВершин (узлов), соединённых рёбрами
3. CТолько ключей и хешей
4. DТолько корня и листьев

Что такое лист дерева?

1. AУзел без потомков
2. BУзел с наибольшим значением
3. CУзел без родителя
4. DУзел ровно с одним потомком

Какую структуру обычно используют для реализации очереди с приоритетом?

1. AСтек
2. BНеупорядоченный односвязный список
3. CКучу
4. DСтроку

У узла двоичного дерева поиска есть правое поддерево. Где находится его in-order преемник?

1. AСамый левый узел его правого поддерева
2. BВсегда его родитель
3. CВсегда его правый потомок
4. DСамый правый узел его левого поддерева

Какой метод разрешения коллизий хранит конфликтующие ключи в списке в той же корзине?

1. AМетод цепочек (separate chaining)
2. BЛинейное пробирование
3. CКвадратичное пробирование
4. DДвойное хеширование

Какое условие балансировки поддерживает АВЛ-дерево в каждом узле?

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

Какую гарантию дают правила красно-чёрного дерева относительно высоты дерева с n ключами?

1. AВысота не превышает 2 log₂(n + 1)
2. BВысота не превышает n / 2
3. CВысота равна ровно log₂ n
4. DВысота не превышает log₂ n + 1

Динамический массив удваивается при заполнении. Почему многие реализации уменьшают его, только когда он заполнен на четверть, а не наполовину?

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