База ответов ИНТУИТ

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

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

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

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

Варианты ответа
пусть для ациклического отношения построена топологически отсортированная последовательность a_1, a_2,… a_n. Тогда для любого элемента a_k найдется в последовательности такой элемент a_j (j>k), что пара [a_j, a_k] принадлежит отношению
для заданного на конечном множестве ациклического отношения r топологическая сортировка состоит в построении полного порядка на множестве, для которого отношение r является подмножеством(Верный ответ)
топологическая сортировка определена для ациклического отношения(Верный ответ)
пусть для ациклического отношения построена топологически отсортированная последовательность a_1, a_2,… a_n. Тогда для любого элемента a_k либо пара [a_k, a_{к+1}], либо пара [a_{k+1},a_k] принадлежит отношению
перечисление a_1, a_2,… a_n задает топологическую сортировку для заданного на конечном множестве ациклического отношения r, если никакая пара [a_j, a_k], где j>k, не принадлежит отношению r(Верный ответ)
Похожие вопросы
Структуры данных, используемые в алгоритме топологической сортировки, работают не с самими элементами множества, а с их номерами. Какие утверждения справедливы относительно возможного типа сортируемых элементов в предлагаемой реализации алгоритма?
Какие утверждения справедливы о сложности решения задачи о топологической сортировке?
Какие утверждения справедливы о числе решений в задаче о топологической сортировке?
Какие утверждения не справедливы для класса, спроектированного в ходе решения задачи о топологической сортировке?
Какие операции можно считать базисными для алгоритма построения топологической сортировки?
Пусть для конечного множества элементов A ={a_1, a_2,… a_n} задано ациклическое отношение r множеством пар [a_k, a_j], принадлежащих отношению. На множестве А можно построить n! различных последовательностей этих элементов - перечислений элементов. Какие утверждения справедливы относительно этих перечислений и их топологической отсортированности?
Предлагаемый алгоритм топологической сортировки позволяет построить последовательность, упорядоченную по возрастанию - элементы в последовательности расположены в соответствии с их предшествованием. Пусть требуется строить последовательность, упорядоченную по убыванию, где элементы расположены в порядке следования. Какие стратегии может применять программист?
Какие утверждения справедливы?
Какие утверждения справедливы для контейнеров?
Какие утверждения справедливы для курсора?