Лист заданий по школьным темам

Выберите тему, решите вопросы самостоятельно и сверьтесь с объяснением. Готовый лист можно распечатать.

Графы и маршруты

Информатика · Вопросов: 10

Имя: ____________________ Дата: __________

  1. Корень DFS имеет трёх соседей в исходном графе, но только одного ребёнка в дереве обхода. Достаточно ли трёх соседей для признания точкой сочленения?

    1. Да, любые три ребра гарантируют разрыв
    2. Да, корень любого DFS всегда является точкой сочленения
    3. Нет, у корня нужен минимум два ребёнка дерева DFS
    Разобрать тему
  2. Есть дуги М→Н веса 7, Н→О веса −4 и М→О веса 8. Других дуг нет. Каково кратчайшее расстояние М→О?

    1. 8
    2. Пути нет из-за отрицательной дуги
    3. 3
    Разобрать тему
  3. Из S в T есть только пути весов−3 и−8. Пустой путь к T не разрешён. Каков максимальный вес?

    1. 0
    2. −8
    3. −3
    Разобрать тему
  4. Увеличивающий путь содержит три невыбранных ребра и два выбранных. Как изменится число пар после переключения?

    1. Увеличится на 3
    2. Не изменится, потому что рёбра только переставляются
    3. Увеличится на 1
    Разобрать тему
  5. В ориентированном DFS ребро ведёт к активному предку текущей ветви. Что это показывает?

    1. Отсутствие всех циклов
    2. Наличие направленного цикла
    3. Обязательную несвязность графа
    Разобрать тему
  6. Какие ёмкости суммируются в сертификате разреза?

    1. Потоки всех дуг без учёта направления
    2. Исходные ёмкости дуг из достижимой стороны наружу
    3. Остаточные ёмкости всех дуг сети
    Разобрать тему
  7. Полный лапласиан треугольника имеет нулевой определитель. Сколько у него остовных деревьев?

    1. Ноль
    2. Три
    3. Определить нельзя
    Разобрать тему
  8. В графе А→Б, Б→В, В→А нет других вершин. Что покажет очередь вершин с нулевой входящей степенью?

    1. Обязательно начнёт с А, потому что это первая буква
    2. Сразу будет пустой: допустимого топологического порядка нет
    3. Выдаст любой алфавитный порядок как правильный
    Разобрать тему
  9. Было шесть отдельных объектов. Объединили 1 с 2, затем 2 с 3, затем снова 1 с 3. Сколько компонент осталось?

    1. Три
    2. Четыре
    3. Пять
    Разобрать тему
  10. Есть рёбра A→B,B→A,B→C,а из C нет выходов. Какие компоненты получаются?

    1. {A,B}и{C}
    2. {A,B,C}
    3. {A}и{B,C}
    Разобрать тему

Частые вопросы

Где посмотреть правильные ответы?

Включите «Показать ответы и пояснения» над вопросами. Тогда ответы будут видны на экране и попадут в печатный лист. Без этой отметки печатаются только задания.

Почему вопросов меньше выбранного количества?

Лист использует доступные вопросы выбранной темы и уровня, без повторения одного вопроса внутри набора. Если их меньше, количество не дополняется выдуманными или дублирующими заданиями.