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

В каком порядке прямой обход (preorder) двоичного дерева посещает узлы?

1. AУзел, затем левое поддерево, затем правое поддерево
2. BПо уровням сверху вниз
3. CЛевое поддерево, затем правое поддерево, затем узел
4. DЛевое поддерево, затем узел, затем правое поддерево

Какая операция выполняется за O(1) для массива, но за O(n) для односвязного списка?

1. AВставка в начало
2. BДоступ к элементу с индексом i
3. CУдаление головного элемента
4. DЧтение первого элемента

В двоичном дереве поиска значения в левом поддереве узла:

1. AМеньше значения узла
2. BРасположены в случайном порядке
3. CРавны значению узла
4. DБольше значения узла

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

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

Чему равно значение постфиксного выражения 3 4 + 2 * ?

1. A11
2. B14
3. C24
4. D10

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

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

Алгоритм Кана для топологической сортировки многократно удаляет вершины с полустепенью захода 0. Какая структура хранит эти вершины?

1. AМатрица смежности, фиксирующая, какие вершины уже удалены
2. BMax-куча, упорядоченная по полустепени исхода
3. CСтек всех посещённых рёбер
4. DОчередь (или любая коллекция) вершин с полустепенью захода 0

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

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