2011-gre-cs-practice-book.pdf/Q02 — различия между версиями
Материал из DISCOPAL
Urmat A (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показано 29 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q02-08c765 == | == Вопрос: Q02-08c765 == | ||
Бинарная куча использует следующий массив a[] = [9, 7, 4, 2, 6, 1, 3] для хранения своих элементов. | Бинарная куча использует следующий массив a[] = [9, 7, 4, 2, 6, 1, 3] для хранения своих элементов. | ||
| − | Какими будут оставшиеся значения элементов массива после одной операции удалить-максимум из кучи? | + | Какими будут оставшиеся значения элементов массива после одной операции удалить-максимум из кучи? |
| − | + | ||
| − | + | <graph> | |
| − | + | digraph G { | |
| − | + | 9 -> 7 | |
| − | + | 9 -> 4 | |
| − | + | 7 -> 2 | |
| − | + | 7 -> 6 | |
| + | 4 -> 1 | ||
| + | 4 -> 3 | ||
| + | } | ||
| + | </graph> | ||
=== Ответы === | === Ответы === | ||
| − | + | * [7, 4, 2, 6, 1, 3] | |
| − | + | * [7, 4, 6, 2, 1, 3] | |
| − | + | * [7, 4, 6, 2, 3, 1] | |
| − | + | * [7, 6, 4, 2, 1, 3] | |
| − | + | * Правильный ответ: [7, 6, 4, 2, 3, 1] | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
=== Объяснение === | === Объяснение === | ||
| Строка 27: | Строка 25: | ||
{{cstest-source|2011-gre-cs-practice-book.pdf|14|2}} | {{cstest-source|2011-gre-cs-practice-book.pdf|14|2}} | ||
| − | + | [[File:treesolve.png|480px]] | |
| − | + | ||
| − | + | ||
| + | По рисунку видно, что после удаления 9, на его место встанет последний элемент снизу, он же последний в массиве, то есть 3. | ||
| + | И эта тройка опускается вниз по принципу «тот кто больше из двух потомков встанет на мое место». Сначала это 7 (7 > 4), затем 6 (6 > 2). | ||
| + | {{question-ok|[[Участник:StasFomin|StasFomin]] 20:04, 18 декабря 2024 (UTC)}} | ||
| − | + | [[Категория:Структуры данных]] | |
Текущая версия на 20:24, 18 декабря 2024
Вопрос: Q02-08c765
Бинарная куча использует следующий массив a[] = [9, 7, 4, 2, 6, 1, 3] для хранения своих элементов. Какими будут оставшиеся значения элементов массива после одной операции удалить-максимум из кучи?
Ответы
- [7, 4, 2, 6, 1, 3]
- [7, 4, 6, 2, 1, 3]
- [7, 4, 6, 2, 3, 1]
- [7, 6, 4, 2, 1, 3]
- Правильный ответ: [7, 6, 4, 2, 3, 1]
Объяснение
Исходники — вопрос 2 на 14 странице книги «2011-gre-cs-practice-book.pdf»
По рисунку видно, что после удаления 9, на его место встанет последний элемент снизу, он же последний в массиве, то есть 3. И эта тройка опускается вниз по принципу «тот кто больше из двух потомков встанет на мое место». Сначала это 7 (7 > 4), затем 6 (6 > 2).