2001-gre-vs-practice.pdf/Q05 — различия между версиями
Материал из DISCOPAL
Urmat A (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q05-e5724f == | == Вопрос: Q05-e5724f == | ||
| − | Что из нижеперечисленного является обратным обходом[https://habr.com/ru/articles/267855/#:~:text=%D0%92%D1%81%D0%BF%D0%BE%D0%BC%D0%BE%D0%B3%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9%20%D1%80%D0%B8%D1%81%D1%83%D0%BD%D0%BE%D0%BA%20%D0%B4%D0%BB%D1%8F%20%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%BE%D0%B2] приведённого двоичного дерева? | + | Что из нижеперечисленного является [https://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B0 обратным обходом] [https://habr.com/ru/articles/267855/#:~:text=%D0%92%D1%81%D0%BF%D0%BE%D0%BC%D0%BE%D0%B3%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9%20%D1%80%D0%B8%D1%81%D1%83%D0%BD%D0%BE%D0%BA%20%D0%B4%D0%BB%D1%8F%20%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%BE%D0%B2] приведённого двоичного дерева? |
| − | |||
A | A | ||
/ \ | / \ | ||
| Строка 11: | Строка 9: | ||
=== Ответы === | === Ответы === | ||
| − | + | * ABCDEF | |
| − | + | * ABDECF | |
| − | + | * DBEACF | |
| − | + | * Правильный ответ: DEBFCA | |
| − | + | * DEFBCA | |
| Строка 22: | Строка 20: | ||
{{cstest-source|2001-gre-vs-practice.pdf|13|5}} | {{cstest-source|2001-gre-vs-practice.pdf|13|5}} | ||
| − | Давайте вручную обойдём дерево, как на примере [https://habr.com/ru/articles/267855/#:~:text=%D0%92%D1%81%D0%BF%D0%BE%D0%BC%D0%BE%D0%B3%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9%20%D1%80%D0%B8%D1%81%D1%83%D0%BD%D0%BE%D0%BA%20%D0%B4%D0%BB%D1%8F%20%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%BE%D0%B2]. Начнём в самой левой нижней вершине D. Далее E, и их предок B. Левое поддерево корня обошли, идём в правое: в F, далее в C. Остался корень A. Получили D-E-B-F-C-A. | + | Давайте вручную обойдём дерево, как на примере [https://habr.com/ru/articles/267855/#:~:text=%D0%92%D1%81%D0%BF%D0%BE%D0%BC%D0%BE%D0%B3%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9%20%D1%80%D0%B8%D1%81%D1%83%D0%BD%D0%BE%D0%BA%20%D0%B4%D0%BB%D1%8F%20%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%BE%D0%B2]. |
| − | + | * Начнём в самой левой нижней вершине D. | |
| − | + | * Далее E, и их предок B. | |
| + | * Левое поддерево корня обошли, идём в правое: в F, далее в C. | ||
| + | * Остался корень A. | ||
| + | * Получили D-E-B-F-C-A. | ||
| − | [[Категория: | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 21:40, 19 декабря 2024 (UTC)}} |
| + | |||
| + | [[Категория:Алгоритмы на графах]] | ||
Текущая версия на 21:40, 19 декабря 2024
Вопрос: Q05-e5724f
Что из нижеперечисленного является обратным обходом [1] приведённого двоичного дерева?
A / \ B C /\ / D E F
Ответы
- ABCDEF
- ABDECF
- DBEACF
- Правильный ответ: DEBFCA
- DEFBCA
Объяснение
Исходники — вопрос 5 на 13 странице книги «2001-gre-vs-practice.pdf»
Давайте вручную обойдём дерево, как на примере [2].
- Начнём в самой левой нижней вершине D.
- Далее E, и их предок B.
- Левое поддерево корня обошли, идём в правое: в F, далее в C.
- Остался корень A.
- Получили D-E-B-F-C-A.