Презентация на тему по информатике на тему Структуры данных

виде, отражающем связи (смысловые, ассоциативные, причинно-следственные и другие).
Структурирование информации

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

указывается номер и заголовок.
Заголовки столбцов пишутся с заглавной буквы,

если необходимо указываются размерности величин.

объектами)

соединяющих их ребер.
Используют когда в задаче есть несколько однотипных

объектов и каждый из них связан с произвольным количеством других объектов.
Граф – это средство для наглядного представления состава и структуры некоторой системы.

сложных реакций)
В информатике и программировании
Изображение связей наследования

соединенные ребром, называются смежными.
Петля – ребро, которое начинается и

заканчивается в одной и той же вершине

смежности учтено два раза
Матрица симметрична относительно главной диагонали
1

несимметрична относительно главной диагонали

ребра нет – клетка пустая
Вес может обозначать длину дороги

или стоимость проезда
Взаимное расположение вершин не определено

8

12

2

4

6

5

8

2

4

6

5

12

в графе называется последовательная цепочка смежных ребер, которая начинается

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

Возможные пути из А в В:
АВ
АСВ
ACDB

Циклом называется путь, у которого начало и конец совпадают.
 На рисунке циклами являются следующие пути: (ACBA), (ACDBA).

ГОРКА, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между

ними:

Аэропорт вылета Аэропорт прилета Время вылета Время прилета
ВОСТОРГ ГОРКА 16:15 18:30
ОЗЕРНЫЙ ЗАРЯ 13:40 15:50
ОЗЕРНЫЙ ВОСТОРГ 14:10 16:20
ГОРКА ОЗЕРНЫЙ 17:05 19:20
ВОСТОРГ ОЗЕРНЫЙ 11:15 13:20
ЗАРЯ ОЗЕРНЫЙ 16:20 18:25
ВОСТОРГ ЗАРЯ 14:00 16:15
ЗАРЯ ГОРКА 16:05 18:15
ГОРКА ЗАРЯ 14:10 16:25
ОЗЕРНЫЙ ГОРКА 18:35 19:50

Путешественник оказался в аэропорту ВОСТОРГ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт ГОРКА.

1) 16:15 2) 18:15 3)18:30 4) 19:50

Решение задач Задача 1

ВОСТОРГ в ГОРКУ с прибытием в 18:30:
ВОСТОРГ ГОРКА

16:15 18:30
Посмотрим, сможет ли путешественник оказаться в ГОРКЕ раньше этого времени, если полетит через другой аэропорт, с пересадкой; рассмотрим все остальные рейсы, который прибывают в аэропорт ГОРКА:
ЗАРЯ ГОРКА 16:05 18:15
ОЗЕРНЫЙ ГОРКА 18:35 19:50
Это значит, что имеет смысл проверить только возможность перелета через аэропорт ЗАРЯ (через ОЗЕРНЫЙ явно не получится раньше, чем прямым рейсом); для этого нужно быть в ЗАРЕ не позже, чем в 16:05
Смотрим, какие рейсы прибывают в аэропорт ЗАРЯ раньше, чем в 16:05:
ОЗЕРНЫЙ ЗАРЯ 13:40 15:50
Дальше проверяем рейсы, который приходят в ОЗЕРНЫЙ раньше, чем в 13:40
ВОСТОРГ ОЗЕРНЫЙ 11:15 13:20
Таким образом, мы «пришли» от конечного пункта к начальному, в обратном направлении
Поэтому оптимальный маршрут

Правильный ответ – 2.

Решение Задача 1

на пересечениях строк и столбцов таблиц, означают стоимость проезда

между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.

Решение задач Задача 2

Задача 2

таблицы:
1:
или
, стоимость 7
или
2:
, стоимость 7
3:
4:
,

стоимость 6

Условие «не больше 6» выполняется только для таблицы 3
Таким образом, правильный ответ – 3.

, стоимость 8

железнодорожными станциями.
Укажите схему, соответствующую таблице.
Задача 1

E построены дороги, протяженность которых приведена в таблице.
Определите

кратчайший путь между пунктами A и D (при условии, что передвигаться можно только по построенным дорогам).

Самостоятельная работа

некоторыми парами вершин.
Наличие циклов.

отображения таких связей между объектами как вложенность, подчиненность, наследование

и т.п.

Свойства дерева:
Между любыми двумя его вершинами существует единственный путь.
Деревья не содержат циклов и петель.

Каждая вершина (кроме корня) имеет одну исходную вершину на предыдущем уровне и множество порожденных вершин на следующем уровне.
Вершины, не имеющие порожденных вершин, называются листьями.

вершины

1;4;7 (цифры в записи числа не повторяются).
Для её

решения построим схему-дерево возможных вариантов.

число

1

4

7

4

7

7

4

1

7

7

1

1

4

4

1

Ответ: 6 вариантов.
Числа 147; 174; 417; 471; 714; 741