Тест на тему Граф. Весовая матрица

Тест по информатике: Граф. Весовая матрица

Класс: 9

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

Вопросы

1. Что представляет собой граф в информатике?
   a) Набор чисел
   b) Набор объектов, соединённых отношениями
   c) Система уравнений
   d) Множество строк текста

2. Что такое весовая матрица?
   a) Матрица, где каждый элемент – это расстояние между вершинами графа
   b) Таблица с названиями вершин графа
   c) Система координат
   d) Имя файла

3. Каково назначение весовой матрицы?
   a) Хранение данных о вершинах
   b) Хранение весов рёбер между вершинами
   c) Определение количества вершин
   d) Сохранение графического изображения графа

4. Как вычисляется вес рёбер в графе?
   a) С помощью алгоритмов сортировки
   b) На основе данных о соединениях
   c) На основе расстояния между вершинами
   d) Все вышеперечисленные варианты

5. Какой размер будет у весовой матрицы полного графа с n вершинами?
   a) n × n
   b) n × (n - 1)
   c) (n - 1) × (n - 1)
   d) n²

6. Как обозначается отсутствие ребра между вершинами в весовой матрице?
   a) 0
   b) ∞
   c) -1
   d) None

7. Какой из следующих элементов матрицы представляет вес рёбер из вершины i в вершину j?
   a) A[i][j]
   b) A[j][i]
   c) A[i]
   d) A[j]

8. Как записывается весовая матрица графа с 4 вершинами?
   a) 4 × 4
   b) 3 × 4
   c) 2 × 4
   d) 4 × 3

9. Если между двумя вершинами нет ребра, какой вес в соответствующей ячейке матрицы будет уместен?
   a) 0
   b) 1
   c) -1
   d) ∞

10. Какой алгоритм используется для нахождения кратчайшего пути в графе с весами?
    a) Алгоритм Прима
    b) Алгоритм Дейкстры
    c) Алгоритм Флойда-Уоршелла
    d) Оба b и c

11. Какой тип графа представлен в полных графах?
    a) Вершины связаны не между собой
    b) Каждая пара вершин соединена ребром
    c) Рёбра имеют одинаковый вес
    d) Нет рёбер

12. Какой элемент весовой матрицы указывает на прямую связь между двумя вершинами?
    a) 0
    b) 1
    c) Любое положительное число
    d) ∞

13. Какой из графов является взвешенным?
    a) Граф, где рёбра имеют веса
    b) Граф, где рёбра одинаковы
    c) Граф, с одинаковым количеством рёбер и вершин
    d) Граф, который содержит только циклы

14. Какой элемент диагонали весовой матрицы всегда равен?
    a) 0
    b) 1
    c) Вес рёбер
    d) ∞

15. Какой из методов обхода графа используется для поиска всех возможных путей?
    a) Поиск в глубину (DFS)
    b) Поиск в ширину (BFS)
    c) Оба a и b
    d) Никакой из них

16. Что произойдет при добавлении нового ребра в граф?
    a) Увеличится количество рёбер и вершин
    b) Увеличится только количество рёбер
    c) Увеличится только количество вершин
    d) Ничего не произойдет

17. Как легко видоизменить весовую матрицу?
    a) Добавить новые рёбра
    b) Изменить значения весов
    c) Удалить рёбра
    d) Все вышеперечисленное

18. Какое значение в весовой матрице показывает, что вес сильно увеличивается?
    a) 0
    b) 1
    c) Негативное число
    d) ∞

19. Какова основная задача алгоритма Дейкстры?
    a) Построить полный граф
    b) Найти все возможные пути
    c) Найти кратчайший путь от одной вершины до другой
    d) Определить количество рёбер в графе

20. Какой из элементов весовой матрицы указывает на отсутствие ребра в ориентированном графе?
    a) 0
    b) 1
    c) -1
    d) ∞

Ответы

1. b) Набор объектов, соединённых отношениями
2. a) Матрица, где каждый элемент – это расстояние между вершинами графа
3. b) Хранение весов рёбер между вершинами
4. c) На основе расстояния между вершинами
5. a) n × n
6. b) ∞
7. a) A[i][j]
8. a) 4 × 4
9. d) ∞
10. d) Оба b и c
11. b) Каждая пара вершин соединена ребром
12. c) Любое положительное число
13. a) Граф, где рёбра имеют веса
14. a) 0
15. c) Оба a и b
16. b) Увеличится только количество рёбер
17. d) Все вышеперечисленное
18. d) ∞
19. c) Найти кратчайший путь от одной вершины до другой
20. d) ∞

Удачи на тестировании!