- Сопоставьте понятия графа и их определения.
Группа A
А1. Граф
А2. Смежные вершины
А3. Петля
А4. Маршрут
Группа B
Б1. Конечная последовательность вершин, в которой каждые две соседние вершины соединены ребром
Б2. Две вершины, соединённые ребром
Б3. Множество вершин вместе с множеством соединяющих их рёбер
Б4. Ребро, начало и конец которого — одна и та же вершина
- Сопоставьте элементы поиска в ширину и их назначение.
Группа A
А1. Очередь
А2. Операция постановки в очередь
А3. Операция извлечения из очереди
А4. Массив посещённых вершин
Группа B
Б1. Показывает, была ли вершина уже обнаружена
Б2. Работает по принципу «первым пришёл — первым вышел»
Б3. Добавляет элемент в конец очереди
Б4. Берёт элемент из начала очереди
- Сопоставьте шаг алгоритма BFS и выполняемое действие.
Группа A
А1. Запуск BFS из стартовой вершины
А2. Извлечение очередной вершины
А3. Просмотр соседей текущей вершины
А4. Окончание BFS
Группа B
Б1. Остановиться, когда очередь опустеет
Б2. Пометить стартовую вершину посещённой и добавить её в очередь
Б3. Взять вершину из начала очереди и сделать её текущей
Б4. Непосещённого соседа пометить и добавить в очередь
- Сопоставьте способ представления графа или его вид и описание.
Группа A
А1. Матрица смежности
А2. Список смежности
А3. Ориентированный граф
А4. Взвешенный граф
Группа B
Б1. Каждому ребру сопоставлено числовое значение
Б2. Для каждой вершины хранится перечень соседних вершин
Б3. Рёбра имеют направление
Б4. Таблица N×N, в которой элемент показывает наличие ребра между вершинами
- Сопоставьте утверждение о поиске в ширину и его пояснение.
Группа A
А1. BFS в невзвешенном графе находит
А2. Для хранения вершин, ожидающих обработки, BFS использует
А3. Если после BFS из стартовой вершины есть непосещённые вершины, то
А4. Вершины в BFS обрабатываются
Группа B
Б1. очередь
Б2. кратчайший путь от стартовой вершины по числу рёбер
Б3. в порядке возрастания расстояния от стартовой вершины
Б4. они недостижимы из стартовой вершины
Ответы
- А1 — Б3; А2 — Б2; А3 — Б4; А4 — Б1.
- А1 — Б2; А2 — Б3; А3 — Б4; А4 — Б1.
- А1 — Б2; А2 — Б3; А3 — Б4; А4 — Б1.
- А1 — Б4; А2 — Б2; А3 — Б3; А4 — Б1.
- А1 — Б2; А2 — Б1; А3 — Б4; А4 — Б3.