2011-gre-cs-practice-book.pdf/Q16 — различия между версиями
Материал из DISCOPAL
Urmat A (обсуждение | вклад) (→Вопрос: Q16-08c765) |
Urmat A (обсуждение | вклад) (→Вопрос: Q16-08c765) |
||
| Строка 1: | Строка 1: | ||
{{reserve-task|[[Участник:Urmat A|Urmat A]] 18:28, 18 декабря 2024 (UTC)}} | {{reserve-task|[[Участник:Urmat A|Urmat A]] 18:28, 18 декабря 2024 (UTC)}} | ||
| + | {{reserve-task|[[Участник:Urmat A|Urmat A]] 18:30, 18 декабря 2024 (UTC)}} | ||
== Вопрос: Q16-08c765 == | == Вопрос: Q16-08c765 == | ||
| Строка 17: | Строка 18: | ||
Проиллюстрируем на картинке: | Проиллюстрируем на картинке: | ||
| − | [[Файл:Full Binary Heap.png|640px]] | + | [[Файл:Full Binary Heap.png|640px]] |
| + | |||
| + | Начнём с первого дерева у которого два листа. Далее, если мы хотим прибавить +1 лист к дереву, то мы дорисовываем по 2 потомка свободным листам, беря их слева направо. Таким образом количество листьев всегда на 1 больше количества внутренних узлов | ||
{{question-ok|}} | {{question-ok|}} | ||
Версия 18:30, 18 декабря 2024
Задача зарезервирована: Urmat A 18:28, 18 декабря 2024 (UTC)
Задача зарезервирована: Urmat A 18:30, 18 декабря 2024 (UTC)
Вопрос: Q16-08c765
Полное бинарное дерево — это корневое дерево, в котором каждый внутренний узел имеет ровно два потомка. Сколько внутренних узлов в полном бинарном дереве с 500 листьями?
Ответы
- 250
- Правильный ответ: 499
- 500
- 501
- 1000
Объяснение
Исходники — вопрос 16 на 22 странице книги «2011-gre-cs-practice-book.pdf»
Проиллюстрируем на картинке:
Начнём с первого дерева у которого два листа. Далее, если мы хотим прибавить +1 лист к дереву, то мы дорисовываем по 2 потомка свободным листам, беря их слева направо. Таким образом количество листьев всегда на 1 больше количества внутренних узлов