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

В каком порядке прямой обход (preorder) двоичного дерева посещает узлы?

1. AЛевое поддерево, затем правое поддерево, затем узел
2. BУзел, затем левое поддерево, затем правое поддерево
3. CЛевое поддерево, затем узел, затем правое поддерево
4. DПо уровням сверху вниз

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

1. AОчередь
2. BКуча
3. CБинарное дерево
4. DСтек

Что содержит каждый узел двусвязного списка?

1. AДве копии данных и один указатель
2. BДанные и два указателя: один на следующий узел и один на узел после него
3. CДанные и только указатель на следующий узел
4. DДанные, указатель на следующий узел и указатель на предыдущий узел

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

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

Почему двоичную кучу можно хранить в массиве без каких-либо указателей?

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

Симметричный обход (in-order) двоичного дерева поиска посещает ключи:

1. AВ порядке вставки
2. BВ порядке возрастания (отсортированно)
3. CПо уровням
4. DВсегда в порядке убывания

Почему базы данных часто используют для индексов B+ деревья, а не обычные B-деревья?

1. AB+ деревья хранят данные только в корне
2. BB+ деревья используют двоичные внутренние узлы, что сокращает число чтений с диска
3. CB+ деревья не нужно балансировать
4. DВсе записи находятся в связанных листьях, что делает сканирование диапазонов эффективным

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

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