1. Чем отличается список от множества?
Список — это упорядоченный набор элементов, а множество — это неупорядоченный набор уникальных элементов.
2. Можно ли сказать, что список — это частный случай двоичного дерева? Почему?
Неверно сказать, что список — это частный случай бинарного дерева, поскольку списки и бинарные деревья — это две разные структуры данных с разными целями. Списки используются для последовательного доступа к элементам, а бинарные деревья используются для эффективного поиска, вставки и удаления элементов на основе ключа.
3. Может ли количество листьев дерева совпадать с количеством его узлов?
В некоторых случаях количество листьев в дереве может равняться количеству узлов в дереве, например, в полном бинарном дереве.
4. Сколько узлов может быть в двоичном дереве высотой 2? Высотой 3? Для каждого случая назовите наибольшее и наименьшее количество узлов.
В бинарном дереве высотой 2 может быть минимум 2 узла и максимум 3 узла. В бинарном дереве высотой 3 может быть минимум 4 узла и максимум 7 узлов.
5. Сколько ребёр может быть в двоичном дереве высотой 2? Высотой 3? Для каждого случая назовите наибольшее и наименьшее количество ребёр.
В бинарном дереве высотой 2 может быть минимум 1 ребро и максимум 2 ребра. В бинарном дереве высотой 3 может быть минимум 2 ребра и максимум 3 ребра.
6. Может ли двоичное дерево высоты 3 содержать больше узлов, чем дерево высоты 5?
Да, бинарное дерево высотой 3 может содержать больше узлов, чем бинарное дерево высотой 5, так как высота дерева определяется как длина самого длинного пути от корня до листа и не гарантирует количество узлов в дереве.
7. Если для кода выполняется обратное условие Фано (ни одно кодовое слово не совпадает с окончанием другого кодового слова), то сообщение можно декодировать однозначно. Какое дерево нужно построить, чтобы убедиться в выполнении обратного условия Фано?
Чтобы гарантировать выполнение обратного условия веера, можно использовать дерево префиксов. В дереве каждый узел представляет символ в строке, а ребро от одного узла к другому представляет следующий символ в строке. Поскольку каждое кодовое слово представлено уникальным путем от корня к листу, ни одно кодовое слово не может быть суффиксом другого кодового слова, удовлетворяющего обратному условию Фано.