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

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

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

Какие из представленных ниже утверждений являются верными?

• 1)

• 2)

• 3),  — константа

• 4)

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

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

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

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

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

Пусть структура данных поддерживает операцию `foo`, таким образом, что последовательность из n операций `foo` занимает времени в худшем случае. Каково амортизационное время операции `foo`?

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

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