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

Какая структура данных используется для обхода дерева по уровням (level-order)?

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Оно хранит элементы без повторений

Как работает extract-min в двоичной min-куче?

1. AУдаляют последний элемент массива
2. BПоследний элемент перемещают в корень и опускают вниз (sift down)
3. CУдаляют корень и сдвигают все элементы на одну позицию влево
4. DИщут новый минимум среди всех листьев

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

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

Сколько памяти занимает матрица смежности графа с V вершинами?

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

В BST с корнем 50, левым поддеревом 30 (потомки 20, 40) и правым поддеревом 70 (потомки 60, 80) корень удаляют с помощью in-order преемника. Какой ключ станет новым корнем?

1. A70
2. B40
3. C60
4. D80

Какая структура данных обеспечивает кэш LRU (least recently used) с операциями get и put за O(1)?

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