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

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

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

В чём главное отличие статического массива от динамического?

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

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

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

Хеш-таблица размера 7 использует h(k) = k mod 7 и линейное пробирование. Где окажется 17 после вставки 10?

1. AВ индексе 3
2. BВ индексе 0
3. CВ индексе 4
4. DВ индексе 6

Какая структура данных используется, чтобы проверить, сбалансированы ли скобки в «{[()]}»?

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

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

1. A5 4 3 2 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D4 5 2 3 1

Какова стоимость одной операции find в худшем случае в структуре union-find с n элементами без объединения по рангу и сжатия путей?

1. AO(1)
2. BO(log n)
3. CO(n)
4. DO(α(n))

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

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