Сгенерируй тест для школьников с учетом следующих параметров: 1. Предмет: Информатика 2. Тема теста: Построение минимального остовного дерева взвешенного связного…

Вот тест для школьников по теме "Построение минимального остовного дерева взвешенного связного неориентированного графа, алгоритмы Прима и Краскала".

Тест по информатике для 11 класса

Тема: Построение минимального остовного дерева. Алгоритмы Прима и Краскала.

Вопрос 1:

Какой из следующих алгоритмов используется для построения минимального остовного дерева (МОД) в графе?

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

Правильный ответ: B) Алгоритм Краскала

Вопрос 2:

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

A) Сортировка всех ребер графа по весу
B) Выбор ребер с минимальным весом, соединяющих уже построенное дерево с новыми вершинами
C) Поиск кратчайших путей от одной вершины ко всем остальным
D) Разделение графа на минимальные компоненты

Правильный ответ: B) Выбор ребер с минимальным весом, соединяющих уже построенное дерево с новыми вершинами

Вопрос 3:

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

A) Он всегда работает быстрее, чем алгоритм Прима.
B) Он основан на жадном подходе и работает с рёбрами.
C) Он требует, чтобы граф был ориентированным.
D) Он использует приоритетную очередь для выбора рёбер.

Правильный ответ: B) Он основан на жадном подходе и работает с рёбрами.

Вопрос 4:

Каковы основные компоненты алгоритма Прима?

A) Граф, множество рёбер и графовые матрицы.
B) Множество вершин, список рёбер и общая стоимость.
C) Множество вершин, множество рёбер и множество включённых вершин.
D) Линейный список рёбер и массив вершин.

Правильный ответ: C) Множество вершин, множество рёбер и множество включённых вершин.

Вопрос 5:

Какой временной Complexity у алгоритма Краскала при использовании объединения и поиска (Union-Find)?

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

Правильный ответ: B) O(E log E)

Вопрос 6:

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

A) Метод Флойда
B) Метод сжатия путей
C) Метод поиска и объединения
D) Метод предшествующих вершин

Правильный ответ: C) Метод поиска и объединения

Тест можно использовать для проверки знаний учеников по теме "Минимальные остовные деревья". Удачи в подготовке!