Тест: Поиск кратчайшего пути
Предмет: Информатика
Класс: 11
Цели обучения: 11.2.2.3 применять алгоритмы обхода графов для нахождения кратчайшего пути в прикладных задачах (маршрутизация, логистика)
Вопросов: 10
Время: 20 мин
Вопрос 1
Какова основная цель алгоритма Дейкстры?
Выберите один ответ.
A) Нахождение кратчайшего пути от начальной вершины до всех остальных в графе с неотрицательными весами
B) Поиск всех возможных путей между двумя вершинами
C) Обход графа в глубину для проверки связности
D) Сортировка вершин графа по весам рёбер
Вопрос 2
На уроке рассматривался граф: A→B (5 км), A→C (10 км), B→C (2 км), B→D (7 км), C→D (3 км). Каков кратчайший путь от A до D?
Выберите один ответ.
A) A→B→C→D, длина 10 км
B) A→C→D, длина 13 км
C) A→B→D, длина 12 км
D) A→B→C→D, длина 14 км
Вопрос 3
Какое начальное расстояние присваивается стартовой вершине в алгоритме Дейкстры?
Выберите один ответ.
A) 0
B) Бесконечность (∞)
C) 1
D) Минимальный вес ребра в графе