1.
|
В каких целях используются графы в сети компьютеров?
|
A.
|
для проверка связности
|
Б.
|
для планирования
|
С.
|
работоспособности
|
Д.
|
быстродействия
|
2.
|
Какую задачу решает обобщенный графовый поиск ?
|
A.
|
поиск ребер
|
Б.
|
поиск в графе
|
С.
|
поиск вершин
|
Д.
|
поиск связей
|
3.
|
Какие две стратегии существует в графовом поиске?
|
A.
|
поиск в ширину и поиск в длину
|
Б.
|
поиск в ширину и поиск в связность
|
С.
|
поиск в длину и поиск в связность
|
Д.
|
поиск в ширину и поиск в глубину
|
4.
|
Алгоритм поиска в глубину позволяет построить обход ориентированного или неориентированного графа, при котором посещаются ……, доступные из начальной вершины
|
A.
|
соседние вершины
|
Б.
|
не все вершины
|
С.
|
все вершины
|
Д.
|
связные вершины
|
5.
|
В чём отличие поиска в глубину от поиска в ширину?
|
A.
|
проверить последовательно все вершины графа
|
Б.
|
обход последовательно все вершины графа
|
С.
|
найти последовательно все вершины графа
|
Д.
|
связать последовательно все вершины графа
|
6.
|
Поиск в глубину не находит …..
|
A.
|
кратчайших путей
|
Б.
|
максимальных путей
|
С.
|
циклических путей
|
Д.
|
параллельных путей
|
7.
|
Если же граф ориентированный, то поиск в глубину строит….. из начальной вершины во все доступные из нее.
|
A.
|
направление путей
|
Б.
|
параллельных путей
|
С.
|
циклических путей
|
Д.
|
дерево путей
|
8.
|
Граф называется …. - если его вершины можно разбить на два множества так, что концы каждого ребра принадлежат разным множествам
|
A.
|
ориентированным
|
Б.
|
неориентированным
|
С.
|
двудольным
|
Д.
|
смешанным
|
9.
|
Алгоритм DFS это -
|
A.
|
алгоритм поиска в ширину
|
Б.
|
алгоритм поиска в глубину
|
С.
|
алгоритм поиска кратчайших путей
|
Д.
|
алгоритм поиска цикла в графе
|
10.
|
Как называется ребро, при удалении которого граф распадается на две компоненты связности?
|
A.
|
мостом
|
Б.
|
направленные
|
С.
|
ненаправленные
|
Д.
|
листьем
|
11.
|
Какую сложность имеет алгоритм поиска в глубину, который позволяет найти все мосты в связном графе за один DFS?
|
A.
|
O(2n)
|
Б.
|
O(n)
|
С.
|
O(n2)
|
Д.
|
O(logn)
|
12.
|
Какую задачу решает алгоритм поиска в ширину ?
|
A.
|
поиск максимальных путей
|
Б.
|
поиск циклических путей
|
С.
|
поиск кратчайщего пути
|
Д.
|
поиск параллельных путей
|
13.
|
Алгоритм BFS это -
|
A.
|
алгоритм поиска в ширину
|
Б.
|
алгоритм поиска в глубину
|
С.
|
алгоритм поиска кратчайших путей
|
Д.
|
алгоритм поиска цикла в графе
|
14.
|
Если в графе содержится n вершин и m ребер, то сложность алгоритма поиска в ширину равна
|
A.
|
O(n+m)
|
Б.
|
O(n2)
|
С.
|
O(n)
|
Д.
|
O(n*m)
|
15.
|
Если граф хранится при помощи матрицы смежности, то сложность алгоритма поиска в ширину равна
|
A.
|
O(n+m)
|
Б.
|
O(n2)
|
С.
|
O(n)
|
Д.
|
O(n*m)
|
16.
|
Остовным деревом графа называется дерево, которое можно получить из него путём ...
|
A.
|
добавления некоторых рёбер
|
Б.
|
соединения некоторых рёбер
|
С.
|
удаления некоторых мостов
|
Д.
|
удаления некоторых рёбер
|
17.
|
Для нахождения минимального остовного дерева графа существуют два основных алгоритма:
|
A.
|
алгоритм Прима и алгоритм Крускаля
|
Б.
|
алгоритм Прима и алгоритм Дейкстры
|
С.
|
алгоритм Дейкстры и алгоритм Крускаля
|
Д.
|
Нет правильного ответа
|
18.
|
Как называется граф, у которого для любых двух различных вершин существует путь (последовательность смежных вершин), соединяющий их.
|
A.
|
не связный граф
|
Б.
|
связный граф
|
С.
|
ориентированный
|
Д.
|
неориентированный
|
19.
|
Как называется эффективный алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа?
|
A.
|
Алгоритм Крускаля
|
Б.
|
Алгоритм Прима
|
С.
|
алгоритм Дейкстры
|
Д.
|
Нет правильного ответа
|
20.
|
Какой алгоритм предназначен для нахождения кратчайшего пути?
|
A.
|
Алгоритм Крускаля
|
Б.
|
Алгоритм Прима
|
С.
|
алгоритм Дейкстры
|
Д.
|
Нет правильного ответа
|
