Сгенерируй тест для школьников с учетом следующих параметров: 1. Предмет: Информатика 2. Тема теста: Дерево. Перебор вариантов с помощью дерева. Графы 3. Класс учеников: 9 4. Типы…

Ниже тест для 9 класса по теме: Дерево. Перебор вариантов с помощью дерева. Графы. Тип: множественный выбор. Включены ответы.

1. Что такое дерево в теории графов? A) Связный граф без циклов.
   B) Связный граф с хотя бы одним циклом.
   C) Любой граф без рёбер.
   D) Несвязный граф без циклов.
   Правильный ответ: A

2. Какой признак является характерным для дерева с n вершинами? A) Связный граф без циклов имеет ровно n−1 рёбер.
   B) Граф всегда содержит больше рёбер, чем узлов.
   C) Граф может иметь циклы.
   D) В дереве обязательно есть более одного корня.
   Правильный ответ: A

3. Какой порядок обхода дерева соответствует обходу в глубину в префиксном виде? A) Корень, левое поддерево, правое поддерево.
   B) Левое поддерево, правое поддерево, корень.
   C) Корень, правое поддерево, левое поддерево.
   D) Правое поддерево, левое поддерево, корень.
   Правильный ответ: A

4. Что отличает граф от дерева? A) Граф может содержать циклы; дерево — нет циклов.
   B) Граф обязательно связный; дерево — может быть не связно.
   C) Дерево может иметь несколько корней; граф — никогда.
   D) Граф не имеет рёбер; дерево — имеет рёбра.
   Правильный ответ: A

5. Что такое остовное дерево графа? A) Подмножество рёбер, соединяющее все вершины без циклов.
   B) Любое дерево внутри графа.
   C) Подмножество рёбер, не соединяющее все вершины.
   D) Граф без рёбер.
   Правильный ответ: A

6. Какой характерен обход в ширину (BFS)? A) Посещение вершин слоями, начиная с корня.
   B) Посещение узлов по порядку “корень, левое поддерево, правое поддерево”.
   C) Посетить вершины в порядке их номеров.
   D) Обход только вдоль одной ветви.
   Правильный ответ: A

7. Какой метод перебора вариантов обычно реализуется с помощью дерева решений и возврата назад (backtracking)? A) Динамическое программирование
   B) Комбинаторный перебор (backtracking)
   C) Жадные алгоритмы
   D) Графовые алгоритмы для поиска кратчайшего пути
   Правильный ответ: B

8. Какой алгоритм обычно используют для поиска кратчайшего пути между двумя вершинами в неориентированном графе без весовых рёбер? A) Дейкстра
   B) Флойда–Уоршелла
   C) BFS
   D) Жадный обход
   Правильный ответ: C