ГДЗ по информатике 9 класс учебник Поляков, Еремин § 13. Списки и деревья

1. Чем отличается список от множества?

Множество - тип данных, который хранит в себе, как правило, ограниченное количество элементов одного типа. Повторяющихся значений здесь нет. Не упорядочены. Список - тип данных, который хранит в себе значения, которые могут встречаться более одного раза. Упорядочен.

2. Можно ли сказать, что список — это частный случай двоичного дерева? Почему?

Да, и список и дерево имеют упорядоченную последовательность  элементов и иерархия в них важна.

3. Может ли количество листьев дерева совпадать с количеством его узлов?

Да, например пустое дерево с 1 узлом, которое же является и листом.

4. Сколько узлов может быть в двоичном дереве высотой 2? Высотой 3? Для каждого случая назовите наибольшее и наименьшее количество узлов.

2² = 4

2³ = 8

Число узлов в двоичном дереве не может превышать двойки в степени, равной высоте этого дерева.

5. Сколько ребёр может быть в двоичном дереве высотой 2? Высотой 3? Для каждого случая назовите наибольшее и наименьшее количество ребёр.

2

22   

2 ребра

    2

2      2

22  22

6 ребер

6. Может ли двоичное дерево высоты 3 содержать больше узлов, чем дерево высоты 5?

Да, может.

Дерево высотой 3:

2

2 2

22 22

Дерево высотой 5:

2

2

2

2

2

7. Если для кода выполняется обратное условие Фано (ни одно кодовое слово не совпадает с окончанием другого кодового слова), то сообщение можно декодировать однозначно. Какое дерево нужно построить, чтобы убедиться в выполнении обратного условия Фано?