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

Что хранится для каждой вершины в представлении графа списками смежности?

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

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

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

Сколько рёбер в дереве с n узлами?

1. An + 1
2. Bn
3. C2n
4. Dn − 1

Почему обход массива на практике часто гораздо быстрее обхода связного списка той же длины?

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

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

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

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

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

Какая пара обходов всегда однозначно определяет двоичное дерево с различными ключами?

1. AОдин только обход по уровням
2. BПрямой и обратный (preorder и postorder)
3. CПрямой и симметричный (preorder и inorder)
4. DОдин только прямой

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

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