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

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

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

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

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

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

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

Сколько существует различных бинарных деревьев с 8 узлами?

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

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

Какие из следующих алгоритмов используют подход Разделяй и Властвуй?

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

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

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

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

• I.

• II.

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