2004-gre-cs-practice-book.pdf/Q10 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q10-4c9f66 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…») |
StasFomin (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q10-4c9f66 == | == Вопрос: Q10-4c9f66 == | ||
| + | [https://en.wikipedia.org/wiki/M-ary_tree ''k''-арное дерево] — это дерево, в котором каждый узел имеет не более ''k'' детей. | ||
| − | + | Если в нем ''n'' узлов и высота ''h'', какое из следующих значений является верхней границей для максимального количества листьев в зависимости от ''h'', ''k'' и ''n''? | |
| − | + | ||
| − | + | ||
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | < | + | * <m>log_kn</m> |
| − | + | * <m>\log_kh</m> | |
| + | * <m>\frac{n}{\log_kn}</m> | ||
| + | * Правильный ответ: <m>k^h</m> | ||
| + | * <m>h^k</m> | ||
| − | + | === Объяснение === | |
| − | + | {{cstest-source|2004-gre-cs-practice-book.pdf|16|10}} | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | Число узлов неважно, если мы знаем высоту. Ну на каждом уровне высоты, у нас может быть ''k''-потомков. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 23:27, 13 декабря 2024 (UTC)}} | |
| − | + | [[Категория:Деревья]] | |
Текущая версия на 23:30, 13 декабря 2024
Вопрос: Q10-4c9f66
k-арное дерево — это дерево, в котором каждый узел имеет не более k детей.
Если в нем n узлов и высота h, какое из следующих значений является верхней границей для максимального количества листьев в зависимости от h, k и n?
Ответы
- Правильный ответ:
Объяснение
Исходники — вопрос 10 на 16 странице книги «2004-gre-cs-practice-book.pdf»
Число узлов неважно, если мы знаем высоту. Ну на каждом уровне высоты, у нас может быть k-потомков.