2011-gre-cs-practice-book.pdf/Q16

Задача зарезервирована: Urmat A 18:28, 18 декабря 2024 (UTC)

Задача зарезервирована: Urmat A 18:30, 18 декабря 2024 (UTC)

Задача зарезервирована: Urmat A 18:31, 18 декабря 2024 (UTC)

Вопрос: Q16-08c765

Полное бинарное дерево — это корневое дерево, в котором каждый внутренний узел имеет ровно два потомка. Сколько внутренних узлов в полном бинарном дереве с 500 листьями?

Ответы

1. 250
2. Правильный ответ: 499
3. 500
4. 501
5. 1000

Объяснение

Исходники — вопрос 16 на 22 странице книги «2011-gre-cs-practice-book.pdf»

Проиллюстрируем на картинке:

Начнём с первого дерева у которого два листа. Далее, если мы хотим прибавить +1 лист к дереву, то мы дорисовываем по 2 потомка свободным листам, беря их слева направо. Таким образом количество листьев всегда на 1 больше количества внутренних узлов Решено: Urmat A 18:31, 18 декабря 2024 (UTC)

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.