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

Что такое взвешенный граф?

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

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

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

Хеш-таблица (hash table) хранит данные в виде:

1. AСтроки фиксированной длины
2. BДерева с упорядоченными ключами
3. CПар ключ–значение, расположение которых определяет хеш-функция
4. DТолько отсортированного списка

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

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

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

1. A4 5 2 3 1
2. B1 2 4 5 3
3. C4 2 5 1 3
4. D5 4 3 2 1

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

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

Какое утверждение о пирамидальной сортировке (heapsort) верно?

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

Временная сложность операции decrease-key в двоичной куче (при известной позиции элемента) составляет:

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