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

1

2

3

4

Тест по Computer Science, подготовил Участник:Ssyrovatkin

Вариант 3510994437.

Прошло 00:00:00.

Ваше имя*:

Вопрос 1

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

Вопрос 2

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

1
2
3
4

Вопрос 3

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

Модификация добавляет к общему весу всех остовных деревьев.
Порядок ребер, добавляемых к минимальному остовному дереву с использованием алгоритма Прима, изменится.
Порядок ребер, добавляемых к минимальному остовному дереву с использованием алгоритма Крускала, изменится.
Ничего из вышеперечисленного.

Вопрос 4

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

Вопрос 5

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

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

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

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

Ни одно
Только II
Оба
Только I

Вопрос 6

Пусть дана последовательность n случайных чисел. Какая будет временная сложность для вычисления медианы данного массива?

Вопрос 7

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

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