2011-gre-cs-practice-book.pdf/Q30 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 33: | Строка 33: | ||
{{cstest-source|2011-gre-cs-practice-book.pdf|29|30}} | {{cstest-source|2011-gre-cs-practice-book.pdf|29|30}} | ||
| − | * Начнём с конца, с вершины, из которой нет ни одного исходящего ребра. Она здесь единственная, это 30. | + | * Начнём с конца, с вершины, из которой нет ни одного исходящего ребра. Она здесь единственная, это 30. |
| − | * Далее можно пойти либо в 7, либо в 20. | + | * Далее можно пойти либо в 7, либо в 20. |
| − | * Но из 20 можно попасть 7, значит эта вершина стоит раньше. | + | * Но из 20 можно попасть 7, значит эта вершина стоит раньше. |
| − | * Тогда идем выбираем 7. | + | * Тогда идем выбираем 7. |
| − | * Та же дилемма между 14 и 17. Видно, что из 14 можно попасть в 17, но не наоборот. | + | * Та же дилемма между 14 и 17. Видно, что из 14 можно попасть в 17, но не наоборот. |
| − | * Пойдём так дальше до 13. Получили 13-14-7-30. | + | * Пойдём так дальше до 13. Получили 13-14-7-30. |
| − | * Из 13 опять | + | * Из 13 опять вилка — либо 5, либо 17. Но 5 идет раньше 17, поэтому получим 5-17-13-14-7-30. |
| − | * Далее очевидный выбор между 10 и 20. | + | * Далее очевидный выбор между 10 и 20. |
* Получили 10-20-5-17-13-14-7-30. | * Получили 10-20-5-17-13-14-7-30. | ||
Версия 19:22, 19 декабря 2024
Вопрос: 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.
- Та же дилемма между 14 и 17. Видно, что из 14 можно попасть в 17, но не наоборот.
- Пойдём так дальше до 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.