Базовые и "продвинутые" алгоритмы для школьников

Упражнение 1:

Номер 1

Таблица, где как столбцы, так и строки соответствуют вершинам графа, носит название

Ответ:

(1) матрица инцидентности

(2) матрица смежности

(3) матрица комплексности

Номер 2

В матрице смежности строки соответствуют

Ответ:

(1) ребрам графа

(2) вершинам графа

(3) маркерам графа

Номер 3

В матрице смежности столбцы соответствуют

Ответ:

(1) вершинам графа

(2) ребрам графа

(3) идентификаторам графа

Упражнение 2:

Номер 1

Сколько памяти занимает хранение матрицы смежности?

Ответ:

(1) квадрат количества вершин

(2) логарифм количества вершин

(3) количество вершин

Номер 2

В матрице инцидентности строки соответствуют

Ответ:

(1) вершинам графа

(2) ребрам графа

(3) итераторам графа

Номер 3

В матрице инцидентности столбцы соответствуют

Ответ:

(1) вершинам графа

(2) связям графа

(3) модификаторам графа

Упражнение 3:

Номер 1

Какие значения могут содержаться в матрице инцидентности?

Ответ:

(1) 1

(2) 0

(3) end

Номер 2

Если связь является петлей, в матрицу инцидентности записывается

Ответ:

(1) 0

(2) 1

(3) любое число, кроме 0, 1, -1

Номер 3

Каждое ребро графа в списке ребер представляется

Ответ:

(1) номерами вершин ребра

(2) маркерами ребра

(3) весом ребра

Упражнение 4:

Номер 1

Для чего используется алгоритм Форда-Беллмана?

Ответ:

(1) для формирования матрицы смежности

(2) для поиска кратчайшего пути во взвешенном графе

(3) для вывода списка ребер

Номер 2

Граф в алгоритме Форда-Беллмана должен быть

Ответ:

(1) статическим

(2) динамическим

(3) взвешенным

Номер 3

В чем отличие алгоритма Форда-Беллмана от алгоритма Дейкстры?

Ответ:

(1) порядок массивной сложности

(2) использование отрицательных ребер

(3) отличий нет

Упражнение 5:

Номер 1

Сумма весов рёбер, входящих в путь, носит название

Ответ:

(1) длина пути

(2) вес пути

(3) глубина пути

Номер 2

Длина пути в графе - это

Ответ:

(1) количество пройденных ребер

(2) сумма весов ребер пути

(3) сумма по столбцу матрицы достижимости

Номер 3

Цикл, сумма весов рёбер которого отрицательна, называется

Ответ:

(1) маркированным циклом

(2) деградационным циклом

(3) отрицательным циклом

Упражнение 6:

Номер 1

Для чего используется алгоритм Флойда?

Ответ:

(1) для вывода матрицы инцидентности

(2) для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа

(3) для поиска длин динамических путей в графе

Номер 2

Каким должен быть граф в алгоритме Флойда?

Ответ:

(1) взвешенным

(2) массивным

(3) комплексным

Номер 3

Граф в алгоритме Флойда должен быть

Ответ:

(1) циклическим

(2) ориентированным

(3) модульным

Упражнение 7:

Номер 1

Какую сложность имеет алгоритм Флойда?

Ответ:

(1) квадратичную

(2) кубическую

(3) экспоненциальную

Номер 2

Сложность алгоритма Флойда выражается временем

Ответ:

(1) O(n³)

(2) O(n²)

(3) O(n)

Номер 3

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

Ответ:

(1) O(n³)

(2) O(nlogn)

(3) O(logn)

Упражнение 8:

Номер 1

Кратчайшие пути между всеми парами вершин взвешенного ориентированного графа можно найти с помощью

Ответ:

(1) алгоритма Брайана

(2) алгоритма Джонсона

(3) алгоритма Стеффсона

Номер 2

Работает ли алгоритм Джонсона в графах с отрицательными циклами?

Ответ:

(1) да, работает

(2) нет, не работает

(3) зависит от типа графа

Номер 3

Каким должен быть граф в алгоритме Джонсона?

Ответ:

(1) взвешенным

(2) ориентированным

(3) модульным

Упражнение 9:

Номер 1

Время работы алгоритма Джонсона равно

Ответ:

(1) O(V²lgV + VE)

(2) O(ElogV)

(3) O(EV²)

Номер 2

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

Ответ:

(1) поиск в ширину

(2) поиск в глубину

(3) модульный поиск

Номер 3

DFS - это

Ответ:

(1) поиск в глубину

(2) метод сжатия

(3) матрица достижимости

Упражнение 10:

Номер 1

При поиске в глубину всегда развертывается

Ответ:

(1) самый глубокий узел

(2) самый доступный узел

(3) самый первый узел

Номер 2

Очередь LIFO носит название

Ответ:

(1) стек

(2) контейнер

(3) массив

Номер 3

Стек имеет реализацию доступа

Ответ:

(1) LIFO

(2) FILO

(3) FIFO

Упражнение 11:

Номер 1

Поиск в глубину требует хранения пути

Ответ:

(1) между всеми листами

(2) от корня до листового узла

(3) от вершины до смежных листов

Номер 2

После того как при поиске в глубину был развернут некоторый узел

Ответ:

(1) он может быть удален из памяти

(2) он хранится в матрице смежности

(3) он записывается в конец стека вершин

Номер 3

Для пространства состояний с коэффициентом ветвления b и максимальной глубиной m поиск в глубину требует хранения

Ответ:

(1) b+m узлов

(2) bm+1 узлов

(3) blogm узлов

Упражнение 12:

Номер 1

Для пространства состояний с коэффициентом ветвления 4 и максимальной глубиной 5 поиск в глубину требует хранения

Ответ:

(1) 15 узлов

(2) 21 узел

(3) 24 узла

Номер 2

Для пространства состояний с коэффициентом ветвления 3 и максимальной глубиной 4 поиск в глубину требует хранения

Ответ:

(1) 10 узлов

(2) 11 узлов

(3) 13 узлов

Номер 3

Для пространства состояний с коэффициентом ветвления 6 и максимальной глубиной 3 поиск в глубину требует хранения

Ответ:

(1) 19 узлов

(2) 18 узлов

(3) 17 узлов

Базовые и "продвинутые" алгоритмы для школьников - тест 3