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

Какая структура данных лучше всего подходит для функции «отменить» (undo) в текстовом редакторе?

1. AГраф
2. BОчередь
3. CХеш-множество
4. DСтек

В односвязном списке каждый узел содержит:

1. AДанные и ссылки на все остальные узлы
2. BДанные и индекс
3. CТолько данные
4. DДанные и ссылку на следующий узел

Что такое цикл в графе?

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

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

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

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

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

Какое условие балансировки поддерживает АВЛ-дерево в каждом узле?

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

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

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

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

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