Просто УрокТест · информатика
Графы и таблицы
Отвечай кликом — после каждого вопроса пояснение. 10 вопросов, 4 варианта, 3–5 минут. Без таймеров и регистрации.
Отвечено 0 из 10 · Верно: 0
1/10
В таблице указаны дороги между посёлками A, B, C, D и их длины: A–B=3, B–C=4, C–D=2, A–C=7, B–D=10. Какова длина кратчайшего пути из A в D?
Пояснение. Кратчайшие пути A–B–C–D и A–C–D имеют длину 9, путь A–B–D длиннее.
2/10
Матрица смежности неориентированного графа с 4 вершинами: 0 1 0 1; 1 0 1 0; 0 1 0 1; 1 0 1 0. Сколько рёбер в графе?
Пояснение. В матрице смежности неориентированного графа 8 единиц, каждое ребро учтено дважды, поэтому рёбер 4.
3/10
Граф: A соединена с B и C; B соединена с A, C, D; C соединена с A, B; D соединена с B. Сколько существует простых путей из A в D?
Пояснение. Есть два пути без повторения вершин: A–B–D и A–C–B–D.
4/10
В таблице указана стоимость перевозки между пунктами: П1–П2=5, П1–П3=12, П2–П3=3, П2–П4=9, П3–П4=4. Какова минимальная стоимость пути из П1 в П4?
Пояснение. Путь П1–П2–П3–П4 стоит 5+3+4=12, это меньше остальных вариантов.
5/10
Ориентированный граф задан рёбрами: A→B, B→C, C→A, B→D. Какие вершины достижимы из A?
Пояснение. Из A можно попасть в B, затем в C и D.
6/10
Взвешенный граф содержит рёбра: A–B=1, B–C=2, C–D=3, A–D=10. Какова длина кратчайшего пути из A в D?
Пояснение. Путь A–B–C–D имеет длину 1+2+3=6, это короче прямого ребра A–D.
7/10
В дереве с 5 вершинами хотят добавить рёбра так, чтобы получился полный граф на этих 5 вершинах. Сколько рёбер нужно добавить?
Пояснение. В дереве 4 ребра, в полном графе на 5 вершинах 10 рёбер, значит добавить нужно 6.
8/10
Дана таблица расстояний: A–B=2, A–C=5, B–C=1, B–D=4, C–D=3. Какова длина кратчайшего пути из A в D?
Пояснение. Кратчайшие пути A–B–D и A–B–C–D дают длину 6.
9/10
В неориентированном графе 6 вершин и 7 рёбер. Какое утверждение обязательно верно?
Пояснение. Лес без циклов на 6 вершинах имеет не более 5 рёбер, поэтому при 7 рёбрах цикл обязательно есть.
10/10
Матрица смежности ориентированного графа с 3 вершинами: 0 1 0; 0 0 1; 1 0 0. Сколько рёбер исходит из вершины 2 (нумерация с 1)?
Пояснение. Во второй строке матрицы ровно одна единица, значит из вершины 2 исходит одно ребро.
Важно. Тесты носят информационно-образовательный характер и не являются публичной офертой (ст. 437 ГК РФ) или аттестацией. Возможны неточности — сверяйтесь с официальными источниками (ФИПИ, учебники). Заметили ошибку — напишите нам.