Инструменты, алгоритмы и структуры данных

<<- Назад к вопросам

Какие утверждения справедливы о числе решений в задаче о топологической сортировке?

(Ответ считается верным, если отмечены все правильные варианты ответов.)

Варианты ответа

решений, удовлетворяющих задаче, всегда не менее n, где n-число элементов сортируемого множества

задача может не иметь решения, не построив ни одной отсортированной последовательности(Верный ответ)

задача может иметь ровно одно решение(Верный ответ)

решений, удовлетворяющих задаче, может быть несколько(Верный ответ)

решений, удовлетворяющих задаче, может быть не более n, где n-число элементов сортируемого множества

Похожие вопросы

Какие утверждения справедливы о сложности решения задачи о топологической сортировке?

Какие утверждения не справедливы для класса, спроектированного в ходе решения задачи о топологической сортировке?

Укажите, какие утверждения справедливы для топологической сортировки:

Структуры данных, используемые в алгоритме топологической сортировки, работают не с самими элементами множества, а с их номерами. Какие утверждения справедливы относительно возможного типа сортируемых элементов в предлагаемой реализации алгоритма?

"Инженерное" решение задачи о топологической сортировке, применимое в различных проблемных областях, предполагает, что на входе множество ограничений задает:

Пять великих шахматистов прошлых лет встретились и сыграли между собой несколько партий. Алехин проиграл Фишеру, но выиграл у Ласкера. Ботвинник проиграл Капабланке, но также выиграл у Ласкера? Полагая, что проигрыш рассматривается как предшествование, укажите, какие последовательности соответствуют топологической сортировке игроков по результатам этих встреч?

Пусть для конечного множества элементов $A ={a_1, a_2,… a_n}$ задано ациклическое отношение r множеством пар [a_k, a_j]

, принадлежащих отношению. На множестве А можно построить n! различных последовательностей этих элементов - перечислений элементов. Какие утверждения справедливы относительно этих перечислений и их топологической отсортированности?

При выполнении рекурсивного метода создаются экземпляры метода, каждому из которых требуется информация, характеризующая данный экземпляр. Число экземпляров может быть большим, так, например, в задаче о Ханойской башне при n, равном, двадцати, более миллиона одновременно существующих экземпляров. Какие утверждения справедливы относительно способов представления информации, необходимой экземпляру метода?

Какие утверждения справедливы?

Какие утверждения справедливы для курсора?