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

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

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

Алгоритм Беллмана-Форда решает задачу кратчайшего пути из вершины в случае, когда веса ребер могут быть отрицательными, какова временная сложность выполнения алгоритма Беллмана-Форда?

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

• I. Диграф — это граф, имеющий ровно 2 вершины.

• II. Остовное дерево в графе всегда должно содержать как минимум ребер.

• III. Алгоритм сортировки ребер для решения задачи коммивояжера всегда дает оптимальный результат.

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

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

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

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

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

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

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

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

Предположим, что символы a,b,c,d,e встречаются с частотами . Какие получатся коды Хаффмана для букв a,b,c соответственно?

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