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

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

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

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

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

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

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

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

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);
        }
    }
}

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

Рассмотрим следующий код:

y = y + z
for i in range(1, n + 1):
    k = k + 2;
for i in range(1, n + 1):
    for j in range(1, n + 1):
        x = x + 1;

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

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