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

Дан неориентированный граф G = (V, E) и положительное целое число K, имеет ли G K вершин, которые образуют полный подграф, и если да, то каково минимальное значение K?

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

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

• 1)

• 2)

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

• 4)

Какова временная сложность выполнения алгоритма Беллмана-Форда на K-регулярном графе ()?

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

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

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

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

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

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

Рассмотрим следующее рекуррентное соотношение: Какое из следующих утверждений является верным?

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

Сколько раз происходит обращение ко всем вершинам в графе G(V, E) в процессе работы алгоритма поиска в глубину?

Какое из представленных ниже регулярных выражений задает строки вида , где m, p, n больше либо равно 2.