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

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

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

Вопросы:

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

   • A) Набор данных
   • B) Математическая структура, состоящая из вершин и ребер
   • C) Алгоритм
   • D) Программа

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

2. Что такое весовая матрица графа?

   • A) Таблица с вершинами
   • B) Матрица, в которой хранятся веса ребер между вершинами
   • C) Список вершин
   • D) Алгоритм сортировки

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

3. Какой элемент графа обычно представляет собой точку?

   • A) Ребро
   • B) Путь
   • C) Вершина
   • D) Вес

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

4. Что показывает длина пути между вершинами графа?

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

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

5. Какой из ниже перечисленных графов является направленным?

   • A) Граф без ребер
   • B) Граф с ребрами, которые не имеют направления
   • C) Граф, в котором каждое ребро имеет направление от одной вершины к другой
   • D) Граф с циклом

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

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

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

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

7. Как обозначается вес ребра в весовой матрице графа?

   • A) 0 или 1
   • B) Числом или символом
   • C) Никак, вес не важен
   • D) Соответствующим элементом матрицы

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

8. Если в графе A→B и B→C, какой путь существует?

   • A) A→C
   • B) B→A
   • C) A→B→C
   • D) C→B

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

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

   • A) Алгоритм Дейкстры
   • B) Алгоритм сортировки
   • C) Алгоритм бинарного поиска
   • D) Алгоритм слияния

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

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

    • A) 0
    • B) 1
    • C) Бесконечность
    • D) Зависит от количества вершин

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

11. Что происходит, если в направленный граф добавить цикл?

    • A) Он становится направленным ациклическим графом
    • B) Он остается направленным графом, но теряет свойства ациклического
    • C) Он становится не направленным графом
    • D) Он удаляет все пути между вершинами

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

12. Как понять, что граф является ациклическим?

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

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

13. В какой форме обычно представляется весовая матрица?

    • A) В виде списка
    • B) В виде таблицы
    • C) В виде графа
    • D) В виде формулы

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

14. Какое количество путей между одинаковыми вершинами в ациклическом графе?

    • A) 0
    • B) 1
    • C) Зависит от графа
    • D) Бесконечность

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

15. В какой ситуации весовая матрица будет содержать значение ∞?

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

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

Итоги теста:

• Всего вопросов: 15
• Баллы: 1 балл за каждый правильный ответ
• Максимальный балл: 15

Успехов на экзамене!