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

Ниже представлен тест по информатике для 9 класса на тему: дерево перебора вариантов. Тип вопросов: единичный выбор. Всего 10 вопросов. В конце — ответы.

Инструкция: выберите один правильный ответ для каждого вопроса.

1. Что такое дерево перебора вариантов?

• A) Структура данных для хранения пар ключ-значение
• B) Графическая модель, где каждый узел представляет выбор варианта
• C) Алгоритм сортировки
• D) Набор процедур для работы с графами Правильный ответ: B

2. Как называется обход дерева, при котором сначала исследуются варианты на максимальной глубине, затем другие ветви?

• A) обход в ширину
• B) обход в глубину
• C) поиск по графу
• D) сортировка Правильный ответ: B

3. Что означает pruning (обрезка) в дереве перебора вариантов?

• A) Добавление новых узлов
• B) Удаление ветвей, которые не могут привести к решению
• C) Присваивание весов узлам
• D) Удаление узлов без подписей Правильный ответ: B

4. Что такое лист в дереве перебора вариантов?

• A) Узел с одним потомком
• B) Узел без потомков
• C) Корень дерева
• D) Узел с двумя потомками Правильный ответ: B

5. Что означает термин разветвление в дереве перебора вариантов?

• A) добавление нового уровня
• B) ветвление узла на несколько вариантов
• C) создание копий дерева
• D) завершение поиска Правильный ответ: B

6. Что означает метод "запоминания посещённых состояний" в дереве перебора вариантов?

• A) динамическое программирование
• B) запоминание посещённых состояний
• C) сортировка
• D) поиск по графу Правильный ответ: B

7. Какой показатель сложности характерен для полного перебора с разветвлением b на глубине d?

• A) O(n^2)
• B) O(b^d)
• C) O(log n)
• D) O(b+d) Правильный ответ: B

8. Какой обход чаще всего используют для генерации всех вариантов и печати их по мере обнаружения?

• A) DFS (обход в глубину)
• B) BFS (обход в ширину)
• C) обход по диагонали
• D) линейный поиск Правильный ответ: A

9. В чем отличие backtracking от полного перебора (exhaustive search)?

• A) Backtracking исследует только валидные варианты и может обрезать ветви
• B) Нет различий
• C) Backtracking всегда быстрее
• D) Backtracking применяется только к числам Правильный ответ: A

10. Сколько листьев будет у полного двоичного дерева высотой 3, если на каждом уровне узлы имеют по два варианта?

• A) 4
• B) 6
• C) 7
• D) 8 Правильный ответ: D

Ответы: 1 — B 2 — B 3 — B 4 — B 5 — B 6 — B 7 — B 8 — A 9 — A 10 — D