Тест по Computer Science — вопросы

Рассмотрим следующее AVL-дерево:

Если в данное дерево требуется вставить элемент со значением 12, сколько поворотов необходимо сделать для балансировки дерева?

Пусть дана последовательность n случайных чисел. Какая будет временная сложность для нахождения элемента, который встречается больше, чем n/2 раз (если такой элемент существует)?

Хэш функция с линейным зондированием используется для вставки ключей 37, 38, 72, 68, 98, 11, 74 в хэш-таблицу с индексом (0-6). Какой индекс соответствует ключу 74?

Рассмотрим следующие выражения:

• I. Подсчет медианы из n элементов занимает времени для любого алгоритма, основанного на сравнении элементов.

• II. Пусть T является минимальным остовным деревом для графа G. Тогда для любой пары вершин a и b кратчайший путь между ними в G является кратчайшим путем между ними в T.

Какие утверждения верные, а какие нет?

Рассмотрим массив из n элементов. Какую временную сложность имеет алгоритм поиска максимальной суммы трех элементов в массиве?

Пусть M является целым числом, которое больше единицы. Какая асимптотика роста функции является верной?

Каково число подстрок любой длины, за исключением пустой строки, может быть получено из заданной строки длиной n?

Какие из представленных ниже утверждений являются верными?

• 1)

• 2)

• 3),  — константа

• 4)

Рассмотрим следующие утверждения об алгоритме обхода графа в глубину:

• I. Предположим, мы запускаем DFS на неориентированном графе и находим ровно 15 обратных ребер. Тогда граф гарантированно будет иметь по крайней мере один цикл.

• II. DFS на ориентированном графе с n вершинами и, по крайней мере, n ребрами гарантированно найдет хотя бы одно обратное ребро.

Какие из данных утверждений верны?

Для какой из изображенных ниже куч на минимум будут получены элементы массива в порядке возрастания, если для кучи применяется обход preorder traversal?