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

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

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

В двоичном дереве поиска значения в левом поддереве узла:

1. AБольше значения узла
2. BРавны значению узла
3. CМеньше значения узла
4. DРасположены в случайном порядке

Что такое свойство max-кучи?

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

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

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

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

1. A4 5 2 3 1
2. B1 2 4 5 3
3. C4 2 5 1 3
4. D5 4 3 2 1

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

1. AВ динамическом массиве
2. BВ односвязном списке
3. CВ двусвязном списке
4. DВ отсортированном массиве

Структура union-find (система непересекающихся множеств) с объединением по рангу и сжатием путей имеет амортизированную стоимость операции:

1. AРовно O(log n)
2. BO(n)
3. CO(α(n)), обратная функция Аккермана, практически константа
4. DO(n²)

Динамический массив удваивается при заполнении. Почему многие реализации уменьшают его, только когда он заполнен на четверть, а не наполовину?

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