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

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

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

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

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

возложить решение задачи на пользователя

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

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

не меняя исходных данных, изменить алгоритм, заменяя понятие "предшественника" понятием "последователь"(Верный ответ)

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

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

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

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

Пусть функция

является решением уравнения неподвижной точки F = h(F)

. Это позволяет дать не рекурсивное определение функции

, аналогично тому, как определяется предел последовательности. Рассмотрим последовательность графов и связанных с ними функций F_0, F_1, … , F_n

. Какие утверждения не являются справедливыми относительно такого определения

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

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

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

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

Рассмотрим рекурсивное определение понятия "идентификатор":

$\text{идентификатор }\triangleq\text{ буква | идентификатор буква | идентификатор цифра}$

Пусть алфавит языка содержит две буквы - x и y и одну цифру -1. Индуцируя построение идентификаторов в стиле неподвижной точки, на нулевом уровне можно построить два идентификатора в соответствии с нерекурсивной частью определения, а сколько идентификаторов можно построить, принадлежащих уровню 2:

Ограничители языка являются лексемами, у которых есть только единственный образец - сам ограничитель, в то время как у таких лексем как Целое или Идентификатор число образцов бесконечно. Укажите, какие элементы не может содержать продукция БНФ?

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