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

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

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

Какая операция выполняется за O(1) для массива, но за O(n) для односвязного списка?

1. AЧтение первого элемента
2. BВставка в начало
3. CУдаление головного элемента
4. DДоступ к элементу с индексом i

Глубина узла в дереве — это:

1. AЧисло узлов в его поддереве
2. BЧисло потомков этого узла
3. CЧисло рёбер от корня до этого узла
4. DЧисло рёбер от этого узла до самого глубокого листа

Как в кольцевой очереди, хранящейся в массиве ёмкостью n, вычисляется следующая позиция после индекса i?

1. A(i + 1) mod n
2. B(i − 1) mod n
3. Ci + 1
4. D2i + 1

Префиксное дерево (trie) особенно эффективно для:

1. AХранения матриц
2. BПоиска по префиксу, например автодополнения
3. CСортировки чисел
4. DПоиска кратчайших путей

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

1. A1 2 4 5 3
2. B4 5 2 3 1
3. C4 2 5 1 3
4. D1 2 3 4 5

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

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

Какова стоимость одной операции find в худшем случае в структуре union-find с n элементами без объединения по рангу и сжатия путей?

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