Моделирование. § 16. Списки и деревья

Август 11, 2022

Главная
Информатика
Моделирование. § 16. Списки и деревья

Содержание

2. Что такое список? Список – последовательность элементов, в которой важен порядок их расположения. Список как модель:
3. Операции со списком замена элемента удаление элемента вставка нового элемента КРАН → КОАН → КОРН →
4. Что такое дерево? Дерево – это структура данных, которая служит моделью многоуровневой структуры (иерархии). Лес –
5. Из чего состоит дерево? A – D, E, F, G – корень листья B, C –
6. Родители и дети B – родитель для D и E D и E – сыновья для
7. Генеалогическое дерево Иванов А.Б. Иванова Д.А. Семёнова М.А. Иванов К.А. Семёнов C.C. Семёнов А.C. Иванов C.К.
8. Классификации Глава 1. Псообразные 1.1. Псовые 1.2. Енотовые 1.3. Медвежьи … Глава 2. Кошкоообразные 2.1. Кошачьи
9. Файловая система
10. Арифметические выражения Двоичное (бинарное) дерево – это дерево, в котором каждый узел может иметь не более
11. Запишите выражения, соответствующие дереву:
12. Перебор вариантов Составить все двухбуквенные слова, которые можно записать с помощью алфавита {A, Б, В}. Б
13. Дерево для двоичного кода Г Д Б В А 0 1 1 0 0 1 0
14. С помощью дерева перебора найдите все трёхзначные числа, меньшие 300, сумма цифр которых равна 6. Сколько
15. Перебор вариантов Разведчик выяснил, что ключ к замку от сейфа состоит из трёх символов, причём могут
17. Скачать презентацию

Слайд 2

Что такое список?
Список – последовательность элементов, в которой важен порядок их

расположения.

Список как модель:

слово = список букв, текст = список абзацев

Слайд 3

Операции со списком
замена элемента
удаление элемента
вставка нового элемента
КРАН → КОАН → КОРН

→ КОРО → КОРОН → КОРОНА

Слайд 4

Что такое дерево?
Дерево – это структура данных, которая служит моделью многоуровневой

структуры (иерархии).

Лес – это несколько деревьев.

Слайд 5

Из чего состоит дерево?
A –
D, E, F, G –
корень
листья
B,

C –

промежуточные
узлы

Путь — это последовательность узлов, где каждый следующий связан с предыдущим.

Высота дерева — это количество уровней.

Поддерево — это часть дерева, которая тоже представляет собой дерево.

левое
поддерево

правое
поддерево

Слайд 6

Родители и дети
B – родитель для D и E
D и E

– сыновья для B

Предок – потомок: между ними есть путь.

A и B – предки для D и E
B, D и E – потомки для A

Родитель – сын: между ними есть ребро.

Слайд 7

Генеалогическое дерево
Иванов А.Б.
Иванова Д.А.
Семёнова М.А.
Иванов К.А.
Семёнов C.C.
Семёнов А.C.
Иванов C.К.

Слайд 8

Классификации
Глава 1. Псообразные
1.1. Псовые
1.2. Енотовые
1.3. Медвежьи
…
Глава 2.

Кошкоообразные
2.1. Кошачьи
2.2. Гиеновые
2.3. Мангустовые

Слайд 9

Файловая система

Слайд 10

Арифметические выражения
Двоичное (бинарное) дерево – это дерево, в котором каждый узел

может иметь не более двух сыновей.

Слайд 11

Запишите выражения, соответствующие дереву:

Слайд 12

Перебор вариантов
Составить все двухбуквенные слова, которые можно записать с помощью алфавита

{A, Б, В}.

Б

Б

A

В

Б

В

Б

A

В

A

A

В

пустое дерево

БВ

Слайд 13

Дерево для двоичного кода
Г
Д
Б
В
А
0
1
1
0
0
1
0
1
Условие Фано: ни одно из кодовых слов не

совпадет с началом другого кодового слова.

тогда однозначно декодируется!

Слайд 14

С помощью дерева перебора найдите все трёхзначные числа, меньшие 300, сумма

цифр которых равна 6.

Сколько чисел вы нашли?

11

Слайд 15

Перебор вариантов
Разведчик выяснил, что ключ к замку от сейфа состоит из

трёх символов, причём могут использоваться буквы из алфавита {A, B, C, D}. Две одинаковые буквы не могут стоять рядом. Рядом с буквой D обязательно должна стоять буква A. Если в ключе есть буква B, то там не может быть буквы C.

14