игра брюс 2048
Главная / Программирование / Инструменты, алгоритмы и структуры данных / Тест 10

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

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

Ответ:

 (1) (Ласкер, Ботвинник, Капабланка, Алехин, Фишер) 

 (2) (Ботвинник, Капабланка,Ласкер, Фишер, Алехин) 

 (3) (Ласкер, Алехин, Ботвинник, Фишер, Капабланка) 

 (4) (Ласкер, Алехин, Капабланка, Ботвинник, Фишер) 

 (5) (Ласкер, Ботвинник, Алехин, Капабланка, Фишер) 

 (6) (Ласкер, Ботвинник, Капабланка, Алехин, Фишер) 

Номер 2 
На теннисном турнире Уимблдон 2011 Федерер проиграл Тсонга, Томич - Джоковичу, Лопес - Маррею, Фиш - Надалю. В полуфиналах Джокович выиграл у Тсонга, а Надаль - у Маррея. Финал выиграл Джокович. Полагая, что проигрыш рассматривается как предшествование, по результатам встреч этих 8 спортсменов укажите, сколько можно построить различных топологически отсортированных последовательностей?

Ответ:

 (1) 1 

 (2) 8 

 (3) 16 

 (4) 24 

 (5) 36 

 (6) 48 

 (7) 64 

Номер 3 
Какие утверждения справедливы относительно понятия "отношение"?

Ответ:

 (1) если два объекта некоторого множества не могут взаимодействовать друг с другом из-за плохих отношений между ними, то это означает, что они находятся в бинарном отношении 

 (2) бинарным отношением на множестве math называют некоторое подмножество пар объектов math этого множества 

 (3) можно обобщить определение бинарного отношения, распространив его на множество пар math, где первый элемент пары принадлежит множеству А, а второй - множеству math 

 (4) можно обобщить определение отношения на множестве math, заменив пару элементов кортежом math, где каждый элемент math принадлежит множеству math. Такое отношение называется n - арным или отношением арности n на множестве math 

 (5) если пара math принадлежит отношению, то пара math не может принадлежать этому отношению 

Упражнение 2:
Номер 1 
Какими свойствами обладает отношение строгого порядка? Отношение строгого порядка:

Ответ:

 (1) транзитивно 

 (2) симметрично 

 (3) асимметрично 

 (4) рефлексивно 

 (5) антирефлексивно 

Номер 2 
Какими свойствами обладает отношение строгого полного (тотального) порядка на множестве math? Отношение полного строгого порядка:

Ответ:

 (1) транзитивно 

 (2) симметрично 

 (3) асимметрично 

 (4) рефлексивно 

 (5) антирефлексивно 

 (6) для любой пары math из math либо math, либо math принадлежит отношению 

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

Ответ:

 (1) Алехин проиграл Фишеру, но выиграл у Ласкера. Ботвинник проиграл Капабланке, но также выиграл у Ласкера 

 (2) Алехин проиграл Фишеру, но выиграл у Ласкера. Ботвинник проиграл Капабланке, но также выиграл у Ласкера, который в свою очередь выиграл у Капабланки 

 (3) Алехин проиграл Фишеру, но выиграл у Ласкера. Ботвинник проиграл Капабланке, но также выиграл у Ласкера. Капабланка проиграл Фишеру 

 (4) Алехин проиграл Фишеру, но выиграл у Ласкера. Ботвинник проиграл Капабланке, но также выиграл у Ласкера. Капабланка выиграл у Фишера, но проиграл Алехину 

 (5) Алехин проиграл Фишеру, но выиграл у Ласкера. Ботвинник проиграл Капабланке, но также выиграл у Ласкера. Фишер проиграл Капабланке 

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

Ответ:

 (1) топологическая сортировка определена для ациклического отношения 

 (2) для заданного на конечном множестве ациклического отношения r топологическая сортировка состоит в построении полного порядка на множестве, для которого отношение r является подмножеством 

 (3) пусть для ациклического отношения построена топологически отсортированная последовательность math. Тогда для любого элемента math найдется в последовательности такой элемент math, что пара math принадлежит отношению 

 (4) перечисление math задает топологическую сортировку для заданного на конечном множестве ациклического отношения r, если никакая пара math, где math, не принадлежит отношению r 

 (5) пусть для ациклического отношения построена топологически отсортированная последовательность math. Тогда для любого элемента math либо пара math, либо пара math принадлежит отношению 

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

Ответ:

 (1) перечисление math топологически отсортировано для отношения r, если для любого элемента перечисления math не существует math, где math, такого, что пара math принадлежит r 

 (2) для перечисления math, задающего топологическую сортировку, для любого элемента перечисления math существует элемент math, являющийся предшественником math в отношении r 

 (3) каждое перечисление math задает полный порядок. Пара math принадлежит этому порядку, если math 

 (4) перечисление math задает топологически отсортированную последовательность для отношения math, если каждая пара из math содержится в множестве пар полного порядка, определенного перечислением 

Номер 3 
Рассмотрим конечное множество из пяти элементов. Пусть на этом множестве задано отношение r, содержащее только одну пару элементов. Сколько различных топологически отсортированных отношением   r последовательностей можно построить?

Ответ:

 (1) 5 

 (2) 10 

 (3) 16 

 (4) 60 

 (5) 120 

 (6) 128 

Упражнение 4:
Номер 1 
Рассмотрим некоторые задачи. Какие отношения, введенные в этих задачах, являются ациклическими?

