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

Что такое степень вершины в неориентированном графе?

1. AЧисло вершин графа
2. BЧисло инцидентных ей рёбер
3. CЕё позиция в списке смежности
4. DДлина самого длинного пути из неё

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

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

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

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

Какова стоимость вставки элемента в середину массива из n элементов?

1. AO(1), потому что индекс известен
2. BO(log n) из-за двоичного поиска
3. CO(n²), потому что каждый элемент сдвигается n раз
4. DO(n), потому что последующие элементы нужно сдвинуть

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

1. AВ отсортированном массиве
2. BВ двусвязном списке
3. CВ динамическом массиве
4. DВ односвязном списке

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков обратный обход (postorder)?

1. A4 5 2 3 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D5 4 3 2 1

Дерево отрезков (segment tree) обычно используют для:

1. AХранения рёбер графа
2. BСортировки строк по алфавиту путём хранения каждого префикса в отдельном узле дерева
3. CРеализации стека
4. DОтветов на запросы на диапазонах (например, суммы диапазонов) и обновлений за O(log n)

Ключи 5, 3, 8, 1 вставляются в таком порядке в пустую двоичную min-кучу на массиве. Каков итоговый массив?

1. A[3, 1, 8, 5]
2. B[1, 3, 5, 8]
3. C[1, 3, 8, 5]
4. D[1, 5, 8, 3]