Задание 5. Деревья

Задание 1.

Составить программу, позволяющую найти НОД по алгоритму Эвклида

(Запись лекции от 11.02.2014, Часть 1, позиция: 00:14:40)

Задание 2.

Пусть время работы алгоритма .
Если X элементов обрабатывается за Y мсек., то во сколько раз следует ожидать увеличения времени выполнения при обработке Z элементов.

(Запись лекции от 11.02.2014, Часть 2, позиция: 1:15:00)

Задание 3.

При каком наименьшем N алгоритм, требующий 100N² операций эффективнее алгоритма, требующего 2ⁿ операций

(Запись лекции от 11.02.2014, Часть 2, позиция: 1:19:00)

Задание 4.

1.

2.

3.

4.

5.

(Запись лекции от 12.02.2014, позиция: 1:30:30)

Задание 5. Деревья.

Упражнение 1.

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

Определите:

1. количество листьев,

2. число уровней

3. высоту дерева

4. длину внутреннего пути расширенного дерева

5. длину внешнего пути расширенного дерева

Упражнение 2.

Пусть в сообщении символы а, б, в, г, д, е появляются с частотой, указанной в вашем варианте соответственно. Постройте дерево Хаффмана. Найдите оптимальный код. Определите, объём (в битах) закодированного с помощью кода Хаффмана сообщения.