Просто УрокТест · информатика
Графы: алгоритм Дейкстры
Отвечай кликом — после каждого вопроса пояснение. 10 вопросов, 4 варианта, 3–5 минут. Без таймеров и регистрации.
Отвечено 0 из 10 · Верно: 0
1/10
Для чего используется алгоритм Дейкстры?
Пояснение. Алгоритм Дейкстры находит кратчайшие расстояния от заданной начальной вершины. Он работает при неотрицательных весах рёбер.
2/10
Какие веса рёбер допустимы в классическом алгоритме Дейкстры?
Пояснение. Отрицательные веса могут нарушить корректность алгоритма. Поэтому классический вариант требует неотрицательных весов.
3/10
Что хранит массив dist в алгоритме Дейкстры?
Пояснение. В dist[v] хранится лучшее найденное на данный момент расстояние от старта до вершины v. В конце для достижимых вершин оно становится кратчайшим.
4/10
Какая структура данных обычно позволяет быстро выбирать непосещённую вершину с минимальным dist?
Пояснение. Приоритетная очередь или куча позволяет быстро извлекать вершину с наименьшим текущим расстоянием. Это ускоряет алгоритм Дейкстры.
5/10
Что означает «посетить» вершину в алгоритме Дейкстры?
Пояснение. Когда вершина выбрана как непосещённая с минимальным dist, её расстояние считается окончательным. После этого она помечается посещённой.
6/10
Если из текущей вершины u в соседнюю v идёт ребро веса w, какое обновление выполняется?
Пояснение. Проверяется, можно ли улучшить путь до v через u. Если новое расстояние меньше текущего dist[v], оно обновляется.
7/10
Можно ли алгоритмом Дейкстры корректно искать кратчайшие пути при отрицательных весах?
Пояснение. При отрицательных весах уже посещённая вершина может позже получить меньший путь. Поэтому классический алгоритм Дейкстры в таком случае не гарантирует правильный ответ.
8/10
Какова сложность алгоритма Дейкстры с бинарной кучей и списками смежности?
Пояснение. При использовании бинарной кучи и списков смежности сложность обычно равна O((V + E) log V). Здесь V — число вершин, E — число рёбер.
9/10
Какие начальные значения dist используются в алгоритме Дейкстры?
Пояснение. Расстояние от старта до самого себя равно 0. До остальных вершин расстояние пока неизвестно, поэтому считается бесконечным.
10/10
Если после завершения алгоритма dist[v] осталось бесконечным, что это значит?
Пояснение. Бесконечность означает, что из начальной вершины нельзя добраться до v. То есть вершина недостижима в данном графе.
Важно. Тесты носят информационно-образовательный характер и не являются публичной офертой (ст. 437 ГК РФ) или аттестацией. Возможны неточности — сверяйтесь с официальными источниками (ФИПИ, учебники). Заметили ошибку — напишите нам.