Ответ:

 (1) в групповых турнирах спортсмены встречаются между собой. Пара спортсменов math принадлежит отношению math, если спортсмен math выиграл у спортсмена g 

 (2) в олимпийских играх спортсмен после проигрыша выбывает из турнира. Пара спортсменов math принадлежит отношению math, если спортсмен math выиграл у спортсмена g 

 (3) на множестве исторических событий можно ввести отношение "предшествует". Пара событий math принадлежит отношению math, если событие math предшествует по времени событию g 

 (4) при сборке изделий (автомобиля, самолета, корабля) детали изделия собираются из других деталей, так что естественным образом вводится отношение "является частью". Пара деталей math принадлежит отношению r, если деталь math является частью детали g 

 (5) в языках программирования, таких как Eiffel, в теле метода может быть вызван другой метод, так что естественным образом вводится отношение "вызывает". Пара методов math принадлежит отношению r, если метод math вызывает метод math 

Номер 2 
Рассмотрим множество А из пяти элементов. Из какого числа пар состоит множество, задающее строгий полный порядок на А?

Ответ:

 (1) 5 

 (2) 10 

 (3) 16 

 (4) 25 

Номер 3 
Какие утверждения справедливы для ациклического отношения и отношения порядка?

Ответ:

 (1) любое отношение порядка ациклично 

 (2) любое подмножество отношения порядка ациклично 

 (3) любое ацикличное отношение является отношением порядка 

 (4) транзитивное замыкание ацикличного отношения является отношением порядка 

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

Ответ:

 (1) отношение порядка 

 (2) ациклическое отношение 

 (3) полное отношение порядка 

 (4) произвольное отношение, заданное множеством пар с возможными повторами и циклами 

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

Ответ:

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

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

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

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

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

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

Ответ:

 (1) теоретически невозможно построить алгоритм временная и емкостная сложность которого была бы ниже чем O(n + m), где n - это число сортируемых элементов, m - число ограничений 

 (2) практически невозможно построить алгоритм временная и емкостная сложность которого была бы O(n + m), где n - это число сортируемых элементов, m - число ограничений 

 (3) практически возможно построить алгоритм временная и емкостная сложность которого была бы O(n + m), где n - это число сортируемых элементов, m - число ограничений 

 (4) практически возможно построить алгоритм временная и емкостная сложность которого была бы O(n) независимо от m, где n - это число сортируемых элементов, m - число ограничений.  

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

Ответ:

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

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

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

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

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

Ответ:

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

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

 (3) удалить элемент x 

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

Номер 3 
Какие утверждения справедливы относительно представления исходных данных задачи?

Ответ:

 (1) исходные данные для задачи должны представляться пользователем в форме, естественной для этой задачи и удобной для ввода данных 

 (2) исходные данные для задачи должны представляться пользователем в форме, удобной для их обработки алгоритмом, чтобы обеспечить лучшие характеристики временной и емкостной сложности 

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

 (4) исходные данные для задачи после их ввода не могут обрабатываться транслятором данных, поскольку транслятор может только транслировать только тексты программ, но не данные 

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

Ответ:

 (1) элементы должны иметь тип INTEGER 

 (2) элементы должны иметь арифметический тип 

 (3) элементы должны иметь арифметический или строковый тип 

 (4) тип элементов должен допускать хеширование 

 (5) допускается любой тип элементов 

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

Ответ:

 (1) всегда 

 (2) только тогда, когда время, затрачиваемое на трансляцию по порядку меньше времени, затрачиваемого алгоритмом на обработку данных, полученных в результате трансляции 

 (3) тогда, когда суммарное время, затрачиваемое на трансляцию и на обработку данных, полученных в результате трансляции, меньше времени работы алгоритма на исходных данных, не прошедших трансляцию 

 (4) когда на одних и тех же исходных данных задачу приходится решать многократно, а трансляцию данных нужно выполнять только один раз 

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

Ответ:

 (1) стек 

 (2) очередь 

 (3) хеш-таблицу 

 (4) очередь с приоритетами 

 (5) список 

 (6) массив 

Упражнение 8:
Номер 1 
Какие утверждения являются справедливыми?

Ответ:

 (1) хорошее инженерное решение в задаче о топологической сортировке должно отвергать ошибочные исходные данные, содержащие цикл 

 (2) ключом эффективности алгоритма является построение структур данных, специально приспособленных для решения задач сортировки 

 (3) память и время выполнения алгоритма топологической сортировки имеют порядок math, где math - число элементов, math - число ограничений 

 (4) трансляция исходных данных в форму, требуемую алгоритму топологической сортировки для его эффективной работы, требует времени math 

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

Ответ:

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

 (2) клиент класса может при постановке задачи записывать элементы и ограничения в удобной для клиента форме 

 (3) клиент класса может получить решение задачи, вызвав метод сортировки 

 (4) клиент класса может выяснить, существуют ли циклы, и, если да, получить список элементов, входящих в цикл 

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

 (6) клиент класса может получить в процессе сортировки от каждого экземпляра класса чашечку кофе 

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

Ответ:

 (1) топологическая сортировка является перечислением множества элементов, совместимого с множеством ограничений, задающих отношение порядка 

 (2) построенная реализация алгоритма требует, чтобы ограничения задавали отношение порядка 

 (3) построенная реализация алгоритма не требует даже, чтобы ограничения задавали ациклическое отношение 

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

Упражнение 9:
Номер 1 
В контекст рекурсивного метода, дающего решение задачи о Ханойской башне, входят 5 величин - 4 аргумента метода (имена трех башен и число переносимых дисков) и одна локальная переменная. Сколько величин достаточно сохранять в записи активации при оптимальной реализации рекурсивного метода?

Ответ:

 (1) 1 

 (2) 2 

 (3) 3 

 (4) 4 

 (5) 5 



Главная / Программирование / Инструменты, алгоритмы и структуры данных / Тест 10