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

Какая структура данных лучше всего подходит для функции «отменить» (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Высоты левого и правого поддеревьев различаются не более чем на 1
3. CВсе листья находятся ровно на одной глубине
4. DКаждый узел окрашен в красный или чёрный цвет

В дорожной сети 100 000 перекрёстков, каждый соединён примерно с 4 другими. Какое представление подходит лучше всего?

1. AМатрица смежности
2. BДвоичная куча рёбер
3. CСписки смежности
4. DОдин отсортированный массив вершин

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

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

Для чего используется структура union-find в алгоритме Краскала построения минимального остовного дерева?

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

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

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