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

Что делает операция peek (или top) стека?

1. AУдаляет верхний элемент и возвращает его
2. BВозвращает верхний элемент, не удаляя его
3. CВозвращает нижний элемент стека
4. DУдаляет все элементы из стека

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

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

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

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

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

1. A5 4 3 2 1
2. B1 2 4 5 3
3. C4 2 5 1 3
4. D4 5 2 3 1

Какую структуру данных использует выполняющаяся программа для отслеживания активных вызовов функций и их локальных переменных?

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

Префиксное дерево (trie) особенно эффективно для:

1. AПоиска кратчайших путей
2. BХранения матриц
3. CПоиска по префиксу, например автодополнения
4. DСортировки чисел

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

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

Какому свойству должно удовлетворять красно-чёрное дерево?

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