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

Какая структура данных работает по принципу «первым пришёл — первым ушёл» (FIFO)?

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. AМассивы автоматически хранят ключи в отсортированном порядке, поэтому указатели не нужны
2. BВ кучах никогда не бывает больше 100 элементов
3. CВсе ключи в куче равны
4. DЭто полное двоичное дерево, поэтому позиции подчиняются простым формулам индексов

Сколько времени занимает проверка существования ребра (u, v) с помощью матрицы смежности?

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

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

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

В кольцевом буфере front == rear может означать и «пуст», и «полон». Какой распространённый способ их различить?

1. AДелать размер буфера степенью двойки
2. BХранить front и rear в одной переменной
3. CВсегда очищать буфер, когда front равен rear, так что состояние — пустой
4. DХранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной

Чем radix-дерево (сжатое префиксное дерево) лучше обычного trie?

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