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

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

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

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

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

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

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

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

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

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

• I.

• II.

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

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

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

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

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

• 1)

• 2)

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

• 4)