Просто УрокТест · Информатика
Графы: кратчайший путь
Отвечай кликом — после каждого вопроса пояснение. 10 вопросов, 4 варианта, 3–5 минут. Без таймеров и регистрации.
Отвечено 0 из 10 · Верно: 0
1/10
Что называют кратчайшим путём между двумя вершинами взвешенного графа?
Пояснение. Во взвешенном графе важна сумма весов рёбер, поэтому кратчайший путь имеет минимальную суммарную длину или стоимость.
2/10
Какой алгоритм обычно применяют для поиска кратчайших путей от одной вершины во взвешенном графе без отрицательных рёбер?
Пояснение. Алгоритм Дейкстры предназначен для поиска кратчайших путей во взвешенном графе при неотрицательных весах рёбер.
3/10
В невзвешенном графе для поиска кратчайшего пути по числу рёбер удобно использовать...
Пояснение. Поиск в ширину обходит вершины слоями и в невзвешенном графе находит путь с наименьшим числом рёбер.
4/10
Что означает вес ребра в графе дорог?
Пояснение. В графе дорог вес ребра обычно показывает расстояние, время или стоимость перехода между вершинами.
5/10
В графе A-B вес 2, B-C вес 3, A-C вес 10. Чему равна длина кратчайшего пути из A в C?
Пояснение. Путь A-B-C имеет длину 2+3=5, что меньше прямого ребра A-C с весом 10.
6/10
На каком шаге алгоритма Дейкстры выбирается вершина с наименьшей текущей меткой?
Пояснение. Алгоритм Дейкстры на каждом шаге выбирает необработанную вершину с наименьшим текущим расстоянием.
7/10
Почему алгоритм Дейкстры может давать неверный результат при отрицательных весах рёбер?
Пояснение. При отрицательных весах более короткий путь может быть найден позже, а Дейкстра считает выбранную вершину окончательно обработанной.
8/10
Путь в графе — это...
Пояснение. Путь задаётся последовательностью вершин, где каждые соседние вершины соединены ребром.
9/10
Если в графе все рёбра имеют одинаковый вес, то кратчайший путь совпадает с путём...
Пояснение. При одинаковых весах рёбер минимальная сумма весов достигается на пути с наименьшим числом рёбер.
10/10
Как в таблице расстояний алгоритма Дейкстры отмечают, что вершина ещё не достигнута?
Пояснение. Недостигнутые вершины обычно имеют метку, равную бесконечности, пока не найден путь до них.
Важно. Тесты носят информационно-образовательный характер и не являются публичной офертой (ст. 437 ГК РФ) или аттестацией. Возможны неточности — сверяйтесь с официальными источниками (ФИПИ, учебники). Заметили ошибку — напишите нам.