Урок 3
Структура информации (простые структуры). Деревья. Графы
§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качать материалы урока