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

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

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

Какова определяющая особенность множества как абстрактного типа данных?

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

Что такое дек (deque, двусторонняя очередь)?

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

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

1. A4 5 2 3 1
2. B4 2 5 1 3
3. C5 4 3 2 1
4. D1 2 4 5 3

Чему равно значение постфиксного выражения 3 4 + 2 * ?

1. A11
2. B10
3. C24
4. D14

Сколько времени занимает поиск слова длины L в префиксном дереве (trie) с фиксированным алфавитом?

1. AO(log n), где n — число слов
2. BO(L × n)
3. CO(L), независимо от числа хранимых слов
4. DO(n), где n — число слов

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

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

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

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