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

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

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

• I.

• II.

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

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

Предположим, что G — это связный неориентированный граф, ребра которого имеют положительные веса. Пусть M — минимальное остовное дерево этого графа. Мы модифицируем граф, добавляя «6» к весу каждого ребра, какое из следующих утверждений верно?

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

Сколько раз происходит обращение ко всем вершинам в графе G(V, E) в процессе работы алгоритма поиска в глубину?

Пусть имеется два отсортированных списка размера K и L соответственно. Сколько потребуется сравнений элементов, для того чтобы получить отсортированный список размера K + L, состоящий из элементов этих списков?

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

• 1)

• 2)

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

• 4)

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

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