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

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

Ответ нейросети
7 часов назад
  1. Какая структура данных лежит в основе алгоритма поиска в ширину (BFS)?

A) стек B) очередь C) двоичная куча D) хеш-таблица

  1. Что гарантированно находит поиск в ширину в невзвешенном графе при запуске из стартовой вершины s?

A) кратчайшие пути от s до всех достижимых вершин по числу рёбер B) путь с минимальной суммой весов рёбер C) все простые циклы графа D) гамильтонов цикл наименьшей длины

  1. Дан неориентированный граф с вершинами 1–6 и рёбрами: 1–2, 1–3, 2–4, 3–5, 4–5, 5–6. Поиск в ширину запущен из вершины 1. Чему равно кратчайшее расстояние (в числе рёбер) от вершины 1 до вершины 6?

A) 2 B) 3 C) 4 D) 5

  1. Какова временная сложность BFS при хранении графа в виде списков смежности? (V — число вершин, E — число рёбер)

A) O(V²) B) O(E log V) C) O(V + E) D) O(2^V)

  1. Пусть BFS запущен из вершины s, а d(v) — число рёбер в кратчайшем пути из s в v. Какое утверждение верно для любого ребра (u, v) неориентированного графа?

A) |d(u) − d(v)| ≤ 1 B) d(u) = d(v) для любого ребра C) |d(u) − d(v)| может быть сколь угодно большим D) d(u) + d(v) всегда чётно

Ответы

  1. B — BFS использует очередь (FIFO).
  2. A — в невзвешенном графе BFS даёт кратчайшие пути по числу рёбер.
  3. B — путь 1–3–5–6 содержит 3 ребра.
  4. C — каждая вершина и каждое ребро просматриваются ограниченное число раз: O(V + E).
  5. A — при обходе в ширину концы любого ребра лежат на одном уровне или на соседних.