Сгенерируй тест для школьников с учетом следующих параметров: 1. Предмет: Информатика 2. Тема теста: графы. Решение алгоритмических задач, связанных с анализом графов 3. Класс учеников: 11 4. Типы вопросов в тесте: Единственный выбор 5. Количество вопросов: 10 6. Выводить ли тест с ответами: Да

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