Рабочий лист на тему:

Алгоритмические задачи на графах

Информатика11 класс20 заданий
Множественный выборКраткий ответЗаполни пропускиСоединениеИстина / ЛожьСравни числаНайти лишнееПоследовательностьТаблицаРеши задачуРеши примеры

Типы заданий

Множественный выборКраткий ответЗаполни пропускиСоединениеИстина / ЛожьСравни числаНайти лишнееПоследовательностьТаблицаРеши задачуРеши примеры
Алгоритмические задачи на графах

11 класс · дифференцированный

Ф.И.
Класс


Разберём, как представлять графы, находить пути и проверять свойства алгоритмами. Задачи будут усложняться — внимательно отслеживай каждый шаг.

№1 · Вершины и рёбра

1 вопрос · 3 балла

1. Поиск вершин на заданном расстоянии

В неориентированном графе вершины обозначены A, B, C, D, E, F, G, H. Рёбра: AB, AC, BD, CE, DE, EF, FG, BG, DH. Из графа удаляют вершины C и F вместе со всеми инцидентными рёбрами. Сколько оставшихся вершин находятся от A на расстоянии ровно 2?

  • 4
  • 3
  • 1
  • 2

№2 · Степени вершин

1 вопрос · 1 балл

2. Степень вершины

В неориентированном графе рёбра заданы списком: AB, AC, AD, BE. Чему равна степень вершины A?

№3 · Матрица смежности

3 пропуска · 2 балла

3. Заполнение строки матрицы

Заполните пропуски в строке матрицы смежности для вершины A. Граф неориентированный, рёбра: AB, AC, CD. Столбцы идут в порядке A, B, C, D.

Строка для A: ; ; ; .

№4 · Представление графа

4 пары · 2 балла

4. Соответствие представлений

Соотнесите способ представления графа с его характеристикой.

№5 · Обход графа

5 утверждений · 2 балла

5. Свойства поиска в ширину

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

  1. Поиск в ширину обрабатывает вершины по уровням удалённости от стартовой вершины.
  2. Поиск в ширину всегда выбирает следующую вершину с максимальным номером.
  3. Для хранения ожидающих обработки вершин обычно используют очередь.
  4. Поиск в ширину нельзя применять к неориентированному графу.
  5. В невзвешенном графе поиск в ширину может найти кратчайшее число рёбер от старта до вершины.

№6 · Кратчайший путь

3 сравнения · 3 балла

6. Сопоставление составных маршрутов

Для каждой пары вычислите суммарный вес обоих маршрутов в одном взвешенном графе, затем сравните длины путей и выберите подходящий знак. Все веса рёбер положительны.

1)Путь A–B–E–F: 7 + 4 + 6Путь A–C–D–F: 5 + 8 + 3
2)Путь B–C–D–E–G: 6 + 3 + 7 + 4Путь B–F–G: 9 + 8
3)Путь A–C–D–E–G: 5 + 8 + 2 + 6Путь A–B–E–F–G: 7 + 4 + 5 + 9

№7 · Дерево поиска

4 элемента · 3 балла

7. Выбор корректного дерева

Найдите лишний вариант. Обычные варианты являются деревьями: в них граф связен и не содержит циклов.

  1. Вершины A, B, C; рёбра AB, BC, CA
  2. Вершины A, B, C; рёбра AB, BC
  3. Вершины A, B, C, D; рёбра AB, BC, CD
  4. Вершины A, B, C, D; рёбра AB, AC, AD

№8 · Алгоритм дейкстры

5 шагов · 3 балла

8. Порядок работы алгоритма

Расположите шаги алгоритма Дейкстры для поиска кратчайших расстояний от одной вершины в правильном порядке.

  1. Завершить работу, если нужная вершина выбрана или непосещённых вершин не осталось.
  2. Пометить выбранную вершину как обработанную.
  3. Пересчитать метки соседей, если путь через выбранную вершину короче.
  4. Для стартовой вершины установить расстояние 0, для остальных — бесконечность.
  5. Выбрать непосещённую вершину с минимальной текущей меткой.

№9 · Анализ связности

4 строки · 4 балла

9. Таблица достижимости

Заполните таблицу для неориентированного графа с рёбрами AB, BC, DE. В каждой строке определите, достижима ли вторая вершина из первой.

Пара вершинЕсть ли путь?Минимальное число рёбер
A и C
A и D
D и E
B и C

№10 · Алгоритмическая стратегия

1 задача · 4 балла

10. Поиск кратчайшего пути во взвешенном графе

В ориентированном взвешенном графе заданы рёбра: A→B (4), A→C (2), C→B (1), B→D (5), C→D (8), B→E (7), D→E (2), D→F (6), E→F (1). Найдите кратчайший путь из вершины A в вершину F и его длину. Покажите 2–3 шага выбора промежуточных вершин алгоритма поиска кратчайших путей.

№1 · Термины

1 вопрос · 1 балл

1. Поиск кратчайшего пути в графе

В неориентированном графе рёбра имеют вид: A—B, A—C, B—D, C—D, D—E, C—F, E—F. Какова длина кратчайшего пути из вершины A в вершину F? Выберите единственный верный ответ.

  • 3 ребра
  • 2 ребра
  • 4 ребра
  • 1 ребро

+10 заданий в этом листе

Зарегистрируйтесь — и соберите свой рабочий лист по этой теме за минуту: заданий столько, сколько нужно.

