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

Рассмотрим следующие утверждения об алгоритме обхода графа в глубину:

• I. Предположим, мы запускаем DFS на неориентированном графе и находим ровно 15 обратных ребер. Тогда граф гарантированно будет иметь по крайней мере один цикл.

• II. DFS на ориентированном графе с n вершинами и, по крайней мере, n ребрами гарантированно найдет хотя бы одно обратное ребро.

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

Пусть и что из ниже перечисленного является верным?

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

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;

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

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

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

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

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

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

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

• I.

• II.

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

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

• 1)

• 2)

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

• 4)

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

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

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