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

Тест по информатике: Алгоритм Дейкстры

Класс: 11
Тема: Алгоритм Дейкстры
Тип вопросов: Множественный выбор
Количество вопросов: 10

---

Вопрос 1:

Что находит алгоритм Дейкстры?

A) Минимальную стоимость пути от одной вершины до всех остальных
B) Максимальную стоимость пути от одной вершины до всех остальных
C) Все возможные пути между вершинами
D) Самый короткий путь между двумя заданными вершинами

Ответ: A

---

Вопрос 2:

Какое из следующих условий необходимо для применения алгоритма Дейкстры?

A) Граф должен быть ориентированным
B) В графе могут быть отрицательные веса ребер
C) Граф должен быть неориентированным
D) В графе все веса ребер должны быть неотрицательными

Ответ: D

---

Вопрос 3:

Какой основной шаг делает алгоритм Дейкстры на каждой итерации?

A) Добавляет новую вершину в дерево решений
B) Убирает вершину с минимальным расстоянием из кучи
C) Изменяет веса ребер
D) Проверяет наличие циклов в графе

Ответ: B

---

Вопрос 4:

Какой тип структуры данных обычно используется для реализации алгоритма Дейкстры?

A) Массив
B) Стек
C) Очередь с приоритетом
D) Связный список

Ответ: C

---

Вопрос 5:

Что происходит, когда алгоритм Дейкстры достигает вершины, у которой нет выходящих ребер?

A) Алгоритм завершает работу
B) Вершина игнорируется
C) Алгоритм продолжает работу с оставшимися вершинами
D) Вычисляются все возможные пути из этой вершины

Ответ: C

---

Вопрос 6:

Каково время работы алгоритма Дейкстры с использованием очереди с приоритетом на основе бинарной кучи?

A) O(V^2)
B) O(E + V log V)
C) O(V log V)
D) O(E log V)

Ответ: D

---

Вопрос 7:

Как визуализируется выполнение алгоритма Дейкстры?

A) Только в текстовом формате
B) С использованием графиков, показывающих пути
C) С использованием таблиц, которые показывают расстояния
D) Обе B и C

Ответ: D

---

Вопрос 8:

Кто является автором алгоритма Дейкстры?

A) Эдсгер Дейкстра
B) Дональд Кнут
C) Кристофер Л. Беннетт
D) Р. Тайлор

Ответ: A

---

Вопрос 9:

В каком случае алгоритм Дейкстры не сможет найти оптимальный путь?

A) Если в графе есть циклы
B) Если в графе есть отрицательные веса ребер
C) Если граф неполный
D) Если граф ориентированный

Ответ: B

---

Вопрос 10:

Как можно улучшить алгоритм Дейкстры в случае работы с большими графами?

A) Использовать линеаризацию
B) Использовать более сложные структуры данных, такие как фибоначчиева куча
C) Упрощать граф
D) Использовать жадный подход

Ответ: B

---

Тест завершен. Поздравляем с его прохождением! Удачи на экзаменах!