Главная / Алгоритмы и дискретные структуры /
Комбинаторные алгоритмы для программистов / Тест 12
Номер 3
Ответ:
Комбинаторные алгоритмы для программистов - тест 12
Упражнение 1:
Номер 1
Ответ:
Номер 1
Сколько разрядов требуется для задания графа матрицей смежностей?
Ответ:
(1)
V2 двоичных разрядов
(2)
V двоичных разрядов
(3)
V2×E2 двоичных разрядов
(4)
V×E2
Номер 2
Ответ:
Какой граф называется взвешенным графом?
Ответ:
(1) граф, в котором ребру
(i,j) сопоставлено ∞
(2) граф, в котором ребру
(i,j) сопоставлено число 0, называется взвешенным графом, а число 0 называется весом ребра (i.j) .
(3) граф, в котором ребру
(i,j) сопоставлено число ∑ wij (число wij называется весом ребра (i,j))
(4) граф, в котором ребру
(i,j) сопоставлено число wij (число wij называется весом ребра (i,j))
Каким способом эффективнее представлять разреженный граф?
Ответ:
(1) списком ребер
(2) матрицей весов
(3) матрицей смежностей
(4) структурами смежности
Упражнение 2:
Номер 1
Ответ:
Номер 1
Каким способом нужно задать граф, если в алгоритмах граф модифицируется таким образом, что в нем добавляются или удаляются вершины?
Ответ:
(1) матрицей смежностей
(2) хранением списков смежности в виде связанного списка
(3) списком ребер
(4) структурой смежности
Номер 2
Ответ:
Как обычно задается простой взвешенный граф?
Ответ:
(1) своей матрицей весов
W = wij, где wij есть вес ребра, соединяющего вершины i и j. Веса несуществующих ребер обычно полагают равными ∞ или 0 в зависимости от приложений
(2) своей матрицей инцидентности
(3) своей матрицей смежности
(4) своей структурой смежности
Номер 3
Ответ:
Какой граф называется полным?
Ответ:
(1) если число вершин в графе равно числу ребер
(2) если каждая пара вершин в графе соединена ребром
(3) если число вершин в графе больше числа ребер
(4) если число вершин в графе меньше числа ребер
Упражнение 3:
Номер 1
Ответ:
Номер 1
Что называется путем в графе?
Ответ:
(1) простой путь, или для краткости, просто путь, записываемый иногда как
(v1,v2,...,vk), - это последовательность смежных ребер (v1,v2),(v2,v3),...,(vk-2,vk-1,(vk-1,vk), в которой все вершины v1,v2,...,vk различны, исключая, возможно, случай v1=vk
(2) простой путь, или для краткости, просто путь, - это последовательность смежных ребер
(v1,v2),(v2,v3),...,(vk-2,vk-1,(vk-1,vk), в которой все вершины v1,v2,...,vk различны, исключая, возможно, случай v1=vk
(3) простой путь, или для краткости, просто путь, записываемый иногда как
v1,v2,...,vk, - это последовательность смежных ребер (v1,v2),(v2,v3),...,(vk-2,vk-1,(vk-1,vk), в которой все вершины v1,v2,...,vk, одинаковы
(4) простой путь, или для краткости, просто путь, это
v1,v2,...,vk
Номер 2
Ответ:
Что называется длиной пути?
Ответ:
(1) число вершин в пути
(2) число ребер в пути
(3) удвоенное число ребер в пути
(4) число ребер в пути минус число вершин
Номер 3
Ответ:
Что является остовными деревьями графа G?
Ответ:
(1) деревья, являющиеся подграфами графа
G и содержащие все его ребра
(2) деревья, являющиеся подграфами графа
G и содержащие все его ребра и вершины
(3) деревья, являющиеся подграфами графа
G и содержащие все его вершины
(4) деревья, являющиеся подграфами графа
G и содержащие все его кратчайшие пути