Новая Школа - онлайн-школа подготовки к ЕГЭ
Задача · 11 класс Задача №3829738
А
Аноним
7 часов назад · публичный вопрос
А
Аноним

Тест по предмету «Информатика» на тему «Графы. Поиск в ширину.»

Ответ нейросети
7 часов назад
  1. Сопоставьте понятия графа и их определения.

Группа A А1. Граф
А2. Смежные вершины
А3. Петля
А4. Маршрут

Группа B Б1. Конечная последовательность вершин, в которой каждые две соседние вершины соединены ребром
Б2. Две вершины, соединённые ребром
Б3. Множество вершин вместе с множеством соединяющих их рёбер
Б4. Ребро, начало и конец которого — одна и та же вершина

  1. Сопоставьте элементы поиска в ширину и их назначение.

Группа A А1. Очередь
А2. Операция постановки в очередь
А3. Операция извлечения из очереди
А4. Массив посещённых вершин

Группа B Б1. Показывает, была ли вершина уже обнаружена
Б2. Работает по принципу «первым пришёл — первым вышел»
Б3. Добавляет элемент в конец очереди
Б4. Берёт элемент из начала очереди

  1. Сопоставьте шаг алгоритма BFS и выполняемое действие.

Группа A А1. Запуск BFS из стартовой вершины
А2. Извлечение очередной вершины
А3. Просмотр соседей текущей вершины
А4. Окончание BFS

Группа B Б1. Остановиться, когда очередь опустеет
Б2. Пометить стартовую вершину посещённой и добавить её в очередь
Б3. Взять вершину из начала очереди и сделать её текущей
Б4. Непосещённого соседа пометить и добавить в очередь

  1. Сопоставьте способ представления графа или его вид и описание.

Группа A А1. Матрица смежности
А2. Список смежности
А3. Ориентированный граф
А4. Взвешенный граф

Группа B Б1. Каждому ребру сопоставлено числовое значение
Б2. Для каждой вершины хранится перечень соседних вершин
Б3. Рёбра имеют направление
Б4. Таблица N×N, в которой элемент показывает наличие ребра между вершинами

  1. Сопоставьте утверждение о поиске в ширину и его пояснение.

Группа A А1. BFS в невзвешенном графе находит
А2. Для хранения вершин, ожидающих обработки, BFS использует
А3. Если после BFS из стартовой вершины есть непосещённые вершины, то
А4. Вершины в BFS обрабатываются

Группа B Б1. очередь
Б2. кратчайший путь от стартовой вершины по числу рёбер
Б3. в порядке возрастания расстояния от стартовой вершины
Б4. они недостижимы из стартовой вершины

Ответы

  1. А1 — Б3; А2 — Б2; А3 — Б4; А4 — Б1.
  2. А1 — Б2; А2 — Б3; А3 — Б4; А4 — Б1.
  3. А1 — Б2; А2 — Б3; А3 — Б4; А4 — Б1.
  4. А1 — Б4; А2 — Б2; А3 — Б3; А4 — Б1.
  5. А1 — Б2; А2 — Б1; А3 — Б4; А4 — Б3.