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

Каково число подстрок любой длины, за исключением пустой строки, может быть получено из заданной строки длиной n?

Рассмотрим следующие утверждения (h(k) — хэш-функция):

• I. если даже .

• II. для любых .

• III. для любых .

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

Запустим алгоритм Дейкстры, начиная с вершины S, чтобы найти кратчайший путь T, и рассмотрим следующие утверждения:

• I. Алгоритм Дейкстры возвращает кратчайший путь с минимальным общим весом.

• II. Алгоритм Дейкстры возвращает кратчайший путь с минимальным количеством ребер.

Какие из данных утверждений верны?

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

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

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

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

• 1)

• 2)

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

• 4)

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

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