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

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

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

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

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

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

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

Пусть G = (V, E) неориентированный граф, какие утверждения ниже являются верными?

• I. Если G является деревом, то между двумя любыми вершинами G существует единственный уникальный путь.

• II. Если G = (V, E) является связным, и E = V - 1, тогда G является деревом.

• III. Удаление ребра из цикла не может сделать граф несвязным.

Какая временная сложность выполнения данного кода?

for (i = n; i > 0; i/= 2){
    for (int j = 1; j < n; j * = 2){
        for (int k = 0; k < n; k + = 2){
        sum + = (i + j * k);
        }
    }
}

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

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