2019-gate-computer-science-and-it-practice.pdf/Q31-alg1 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q31-alg1-31d68c == <blockquote> Вопрос из «Algorithms Test 1» где-то со страницы 222. Тут вставьте пер…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q31-alg1-31d68c == | == Вопрос: Q31-alg1-31d68c == | ||
| + | Каково минимальное и максимальное количество узлов, которые может содержать в себе [https://en.wikipedia.org/wiki/Min-max_heap куча на минимум/максимум] высотой ''h''? | ||
| − | < | + | === Ответ === |
| − | + | * Соответственно <m>2^{h-1}</m> и <m>2^{h+1}</m> | |
| − | + | * Соответственно <m>2^{h-1}</m> и <m>2^{h}</m> | |
| − | + | * Правильный ответ: Соответственно <m>2^{h}</m> и <m>2^{h+1} - 1</m> | |
| − | + | * Соответственно <m>2^{h+1} - 1</m> и <m>2^{h+1}</m> | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | </ | + | |
| − | + | ||
| − | + | ||
| − | < | + | |
| − | + | ||
| − | + | ||
| − | * Правильный ответ: | + | |
| − | + | ||
| − | + | ||
| − | * | + | |
| − | + | ||
| − | + | ||
| − | < | + | |
| − | + | ||
| − | + | ||
| − | + | ||
=== Объяснение === | === Объяснение === | ||
| − | + | * Куча — это полное бинарное дерево. | |
| − | + | * Все уровни, кроме самого нижнего, полностью заполнены. | |
| − | + | * Таким образом, куча содержит как минимум <m>2^{h}</m> элементов и максимум <m>2^{h+1} - 1</m> элементов. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | </ | + | |
| − | {{ | + | {{cstest-source|2019-gate-computer-science-and-it-practice.pdf|225|31}} |
| − | { | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 23:58, 24 декабря 2024 (UTC)}} |
| − | [[ | + | [[Категория:Деревья]] |
| + | [[Категория:Структуры данных]] | ||
Текущая версия на 23:58, 24 декабря 2024
Вопрос: Q31-alg1-31d68c
Каково минимальное и максимальное количество узлов, которые может содержать в себе куча на минимум/максимум высотой h?
Ответ
- Соответственно и
- Соответственно и
- Правильный ответ: Соответственно и
- Соответственно и
Объяснение
- Куча — это полное бинарное дерево.
- Все уровни, кроме самого нижнего, полностью заполнены.
- Таким образом, куча содержит как минимум элементов и максимум элементов.
Исходники — вопрос 31 на 225 странице книги «2019-gate-computer-science-and-it-practice.pdf»