Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, сокращенный курс, 2 часа в неделю)



Урок 4
Структура информации (простые структуры). Деревья. Графы
§4. Структура информации




Содержание урока

Зачем структурировать информацию?

Знакомые структуры данных

Иерархия (дерево)

Графы

Вопросы и задания

Задачи

Практическая работа № 1 «Оформление документа»

Практическая работа № 2 «Структуризация информации (таблица, списки)»

Практическая работа № 3 «Структуризация информации (деревья)»

Практическая работа № 4 «Графы»


Задачи


1. Определите выражения, соответствующие каждому из деревьев, в «нормальном» виде со скобками (эту форму называют инфиксной — операция записывается между данными). Постройте для каждого из них постфиксную форму.

2. Постройте деревья, соответствующие следующим арифметическим выражениям. Запишите эти выражения в префиксной и постфиксной формах:

а) (a+b)*(c+2*d)
б) (2*a-3*d)*c+2*b
в) (a+b+2*c)*d
г) 3*a-(2*b+c)*d

3. Вычислите выражения, записанные в постфиксной форме:


а) 12 6 + 7 3 - 1 - * 12 +
б) 12 10 - 5 7 + * 7 - 2 *
в) 5 6 7 8 9 + - + -
г) 5 4 3 2 1 - - - -

Запишите каждое из них в инфиксной и в префиксной формах и постройте соответствующее дерево. Единственно ли такое дерево? В этом дереве назовите корень, листья и промежуточные вершины.

4. Нарисуйте граф, в котором 5 вершин и три компоненты связности. Постройте его матрицу смежности.

5. Структурируйте следующую информацию разными способами: «Между посёлками Верхний и Нижний есть просёлочная дорога длиной 10 км. Село Сергеево соединяется двумя асфальтовыми шоссе с Нижним (22 км) и Верхним (16 км). В село Солнечное можно доехать только из Сергеева по грунтовой дороге (5 км)». Можно ли сказать точно, как расположены эти пункты?

6. Для графа, полученного в предыдущей задаче, постройте матрицу смежности, список смежности, весовую матрицу. Является ли этот граф деревом?

7. Постройте матрицы смежности и весовые матрицы графов:

8. Постройте графы, соответствующие матрицам смежности.

9. Постройте графы, соответствующие весовым матрицам.

10. Стоимость перевозок между пунктами, которые для краткости обозначены буквами А, В, С, D и Е, задаётся таблицей (весовой матрицей графа). Нужно перевезти груз из пункта А в пункт В. Для каждого из четырёх вариантов определите оптимальный маршрут и полную стоимость перевозки.

11. Постройте орграфы, соответствующие весовым матрицам.

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



Следующая страница Практическая работа № 1 «Оформление документа»



Cкачать материалы урока







Наверх