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

Предположим, что G — это связный неориентированный граф, ребра которого имеют положительные веса. Пусть M — минимальное остовное дерево этого графа. Мы модифицируем граф, добавляя «6» к весу каждого ребра, какое из следующих утверждений верно?

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

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

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

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

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

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

Сколько остовных деревьев имеет данный граф (все ребра имеют одинаковый вес)?

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

Сколько вершин имеет дерево с 57 ребрами?

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

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

Пусть и что из ниже перечисленного является верным?