Новая школа

Класс: 11
Тип вопросов: Соотнесение
Количество вопросов: 6

Соотнесите понятия и их определения:
- A) Вершинный граф
- B) Ребро графа
- C) Алгоритм Дейкстры
- D) Начальная вершина
1. Конкретная точка в графе, которая может вести к другим точкам.
2. Узел, который служит отправной точкой для поиска кратчайшего пути.
3. Связь между двумя вершинами графа.
4. Алгоритм для нахождения кратчайшего пути от одной вершины до всех остальных.

Соотнесите этапы работы алгоритма Дейкстры с их описанием:
- A) Инициализация
- B) Выбор текущей вершины
- C) Обновление расстояний
- D) Завершение алгоритма
1. Распределение начальных значений расстояний до всех вершин.
2. Выбор вершины с минимальным расстоянием для дальнейшего анализа.
3. Проверка всех соседей текущей вершины и обновление их расстояний, если найден более короткий путь.
4. Проверка, достигли ли мы конечной вершины, завершение работы алгоритма.

Соотнесите термины и их примеры:
- A) Взвешенный граф
- B) Невзвешенный граф
- C) Кратчайший путь
- D) Цикл в графе
1. Поездка между городами, где расстояния между ними указаны.
2. Прямое соединение двух точек без учёта расстояния.
3. Путь, длина которого минимальна между начальной и конечной вершиной.
4. Дорога, которая начинается и заканчивается в одной и той же точке.

Соотнесите алгоритмы и их характеристики:
- A) Алгоритм Дейкстры
- B) Алгоритм Форда-Беллмана
- C) Алгоритм A*
- D) Жадные алгоритмы
1. Использует жадный подход для нахождения кратчайшего пути.
2. Способен работать с графами, содержащими отрицательные веса.
3. Использует эвристические функции для улучшения производительности.
4. Ориентирован на графы с неотрицательными весами.

Соотнесите графики и их свойства:
- A) Ориентированный граф
- B) Ненаправленный граф
- C) Дерево
- D) Циклический граф
1. Все ребра имеют направление.
2. Содержит подмножество узлов, связанное и без циклов.
3. Ребра не имеют направления, взаимосвязь между узлами двусторонняя.
4. Содержит хотя бы один цикл.

Соотнесите типы данных и их использование:
- A) Очередь
- B) Стек
- C) Массив
- D) Список смежности
1. Хранение смежных вершин для реализуемого графа.
2. Используется на этапе добавления и удаления вершин.
3. Обеспечивает доступ к элементам по индексу.
4. Хранит элементы в порядке добавления (FIFO).

Этот тест помогает оценить знания учеников о алгоритме Дейкстры и связанных с ним концепциях в информатике.

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