№2 · Матрица

3 пропуска · 2 балла

2. Представление графа матрицей смежности

Заполните пропуски в описании неориентированного графа.

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

№3 · Соответствие

4 пары · 2 балла

3. Алгоритмы и их назначение

Соедините каждый алгоритм с его основным назначением.

№4 · Матрица смежности

4 строки · 2 балла

4. Восстановление свойств графа

Изучите матрицу смежности простого неориентированного графа и заполните пропуски. В строке с названием вершины укажите её степень, а в последней строке определите число рёбер графа.

ВершинаABCDСтепень
A0110
B1011
C1101
D0110
Число рёбер4444

№5 · Свойства

5 утверждений · 2 балла

5. Связность и циклы

Для каждого утверждения определите, верно ли оно. Основание проверки — определения и свойства неориентированных графов.

  1. Если между каждой парой вершин существует путь, граф связный.
  2. В связном графе обязательно есть цикл.
  3. Дерево — это связный граф без циклов.
  4. В полном графе каждая вершина соединена ровно с одной другой вершиной.
  5. В неориентированном графе сумма степеней всех вершин равна удвоенному числу рёбер.

№6 · Алгоритм

5 шагов · 2 балла

6. Порядок поиска в ширину

Расположите шаги алгоритма поиска в ширину в правильном порядке.

  1. Добавить в очередь непосещённую соседнюю вершину.
  2. Выбрать стартовую вершину и пометить её посещённой.
  3. Повторять обработку, пока очередь не станет пустой.
  4. Извлечь из очереди очередную вершину.
  5. Для извлечённой вершины просмотреть всех соседей.

№7 · Анализ

4 элемента · 2 балла

7. Распознавание дерева

Найдите лишний набор характеристик. Три варианта описывают свойства дерева, один вариант — нет.

  1. Связный граф из 7 вершин и 6 рёбер без циклов.
  2. Связный граф из 8 вершин и 8 рёбер без петель.
  3. Граф, в котором между любыми двумя вершинами существует ровно один простой путь.
  4. Связный граф из 10 вершин и 9 рёбер.

№8 · Сравнение

3 пары · 2 балла

8. Сравнение длин маршрутов

Сравните длины маршрутов в каждом пункте. Все веса рёбер неотрицательны; знак уже не указан, его нужно определить.

1)
2)
3)

№9 · Кратчайший путь

1 задача · 3 балла

9. Алгоритм Дейкстры на взвешенном графе

В ориентированном графе заданы рёбра и их веса: — 4, — 2, — 1, — 5, — 8. Найдите длину кратчайшего пути из вершины в вершину . Запишите основные действия алгоритма Дейкстры.

№10 · Подсчёт

4 выражения · 2 балла

10. Подсчёт числа рёбер и степеней

Вычислите значения выражений, используя свойства неориентированных графов.

1)
2)
3)
4)

Создайте уникальный лист по своей теме

  • Любая тема, любой уровень
  • 20+ типов заданий
  • 100% уникальный контент
  • Со страницей ответов
  • Защита от списывания
  • Готово за 1 минуту

Другие темы по информатике для 11 класса

Обновление драйверов, конфигурирование системы, управление ресурсами локальной сетиОптимизация контента и индексирование сайта поисковыми системамиОбработка текстовой информацииСоздание и форматирование документа с помощью текстового редактора MS Word. Создание структурированного документаСредства искусственного интеллектаФункции в Python: основные встроенные и создание собственныхВиды деятельности в сети Интернет, сервисы Интернета, сетевой этикет, проблема подлинности полученной информации, государственные электронные сервисы и услуги, открытые образовательные ресурсыАнализ правильности скобочного выраженияСетевое хранение данных и цифрового контента. Облачные сервисы. Цифровые сервисы государственных услуг. Разделение прав доступа в облачных хранилищах. Соблюдение мер безопасности, предотвращающих незаконное распространение персональных данныхДискретные игры двух игроков с полной информациейОсновные сведения об алгоритмахЦиклы с условием. Циклы по переменной; Язык программирования. Основные конструкции языка; Типы данных: целочисленные, вещественные, символьные, логические; Ветвления. Составные условия; Этапы решения

Чем удобны рабочие листы Нейрум

  • По действующей программеТемы и задания совпадают со школьной программой 1–11 классов. Открыли — дали классу, без правок.
  • Готово к печати, с ответамиPDF в формате A4 и ключ ответов на отдельной странице. Скачали, распечатали, раздали — без правок в Word.
  • Свой лист за минутуНе нашли нужный? ИИ-конструктор соберёт лист по вашей теме, классу и типам заданий.

Вопросы и ответы

Как скачать рабочий лист «Графы. Решение алгоритмических задач, связанных с анализом графов»?

Зарегистрируйтесь бесплатно — лист сохранится в личном кабинете, откуда его можно скачать в PDF и распечатать.

Сколько заданий в листе и какие они?

В листе 20 заданий: множественный выбор, краткий ответ, заполни пропуски, соединение, истина / Ложь, сравни числа, найти лишнее, последовательность, таблица, реши задачу, реши примеры.

Соответствует ли лист ФГОС?

Да, задания ориентированы на школьную программу по информатике для 11 класса по ФГОС.

Можно ли изменить задания под свой класс?

Да. После регистрации лист открывается в конструкторе: задания можно заменить, перегенерировать или добавить новые.