Тест на тему Граф. Весовая матрица графа. Длина пути между вершинами графа. Вычисление количества путей в направленном ациклическом графе

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

Тема: Граф. Весовая матрица графа. Длина пути между вершинами графа. Вычисление количества путей в направленном ациклическом графе.

Вопросы

1. Что такое граф в информатике?

   • A) Структура данных, состоящая из узлов и связей между ними
   • B) Алгоритм сортировки
   • C) Формат изображения
   • D) Язык программирования
   • Правильный ответ: A

2. В каком из приведенных вариантов граф является направленным?

   • A) Граф с парными ребрами
   • B) Граф, в котором каждое ребро имеет направление
   • C) Граф, в котором все вершины равнозначны
   • D) Граф без вершин
   • Правильный ответ: B

3. Что обозначает весовая матрица графа?

   • A) Матрицу смежности
   • B) Матрицу, в которой указываются веса (стоимости) рёбер
   • C) Линейное уравнение
   • D) Граф без рёбер
   • Правильный ответ: B

4. Какую информацию можно получить из матрицы смежности?

   • A) Информацию о весах рёбер
   • B) Информацию о связи между вершинами
   • C) Обе вышеупомянутые
   • D) Никакой информации
   • Правильный ответ: C

5. Если весовое значение рёбер равно нулю, что это означает?

   • A) Ребро отсутствует
   • B) Ребро соединяет вершины, но не имеет веса
   • C) Ребро имеет минимальный вес
   • D) Ребро соединяет вершины по умолчанию
   • Правильный ответ: A

6. Как вычислить длину пути между двумя вершинами в графе?

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

7. Какое из следующих утверждений верно для направленного ациклического графа (DAG)?

   • A) В графе присутствируют циклы
   • B) Граф не имеет направленных рёбер
   • C) У него нет направленных циклов
   • D) Все рёбра не имеют веса
   • Правильный ответ: C

8. Какой алгоритм чаще всего используется для нахождения всех путей в графе?

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

9. Какое количество путей между двумя вершинами может существовать в DAG?

   • A) Ведущих в циклы
   • B) Только один
   • C) Неограниченное количество
   • D) Равно нулю, если нет рёбер
   • Правильный ответ: C

10. Как легко можно представить весовую матрицу графа?

    • A) Как таблицу, где строки и столбцы - вершины графа, а элементы - веса рёбер
    • B) В виде списка
    • C) В виде формул
    • D) В виде дерева
    • Правильный ответ: A

11. В каком случае количество путей между двумя вершинами графа увеличится?

    • A) Когда добавляется новое ребро
    • B) Когда удаляется одно из рёбер
    • C) Когда граф становится направленным
    • D) Когда граф становится несвязным
    • Правильный ответ: A

12. Какое свойство не характеризует ациклический граф?

    • A) Наличие направленных рёбер
    • B) Отсутствие циклов
    • C) Присутствие веса рёбер
    • D) Наличие циклов
    • Правильный ответ: D

13. Что происходит, если в графе удалить одно из рёбер?

    • A) Всегда увеличивается количество путей
    • B) Всегда уменьшается количество путей
    • C) Количество путей может изменяться произвольно
    • D) Количество путей не изменяется
    • Правильный ответ: C

14. Как граничным значением для веса рёбер будет значение, равное −1?

    • A) Это означает, что ребро отсутствует
    • B) Это может означать отрицательные циклы
    • C) Это признак ненормированного веса
    • D) Это значение определяет максимальный вес
    • Правильный ответ: B

15. Какой из приведенных алгоритмов подходит для поиска кратчайшего пути в графе с неотрицательными весами?

    • A) Алгоритм Дейкстры
    • B) Алгоритм Беллмана-Форда
    • C) Алгоритм Флойда-Уоршалла
    • D) Метод ветвей и границ
    • Правильный ответ: A

Итоговые ответы:

1. A
2. B
3. B
4. C
5. A
6. A
7. C
8. C
9. C
10. A
11. A
12. D
13. C
14. B
15. A

С помощью этого теста вы сможете проверить знания школьников по теме графов и их характеристик. Удачи на экзамене!