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

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

Какие операции можно считать базисными для алгоритма построения топологической сортировки?

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

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

удалить из множества ограничений пары, в которых элемент x стоит на первом месте(Верный ответ)

построить транзитивное замыкание множества ограничений

найти элемент x, не имеющий предшественников или сообщить, что такого элемента нет(Верный ответ)

удалить элемент x(Верный ответ)

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

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

Реализация алгоритма топологической сортировки включала такой прием, как предварительная трансляция исходных данных в форму, удобную для эффективной реализации алгоритма. Что справедливо о применении этого приема в других программистских задачах? Этот прием следует применять:

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

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

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

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

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

Для оценки качества алгоритма принято использовать абстрактную сложность алгоритма, не связанную с его реализацией. Чаще всего используют две меры сложности - временную и емкостную, характеризующие время работы алгоритма и память, требуемую для его работы. Укажите утверждения, справедливые для абстрактной сложности алгоритма:

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

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

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