2011-gre-cs-practice-book.pdf/Q30 — различия между версиями
Материал из DISCOPAL
Urmat A (обсуждение | вклад) |
Urmat A (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
[[File:graph.png|480px]] | [[File:graph.png|480px]] | ||
| − | Что из перечисленного является топологической сортировкой вершин графа? | + | Что из перечисленного является топологической сортировкой вершин графа[https://habr.com/ru/companies/otus/articles/499138/]? |
=== Ответы === | === Ответы === | ||
| Строка 18: | Строка 18: | ||
{{cstest-source|2011-gre-cs-practice-book.pdf|29|30}} | {{cstest-source|2011-gre-cs-practice-book.pdf|29|30}} | ||
| − | + | Начнём с конца, с вершины, из которой нет ни одного исходящего ребра. Это 30. Далее можно пойти либо в 7, либо в 20. Но из 20 можно попасть 7, значит эта вершина стоит раньше. Тогда идем выбираем 7, пойдя дальше до 13. Получили 13-14-7-30. ИЗ 13 опять вилка - либо 5, либо 17. Но 5 идет раньше 17, поэтому получим 5-17-13-14-7-30. Далее очевидный выбор между 10 и 20. Получили 10-20-5-17-13-14-7-30. | |
{{question-ok|}} | {{question-ok|}} | ||
| + | {{checkme|[[Участник:Urmat A|Urmat A]] 15:45, 19 декабря 2024 (UTC)}} | ||
Версия 15:45, 19 декабря 2024
Задача зарезервирована: Urmat A 14:58, 19 декабря 2024 (UTC)
Вопрос: Q30-08c765
Дан ориентированный граф:
Что из перечисленного является топологической сортировкой вершин графа[1]?
Ответы
- 5, 7, 10, 13, 14, 17, 20, 30
- 10, 5, 13, 14, 7, 30, 17, 20
- 10, 5, 13, 17, 20, 14, 7, 30
- 10, 5, 20, 13, 17, 30, 14, 7
- Правильный ответ: 10, 20, 5, 17, 13, 14, 7, 30
Объяснение
Исходники — вопрос 30 на 29 странице книги «2011-gre-cs-practice-book.pdf»
Начнём с конца, с вершины, из которой нет ни одного исходящего ребра. Это 30. Далее можно пойти либо в 7, либо в 20. Но из 20 можно попасть 7, значит эта вершина стоит раньше. Тогда идем выбираем 7, пойдя дальше до 13. Получили 13-14-7-30. ИЗ 13 опять вилка - либо 5, либо 17. Но 5 идет раньше 17, поэтому получим 5-17-13-14-7-30. Далее очевидный выбор между 10 и 20. Получили 10-20-5-17-13-14-7-30.
Решено: Urmat A 15:45, 19 декабря 2024 (UTC)