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

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

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

Какая структура данных используется для обхода дерева по уровням (level-order)?

1. AОчередь
2. BСтек
3. CХеш-таблица
4. DОчередь с приоритетом

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

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

Префиксное дерево (trie) особенно эффективно для:

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

В дорожной сети 100 000 перекрёстков, каждый соединён примерно с 4 другими. Какое представление подходит лучше всего?

1. AСписки смежности
2. BОдин отсортированный массив вершин
3. CДвоичная куча рёбер
4. DМатрица смежности

Узел АВЛ-дерева разбалансирован, потому что правое поддерево его левого потомка стало слишком высоким (случай левый–правый). Какое исправление применяется?

1. AЛевый поворот в левом потомке, затем правый поворот в узле
2. BПравый поворот в левом потомке, затем левый поворот в узле
3. CОдиночный правый поворот в узле
4. DОдиночный левый поворот в узле

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

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