Урок 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качать материалы урока
