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

Как называется операция стека, добавляющая элемент на вершину?

1. AEnqueue
2. BPeek
3. CPush
4. DPop

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

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

Что такое цикл в графе?

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

Какова стоимость вставки элемента в середину массива из n элементов?

1. AO(n), потому что последующие элементы нужно сдвинуть
2. BO(n²), потому что каждый элемент сдвигается n раз
3. CO(log n) из-за двоичного поиска
4. DO(1), потому что индекс известен

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

1. A4 5 2 3 1
2. B5 4 3 2 1
3. C4 2 5 1 3
4. D1 2 4 5 3

Где в двоичной куче, хранящейся в массиве с индексацией от 0, находится родитель узла с индексом i?

1. AВ индексе i − 1
2. BВ индексе 2i + 1
3. CВ индексе ⌊(i − 1) / 2⌋
4. DВ индексе ⌊i / 2⌋ + 1

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

1. AХранить каждый посещённый узел в хеш-множестве
2. BСчитать узлы, пока счёт не превысит поле длины списка
3. CОтсортировать список и искать повторы
4. DДвигать один указатель на один шаг, а другой на два и проверять, встретятся ли они

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

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