Новая Школа - онлайн-школа подготовки к ЕГЭ
При поддержке
Посмотреть все тесты нейросети

Тест на тему графы. Решение алгоритмических задач, связанных с анализом графов

10 ноября 2025 07:18

{Другой предмет}
11 Класс

Этот тест сгенерирован искусственным интеллектом. Возможны ошибки.

Сгенерировать свой тест

Ниже тест по теме: графы. Решение алгоритмических задач, связанных с анализом графов. Тип вопросов: единственный выбор. Количество вопросов: 10. Ответы приведены в конце с краткими пояснениями.

  1. Что такое граф в теории графов?
  • A) Множество вершин и ребер
  • B) Множество вершин, без ребер
  • C) Множество ребер, без вершин
  • D) Граф - это дерево Ответ: A Пояснение: граф G определяется как парa вершин V и ребер E, то есть G = (V, E).
  1. Чем отличается ориентированный граф от неориентированного?
  • A) Наличие направления у ребер
  • B) Количество вершин
  • C) Наличие весов
  • D) Наличие циклов Ответ: A Пояснение: в ориентированном графе каждое ребро имеет направление (u → v), в неориентированном — ребро не имеет направления.
  1. Какой алгоритм чаще всего используют для поиска компонент связности в неориентированном графе?
  • A) Дейкстра
  • B) Поиск в глубину
  • C) Флойд
  • D) Беллман-Форда Ответ: B Пояснение: DFS (или BFS) применяется для поиска компонент связности; каждая новая непройденная вершина начинается новый обход.
  1. Какой алгоритм обхода графа посещает вершины слоями?
  • A) DFS
  • B) BFS
  • C) Дейкстра
  • D) Прима Ответ: B Пояснение: BFS (поиск в ширину) исследует граф по уровням, начиная от заданной вершины.
  1. Какой алгоритм найдёт кратчайший путь между двумя вершинами в графе с неотрицательными весами?
  • A) Дейкстра
  • B) Беллман-Форда
  • C) Флойда
  • D) Краскала Ответ: A Пояснение: алгоритм Дейкстры алгоритмически корректен для графа с неотрицательными весами ребер и находит кратчайшие расстояния от одной вершины до всех остальных.
  1. Сложность обхода всех вершин и рёбер графа за один проход?
  • A) O(N^2)
  • B) O(N+M)
  • C) O(N^3)
  • D) O(M^2) Ответ: B Пояснение: для DFS/BFS сложность составляет O(N + M), где N — число вершин, M — число ребер.
  1. Что такое минимальное остовное дерево (MST)?
  • A) Подграф, содержащий все вершины графа и ребра минимального суммарного веса, образующий дерево
  • B) Подграф без вершин
  • C) Граф, в котором все вершины имеют минимальный вес
  • D) Дерево на половине вершин Ответ: A Пояснение: MST — это подграф, содержащий все вершины и минимальную суммарную весовую характеристику ребер, образующий связное дерево.
  1. Какой алгоритм строит минимальное остовное дерево?
  • A) Дейкстра
  • B) Флойд
  • C) Прима
  • D) Беллман-Форда Ответ: C Пояснение: Прима (и Краскала) — стандартные алгоритмы для построения MST; здесь выбран Прима как правильный ответ.
  1. Какой алгоритм подходит для проверки наличия цикла в графе?
  • A) Поиск в глубину
  • B) Поиск в ширину
  • C) Дейкстра
  • D) Беллман-Форда Ответ: A Пояснение: DFS может использоваться для обнаружения циклов в графах; в неориентированном графе цикл обнаруживается по соседу-неотцу.
  1. Что означает топологическая сортировка в DAG (ориентированном ациклическом графе)?
  • A) Линейный порядок вершин, удовлетворяющий условию: для каждого ребра u → v вершина u стоит перед v
  • B) Сортировка вершин по возрастанию их индексов
  • C) Поиск цикла
  • D) Сортировка вершин по весу Ответ: A Пояснение: топологическая сортировка даёт линейный порядок вершин, в котором все ориентированные ребра направлены из более ранних вершин в более поздние.

Если хотите, могу переделать тест под конкретный формат (например, с нумерацией задач в стиле экзамена, добавить задачи‑практику на сравнение алгоритмов или задания на вычисление конкретных значений).


Сгенерировать свой тест

Популярные тесты

{Другой предмет}
9 Класс
{Другой предмет}
11 Класс
{Другой предмет}
8 Класс
{Другой предмет}
9 Класс

Саша — ассистент в телеграмме