Индивидуальный рабочий лист
Информатика · 11 класс
Тема: Алгоритм поиска в ширину (BFS)
Педагог: ____________________ Школа: ____________________
ФИ ученика: Дата: Класс: 11
Инструкция для ученика: Перед тобой 5 заданий по теме «Алгоритм поиска в ширину (BFS)». Внимательно читай каждое задание. Ответы записывай в отведённые поля (схемы, код, пояснения). Соблюдай порядок выполнения. Максимум за работу — 10 баллов. Удачи!
1 Теоретическая разминка (1 балл)
Выбери одно верное утверждение о работе очереди (queue) в алгоритме BFS. Обведи букву правильного ответа.
- А. Очередь работает по принципу LIFO (последним пришёл — первым вышел).
- Б. Очередь работает по принципу FIFO (первым пришёл — первым вышел).
- В. Очередь в BFS не используется, вместо неё применяют стек.
- Г. Очередь хранит только непосещённые вершины, но порядок извлечения не важен.
Запиши букву ответа: ______
2 Пошаговый обход графа (2 балла)
Дан невзвешенный граф, заданный списком смежности:
0: [1, 2]
1: [0, 3, 4]
2: [0, 5]
3: [1]
4: [1]
5: [2]
Стартовая вершина: 0.
Запиши порядок обхода вершин при выполнении BFS (очередь). Если на одном шаге в очередь попадает несколько соседей, добавляй их в порядке возрастания номеров.
Порядок обхода (через запятую, начиная с 0):
_____________________________________________
💡 Ценность «Трудолюбие и профессионализм»: проверь свой порядок дважды — точность в деталях отличает профессионала.
3 Заполни пропуски в коде BFS (2 балла)
Ниже приведён фрагмент реализации BFS на Python. Вставь пропущенные элементы вместо многоточий (…).