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

Упражнение 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

Обозначим через n количество вершин, а через m - количество ребер в графе G. Время работы алгоритма Дейкстры выражается значением

Ответ:

(1) O(n + m²)

(2) O(n*log(n) + m)

(3) O(n+ m)

Номер 2

Обозначим через n количество вершин, а через m - количество ребер в графе G. Если m много меньше n², то граф G носит название

Ответ:

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

(2) разреженный

(3) вариативный

Номер 3

Обозначим через n количество вершин, а через m - количество ребер в графе G. Если для хранения непосещенных вершин использовать фибоначчиеву кучу, то время работы алгоритма Дейкстры составит

Ответ:

(1) O(logn + m)

(2) O(n + m)

(3) O(nlogn + m)

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

Номер 1

Матрица, элементами которой являются только 0 и 1, носит название

Ответ:

(1) простая

(2) бинарная

(3) вариативная

Номер 2

Бинарная матрица - это

Ответ:

(1) матрица с нулями на побочной диагонали

(2) матрица только с 0 и 1

(3) квадратная матрица

Номер 3

Бинарная матрица, в каждом столбце и строке которой лишь одна единица, а все остальные элементы - 0, носит название

Ответ:

(1) матрица связности

(2) матрица перестановки

(3) матрица возврата

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

Номер 1

Если в бинарной матрице на пересечении i-ой строки и j-го столбца стоит 1, и вершины i,j соединены ребром, и 0 в противном случае, то такая матрица называется

Ответ:

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

(2) матрицей зависимости

(3) матрицей непрерывности

Номер 2

Матрица достижимости орграфа является

Ответ:

(1) матрицей сдвига

(2) бинарной матрицей

(3) модульной матрицей

Номер 3

Информация о существовании путей между вершинами орграфа хранится

Ответ:

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

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

(3) в матрице вариативности

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

Номер 1

Какие операции применяются при вычислении булевой степени матрицы достижимости?

Ответ:

(1) конъюнкция

(2) дизъюнкция

(3) инъекция

Номер 2

Матрица сильной связности является

Ответ:

(1) симметричной

(2) модификативной

(3) транзитивной

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

Номер 1

В языке C++ логическое "или" обозначается символом

Ответ:

(1) ||

(2) &&

(3) @

Номер 2

 В языке C++ побитовое "или" обозначается символом

Ответ:

(1) |

(2) #

(3) $

Номер 3

Дизъюнкция является

Ответ:

(1) бинарной операцией

(2) инфиксной операцией

(3) когнитивной операцией

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

Номер 1

В языке C++ логическое "и" обозначается символом

Ответ:

(1) &&

(2) @

(3) %

Номер 2

В языке C++ побитовое "и" обозначается символом

Ответ:

(1) &

(2) %%

(3) &&

Номер 3

Если a=01100101, b=00101001, то конъюнкция a и b будет равна

Ответ:

(1) 01001101

(2) 00100001

(3) 00101001

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

Номер 1

К отношениям транзитивности следует отнести

Ответ:

(1) отношение порядка

(2) импликацию

(3) эквивалентность

Номер 2

Алгоритм Беллмана-Форда применяется для поиска

Ответ:

(1) минимального остовного поддерева

(2) порядка смежности вершин

(3) кратчайшего пути во взвешенном графе

Номер 3

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

Ответ:

(1) возможность использования отрицательных ребер

(2) использование дизъюнкции

(3) модификация бинарной матрицы

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

Номер 1

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

Ответ:

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

(2) модуль пути

(3) вес пути

Номер 2

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

Ответ:

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

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

(3) унимодальным циклом

Номер 3

Каким образом в алгоритме Беллмана-Форда можно определить, существует ли в графе G отрицательный цикл?

Ответ:

(1) модифицировать вершины графа

(2) произвести дополнительную внешнюю итерацию цикла

(3) пересмотреть кратчайшие пути остовных поддеревьев

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

Номер 1

Для чего применяется алгоритм Флойда-Уоршелла?

Ответ:

(1) для нахождения остовных поддеревьев

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

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

Номер 2

Какой граф рассматривается в алгоритме Флойда-Уоршелла?

Ответ:

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

(2) маркированный

(3) терминальный

Номер 3

Алгоритм Флойда-Уоршелла используется

Ответ:

(1) для неориентированного графа

(2) для ориентированного графа

(3) для детерминированного графа

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

Номер 1

На каждом шаге алгоритм Флойда-Уоршелла генерирует двухмерную матрицу, которая содержит

Ответ:

(1) псевдовершины графа

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

(3) маркированные остовные поддеревья графа

Номер 2

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

Ответ:

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

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

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

Номер 3

О чего зависит сложность алгоритма Флойда-Уоршелла?

Ответ:

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

(2) от связности графа

(3) от модуля весов ребер

"Продвинутые" алгоритмы для школьников - тест 4