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

Что такое узлы-братья (siblings) в дереве?

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

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

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

Как называется операция очереди, удаляющая элемент из начала?

1. AInsert
2. BEnqueue
3. CDequeue
4. DPush

Как найти минимальный ключ в двоичном дереве поиска?

1. AОбойти все листья и сравнить их
2. BИдти от корня по правым потомкам, пока правого потомка не окажется
3. CИдти от корня по левым потомкам, пока левого потомка не окажется
4. DПосмотреть только на корень

Зачем нужен сторожевой (фиктивный, sentinel) узел в связном списке?

1. AЧтобы список был отсортирован
2. BЧтобы упростить код, убрав особые случаи в голове или хвосте
3. CЧтобы список не мог вырасти сверх фиксированного максимального числа узлов
4. DЧтобы хранить число элементов

Сколько узлов в идеальном (perfect) двоичном дереве высоты h, если высота считается в рёбрах?

1. A2^h
2. Bh²
3. C2h + 1
4. D2^h+1 − 1

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

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

Удаление узла с двумя потомками из двоичного дерева поиска обычно выполняют так:

1. AМеняют его местами с корнем
2. BУдаляют всё поддерево
3. CЗаменяют его in-order преемником (или предшественником) и удаляют тот узел
4. DПерестраивают поддерево под ним с нуля и заново вставляют каждый содержавшийся в нём ключ