Новая Школа - онлайн-школа подготовки к ЕГЭ
При поддержке
Посмотреть все тесты нейросети

Тест на тему Алгоритм Дейкстра

09 декабря 2025 16:17

{Другой предмет}
11 Класс

Этот тест сгенерирован искусственным интеллектом. Возможны ошибки.

Сгенерировать свой тест

Ниже представлен тест по теме: Алгоритм Дейкстры. Уровень: 11 класс. Тип вопросов: Единственный выбор. Всего вопросов: 14. Тест с ответами.

  1. Что такое алгоритм Дейкстры? A) Поиск кратчайшего пути между всеми парами вершин
    B) Поиск кратчайшего пути от одной вершины ко всем остальным в графе с неотрицательными весами ребер
    C) Поиск максимального пути в графе
    D) Поиск цикла отрицательного веса
    Ответ: B

  2. Каковы допустимые веса ребер для корректной работы алгоритма Дейкстры? A) Только положительные
    B) Только отрицательные
    C) Неотрицательные (≥ 0)
    D) Любые веса
    Ответ: C

  3. Какой основной шаг алгоритма Дейкстры? A) Удаление ребра с максимальным весом
    B) Выбор вершины с минимальной кратчайшей дистанцией среди непомеченных вершин
    C) Обновление всех расстояний до всех вершин
    D) Поиск цикла в графе
    Ответ: B

  4. Какова временная сложность алгоритма Дейкстры при использовании двоичной кучи? A) O(V^2)
    B) O(E log V)
    C) O((V+E) log V)
    D) O(E log E)
    Ответ: C

  5. Чем отличается алгоритм Дейкстры от алгоритма Беллмана-Форда? A) Дейкстра не работает с отрицательными весами; Беллман-Форда работает с ними
    B) Беллман-Форда быстрее на больших графах
    C) Дейкстра на графах без отрицательных весов находит кратчайшие пути, Беллман-Форда может работать с любыми весами
    D) Нет различий
    Ответ: C

  6. Что возвращает алгоритм Дейкстры? A) Только кратчайшие расстояния от исходной вершины до остальных
    B) Только маршрут кратчайшего пути
    C) Как и расстояния, он возвращает сами кратчайшие пути (предшественники) и расстояния
    D) Ничего
    Ответ: C

  7. Какой структурой данных чаще всего используются для реализации очереди вершин в Дейкстре? A) Стек
    B) Очередь без приоритета
    C) Очередь с приоритетами (например, бинарная куча)
    D) Хэш-таблица
    Ответ: C

  8. Какой шаг повторяется до тех пор, пока не будут обработаны все вершины? A) Выбор неиспользованной вершины с минимской дистанцией
    B) Добавление нового ребра
    C) Перестановка вершин графа
    D) Удаление самой длинной вершины
    Ответ: A

  9. Пример: в неориентированном графе веса такие: A-B = 1, A-C = 4, B-C = 2, B-D = 5, C-D = 1. Какое кратчайшее расстояние от A до D? A) 3
    B) 4
    C) 5
    D) 6
    Ответ: B

  10. Что произойдет, если в графе есть ребро с весом 0? A) Алгоритм станет неверным
    B) Алгоритм корректен; нулевые веса допускаются
    C) Нужно использовать Беллмана-Форда
    D) Вершины с нулевым весом исключаются
    Ответ: B

  11. Что означает пометка вершины как обработанной в ходе работы Дейкстры? A) Ее расстояние уже окончательно определено и больше не обновляется
    B) Нужно перезапустить алгоритм
    C) Вершина больше не соединена ребрами
    D) Вершина удалена из графа
    Ответ: A

  12. Что произойдет, если в графе присутствуют отрицательные веса ребер? A) Работа алгоритма Дейкстры может дать неверные результаты
    B) Алгоритм работает нормально
    C) Ничего плохого
    D) Граф становится не связным
    Ответ: A

  13. Какое преимущество использования очереди с приоритетами? A) Уменьшение объема памяти
    B) Сокращение времени работы по сравнению с перебором всех вершин
    C) Обезличивание вершин
    D) Ускорение перестановки графа
    Ответ: B

  14. Каковы типичные асимптотические оценки времени работы алгоритма Дейкстры с использованием кучи Фибоначчи? A) O(V^2)
    B) O(E log V)
    C) O(V log V + E)
    D) O(E^2)
    Ответ: C

Если нужно, могу адаптировать тест под конкретные задания или добавить пояснения к ответам.


Сгенерировать свой тест

Популярные тесты

{Другой предмет}
5 Класс
{Другой предмет}
8 Класс
{Другой предмет}
7 Класс
{Другой предмет}
7 Класс

Саша — ассистент в телеграмме