Тест по информатике на тему "Алгоритм Прима и Крускала"

Класс: 11

Инструкция: Выберите один правильный вариант ответа из предложенных.

---

Вопрос 1: Какова основная цель алгоритмов Прима и Крускала?

• A) Нахождение всех кратчайших путей в графе
• B) Нахождение минимального остовного дерева для неориентированного графа
• C) Нахождение максимального потока в сети
• D) Сортировка массива

Правильный ответ: B

---

Вопрос 2: Какой из следующих графов может быть использован для алгоритма Прима?

• A) Ориентированный граф
• B) Неориентированный граф с положительными весами
• C) Дерево
• D) Граф с отрицательными весами

Правильный ответ: B

---

Вопрос 3: Какой из следующих шагов является первым этапом алгоритма Крускала?

• A) Выбор произвольной вершины
• B) Сортировка всех рёбер по весу
• C) Создание пустого остовного дерева
• D) Поиск кратчайшего пути

Правильный ответ: B

---

Вопрос 4: Какой принцип лежит в основе алгоритма Прима?

• A) "Жадный" подход
• B) Динамическое программирование
• C) Разделяй и властвуй
• D) Обратная пропорциональность

Правильный ответ: A

---

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

• A) Алгоритм Прима
• B) Алгоритм Дейкстры
• C) Алгоритм Крускала
• D) Алгоритм Флойда-Уоршелла

Правильный ответ: C

---

Вопрос 6: Какой параметр не является характерным для алгоритма Прима?

• A) Работа с рёбрами графа
• B) Постепенное добавление рёбер
• C) Постепенное добавление вершин
• D) Сортировка рёбер по весу

Правильный ответ: D

---

Вопрос 7: Алгоритм Крускала работает с:

• A) Полным графом
• B) Все рёбра графа должны быть отсортированы
• C) Нужно использовать структуру "дерево"
• D) Все перечисленные варианты

Правильный ответ: D

---

Вопрос 8: Какой результат дает алгоритм Прима?

• A) Остовное дерево
• B) Минимальный остовной лес
• C) Кратчайший путь
• D) Полный граф

Правильный ответ: A

---

Вопрос 9: Какой алгоритм использует жадный подход и на каждом шаге выбирает минимум?

• A) Алгоритм Дейкстры
• B) Алгоритм Крускала
• C) Алгоритм Прима
• D) Алгоритм Флойда

Правильный ответ: C

---

Вопрос 10: Какой из алгоритмов предпочтительнее использовать для разреженных графов?

• A) Алгоритм Прима
• B) Алгоритм Крускала
• C) Алгоритм Флойда
• D) Алгоритм Беллмана-Форда

Правильный ответ: B

---

Итог

Этот тест помогает проверить знания учащихся по алгоритмам Прима и Крускала, а также их понимание ключевых концепций в теории графов.