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

17.10.2015 Вопросы Комментарии отключены

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

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

В привычном для нас мире десятичной системы счисления незыблемой истиной считается, что 2 * 2 = 4. В двоичной системе счисления такая запись просто невозможна, поскольку нет ни цифр 2, ни 4. А в какой системе счисления с основанием p справедлива запись 2 * 2 = 11?

Какое утверждение справедливо о выполнении в компьютере арифметических операций (сложение, вычитание, умножение) над вещественными числами?

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

Выполнение в компьютере арифметических операций (сложение, вычитание, умножение) над целыми числами:

Компьютер выполнил сложение двух чисел в двоичной системе 1010 + 11011, и результат вывел на печать в привычной для нас десятичной системе. Чему равен результат?

RAM -память со случайным доступом это:

В некоторых первых компьютерах использовалась привычная для человека десятичная система счисления. Кнут в своем знаменитом труде «Искусство программирования» рассматривал машину MIX, работавшую в троичной системе. В Советском Союзе в МГУ под руководством профессора Брусенцова была построена и успешно работала троичная машина «Сетунь». Сегодня все компьютеры используют только двоичную систему, в которой данные представляются последовательностями битов. Укажите причины, сделавшие двоичную систему столь популярной при построении компьютеров?

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

Компьютер выполнил умножение двух чисел в двоичной системе 1010 * 11011, и результат вывел на печать в привычной для нас десятичной системе. Чему равен результат?

Представление вещественного числа в памяти компьютера состоит из нескольких частей. Какая часть не входит в это представление?

Для современных настольных компьютеров примерно во сколько раз скорость доступа к регистрам превышает скорость доступа к дискам?

Команда сложения 32-х битного процессора PowerPC выполняет операцию над данными, которые?

Какие определения применяются по отношению к памяти?

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

Какие типы данных можно использовать в языке Eiffel для сущностей, представляющих тексты?

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

Будем полагать, что поезд — это локомотив, за которым следует один или несколько вагонов. Какая грамматика, корректно описывающая понятие «поезд» является регулярной и использует одно регулярное выражение?

Вершинный (начальный, основной) символ грамматики это:

Какой тип языков по классификации Хомского задают БНФ грамматики?

Чем отличается регулярная грамматика от грамматики БНФ?

БНФ-Е — это вариант БНФ, используемый при описании грамматики Eiffel. Какой вид продукций не применяется в БНФ-Е?

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

Правила БНФ будем называть продукциями. Какие утверждения справедливы для продукций?

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

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

Какая часть не является частью грамматики языка, описывающей синтаксис с помощью БНФ?

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

Какие высказывания являются корректными по отношению к понятию грамматики языка программирования?

Будем полагать, что поезд — это локомотив, за которым следует один или несколько вагонов. Какая грамматика корректно описывающая понятие «поезд» является рекурсивной?

Какое из высказываний является некорректным по отношению к понятиям языка программирования и его грамматики?

Какой символ не принадлежит к символам метаязыка БНФ?

Будем полагать, что поезд — это локомотив, за которым следует один или несколько вагонов. Какие грамматики корректно описывают понятие «поезд»?

Какие высказывания справедливы для продукций в БНФ-Е?

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

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

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

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

Какие утверждения справедливы по отношению к числу проходов компилятора?

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

Укажите, на каких этапах работы компилятора идет работа с абстрактным или конкретным синтаксическим деревом?

За 55 лет, прошедших с момента появления первого языка программирования, создано большое число языков, точного числа которых никто не знает. Языки программирования могут отличаться по многим критериям. Укажите критерий, который не применяется при сравнении языков программирования?

За 55 лет, прошедших с момента появления первого языка программирования, создано большое число языков, точного числа которых никто не знает. Языки программирования могут отличаться по многим критериям. Укажите критерии, которые применяются при сравнении языков программирования?

Историю программирования и людей, делающих эту историю, следует знать. Укажите авторов первого объектно-ориентированного языка Симула?

Для поддержки процесса проектирования, как промышленных изделий, так и программных продуктов, создается специальный инструментарий — мощные программные системы. Какой инструментарий в первую очередь следует выбрать программисту, создающему прикладное ПО на языке C#?

Укажите свойства, характерные для процедурного стиля программирования?

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

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

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

Какие утверждения справедливы для JIT(Just In Time) — компилятора?

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

Скомпонованной, загруженной на выполнение программе требуется инструментальная поддержка и в период выполнения. Поэтому над операционной системой создается специальная надстройка, называемая исполняемой средой или системой времени выполнения (runtime system). Какие функции выполняет эта система?

Укажите, как осуществляется сборка в среде EiffelStudio?

Укажите корректные высказывания:

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

При компоновке системы командой make системы Unix описание компоновки задается с помощью зависимостей вида target: source1, …, source. Данная зависимость говорит, что цель target зависит от нескольких источников. Укажите, в каких случаях зависимость будет применяться, перестраивая цель target?

При обсуждении конфигурации сборки рассматриваются три измерения, приводящие к проблемам. Какое четвертое измерение при этом не рассматривается?

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

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

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

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

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

Что не может делать компилятор языка Eiffel, входящий в EiffelStudio:

Команда Make операционной системы Unix, разработанная более 30 лет назад, является классическим примером инструментария, позволяющего автоматизировать процесс сборки программной системы. Какие выражения справедливы для файла, называемого makefile, задающего описание сборки?

Укажите корректные высказывания:

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

Система управления версиями является частью общей системы управления проектом. На примере системы ORIGO укажите возможные свойства таких систем:

Большинство контейнерных классов имеют общие для всех запросы. Укажите, какое из приведенных выражений не является запросом?

Гарри Поттер ищет важную для него информацию. Он надеется, что она может быть в одной из книг библиотеки Хогварда, содержащей книг. Гарри наугад выбирает книгу и просматривает ее содержимое, на что у него уходит минут. При неудаче он повторяет поиск, выбирая новую книгу. Для такого алгоритма поиска каковы значения времени поиска: минимальное, максимальное, в среднем?

При решении одной и той же задачи можно использовать разные алгоритмы. На практике часто важно, сколько времени и сколько памяти требуется для решения этой задачи. Понятно, что эти характеристики зависят от входных данных, которые определяют «размер» задачи. Для контейнеров естественным «размером» может служить n- число элементов, хранимых в контейнере. Самый простой путь определения для алгоритма характеристик требуемой памяти и времени — это проведение экспериментов и вычисление характеристик на основе наблюдений с последующим усреднением данных. Укажите утверждения, корректные относительно данного способа вычисления характеристик алгоритма:

Классы и типы это близкие понятия. Какое утверждение, связанное с этими понятиями, не является справедливым?

Какие утверждения справедливы относительно имен методов для контейнерных классов, включенных в библиотеки классов EiffelStudio?

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

В языке Eiffel для работы с массивами используется библиотечный класс ARRAY, являющийся универсальным классом. Какие объявления массивов являются корректными, полагая, что существуют классы INTEGER, REAL, STUDENT?

Контейнерные классы задают некоторое хранилище элементов. Как всякая структура данных, контейнер содержит в процессе работы конечное число элементов. Укажите утверждение, справедливое по отношению размера контейнеров:

В классе ARRAY для чтения элемента массива существует запрос item(i:INTEGER), для записи — команда put(v: like item; i: INTEGER). Какое предусловие задается для item и put?

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

Какие операции недоступны при работе с кортежами в языке Eiffel:

Укажите корректные высказывания для кортежей в языке Eiffel:

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

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

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

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

Пусть задано объявление объекта кортежного типа: stud1:TUPLE[who: STUDENT; facultet: STRING; group: INTEGER), пусть также уже создан объект petrov класса STUDENT. Укажите корректные фрагменты Eiffel кода, полагая, что они записаны пв последовательном порядке:

Какие операции над связным списком из класса LINKED_LIST выполняются в среднем за время O(count)?

Укажите корректные высказывания для мультимассивных списков:

Какой из библиотечных классов Eiffel является родительским классом для всех библиотечных классов, задающих различные реализации списков?

Пусть объект your_list задает непустой список с курсором, элементы которого являются целыми числами. Какой из фрагментов кода задает итерирование списка, в результате которого значением переменной temp станет индекс первого в списке элемента со значением 5 или 0, если такового элемента в списке нет.

Дан список с курсором, в котором курсор установлен на некотором элементе списка. Каково минимальное число команд достаточно выполнить, чтобы стал истинным запрос after?

Пусть объект your_list задает непустой список с курсором, элементы которого являются целыми числами. Какой из фрагментов кода задает итерирование списка, в результате которого переменная temp содержит максимальный элемент списка.

Укажите корректные высказывания:

Какие операции над элементами списка имеют сложность O(1):

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

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

При реализации алгоритма обращения списка на том же месте, требующего O(count) времени, на каждом шаге цикла достаточно выполнить несколько операторов ссылочного присваивания. Сколько требуется операторов?

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

Дан список с курсором, в котором курсор установлен на некотором элементе списка. Какие две команды нужно выполнить, чтобы стал истинным запрос before?

Какие операции над элементами массива имеют сложность O(n):

Укажите правильные последовательности действий при вставке элемента в односвязный список класса LINKED_LIST при условии, что элемент вставляется после существующего в списке элемента, назовем его current:

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

Проведение экзамена можно рассматривать как работу с двумя контейнерами. В одном контейнере находятся студенты, сдающие экзамен, в другом — преподаватели кафедры (их может быть несколько), принимающие экзамен. В каких вариантах проведения экзамена контейнер «студент» можно отнести к распределителю, а контейнер «преподаватель» таковым не является?

Для эффективного использования памяти на одном массиве можно реализовать стеков:

Какими правилами можно характеризовать политику, применяемую для стеков:

Распределитель — это контейнер — структура данных, характеризуемая тем, что:

Что такое хеширование?

Какие утверждения справедливы для реализации очереди на массиве классом ARRAYED_QUEUE?

Эффективность работы с хеш-таблицами зависит от выбора хеш-функции (степени ее совершенства) и от способа разрешения конфликтов при совпадении значений. Укажите, как разрешаются конфликты в Eiffel библиотечном классе HASH_TABLE?

Пусть дано арифметическое выражение с бинарными операциями, записанное в обратной польской записи: «2 3 4 5 + * — 6 7 8 — * +». Для его вычисления используется стандартная техника со стеком операндов. Сколько раз при вычислении этого выражения будет выполняться операция put-записи операнда в стек?

Хеш-функция f(k) отображает множество ключей в целочисленный интервал: K -> [a, b]. Пусть ключами являются имена, которые должны отображаться в интервал [0, 9]. В качестве хеш-функции выберем функцию, которая вычисляет сумму позиций в алфавите кириллицы первой и последней буквы имени, прибавляет длину имени и вычисляет остаток от деления на 10 (взятие по модулю от длины интервала). Для имени Яша эта функция выдаст значение 7. Каково число коллизий возникнет при применении этой функции для следующих 10 имен: Анна, Инна, Нина, Ольга, Екатерина, Владимир, Владислав, Виктор, Михаил, Яков?

Пусть дано арифметическое выражение с бинарными операциями, записанное в обратной польской записи: «2 3 4 5 + * — 6 7 8 — * +». Для его вычисления используется стандартная техника со стеком операндов. Сколько раз при вычислении этого выражения будет выполняться операция item-чтения операнда из стека?

Проведение экзамена можно рассматривать как работу с двумя контейнерами. В одном контейнере находятся студенты, сдающие экзамен, в другом — преподаватели кафедры (их может быть несколько), принимающие экзамен. В каких вариантах проведения экзамена оба контейнера можно отнести к распределителям?

Укажите корректные высказывания:

Какие из структур данных относятся к распределителям?

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

Рассмотрим язык программирования с двумя операторами — присваивания и цикла. Присваивание рассматривается в классическом варианте variable := expression и считается терминальным, не определяемым далее понятием. Грамматика языка такова:

$\text{Оператор }\triangleq\text{ Присваивание | Цикл}\\ \text{Цикл }\triangleq \text{ until (Условие) Оператор}$

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

Преобразование рекурсивного определения в циклическое может быть не простой задачей. Зная рекурсивное решение задачи о Ханойской башне, укажите, какой первый ход следует сделать для произвольного значения n:

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

Рассмотрим игру, в которой применяется минимаксная стратегия. Напомним, это означает, что в игре участвуют два противника, поочередно выполняющие ходы. Существует оценочная функция, которая выдает оценку (число) для каждой позиции после очередного хода. Положительное значение этой оценки рассматривается как выигрыш для одного игрока и как проигрыш для другого (игра с нулевой суммой). Рассмотрим дерево конкретной игры, в узлах которого записываются оценки позиций. Дерево зададим скобочной записью:

(((5, 3) (6, -1, 8))((10, 6, 2) (-2, -4, -7)) )

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

Что можно определить рекурсивно?

Сколько времени понадобится вашему персональному компьютеру для решения задачи о «ханойской башне» в ее оригинальном варианте с 64 дисками (для корректности постановки будем полагать, что ваш ПК хотя и не является суперкомпьютером, но способен выполнить за секунду 1 миллиард переносов дисков)?

Пусть — полное бинарное дерево (каждый узел не являющийся листом дерева имеет двух потомков) число листьев в котором равно . Для обхода дерева применяется инфиксная процедура обхода (обойти левое дерево, обойти корень, обойти правое дерево). Каким по счету будет посещен корень дерева, если счет узлов начинается с 1)?

Рекурсивное определение напоминает фокус. Рассмотрим рекурсивное определение известной в математике функции:

$F(n) = n – 10,\text{ если }n > 100\\ F(n) = F(F(n + 11),\text{ если }n <= 100$

Совершенно очевидно, какие значения принимает эта функция при n< 101 ? Оказывается, для таких функция имеет одно и то же значение. Какое?

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

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

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

Рассмотрим игру, в которой применяется минимаксная стратегия. Напомним, это означает, что в игре участвуют два противника, поочередно выполняющие ходы. Существует оценочная функция, которая выдает оценку (число) для каждой позиции после очередного хода. Положительное значение этой оценки рассматривается как выигрыш для одного игрока и как проигрыш для другого (игра с нулевой суммой). Зададим дерево конкретной игры, в узлах которого записаны оценки позиций. Дерево зададим скобочной записью:

( ((5, 3) (6, -1, 8)) ((10, 6, 2) (-2, -4, -7)) )

Здесь цифры, заключенные в скобки — это оценки в листьях, принадлежащих одному родителю. Игрок на нижнем уровне выбирает минимальную оценку. При вычислении цены игры применяется альфа-бета стратегия отсечения вариантов. Сколько вариантов (в данном случае листьев дерева) будет отсечено при применении этой стратегии?

Пусть разыскивается путь в графе. Содержательно можно рассматривать города, соединенные сетью дорог. Задача состоит в том, чтобы найти путь из города А в город В. Для поиска пути применяется алгоритм перебора с возвратами, реализованный в виде процедуры поиска find(path), где path — это построенный путь, начинающийся в городе А и заканчивающийся приходом в некоторый ранее не встречавшийся на построенном пути город N. Из города N дороги ведут в n городов — , не вошедшие в путь path. Какие утверждения справедливы для процедуры поиска?

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

Представим себе, что при определении ссылочного класса PERSON заданы два атрибута (поля класса) mother и father класса PERSON. Какие утверждения справедливы относительно порождения объектов этого класса?

Пусть разыскивается путь в графе. Содержательно можно рассматривать города, соединенные сетью дорог. Задача состоит в том, чтобы найти путь из города А в город В. Для поиска пути применяется алгоритм перебора с возвратами, реализованный в виде процедуры поиска find(path), где path — это построенный путь, начинающийся в городе А и заканчивающийся приходом в некоторый ранее не встречавшийся на построенном пути город N. Из города N дороги ведут в n городов — , не входящие в путь path. Какие утверждения справедливы относительно вызовов процедуры поиска?

Для каких понятий нельзя дать корректного рекурсивного определения?

Напомним, что идентификатором называется любая последовательность букв, цифр и символа подчеркивания, начинающаяся с буквы. Заметьте, это определение не рекурсивно. Какие из БНФ определений идентификатора являются корректными рекурсивными определениями?

Как выглядит граф функции «91», придуманной Маккарти?

Рекурсивное определение можно рассматривать как уравнение неподвижной точки . Пусть функция является решением этого уравнения. Какие утверждения справедливы для этой функции?

Каким свойством не обладает корректно определенный рекурсивный метод?

Рекурсивное определение функции можно рассматривать как уравнение неподвижной точки . Какие утверждения справедливы для этого уравнения?

Пусть метод p вызывает метод q, тот вызывает метод r с косвенной рекурсией, — метод r вызывает метод s, который в свою очередь вызывает метод r. Какие утверждения справедливы относительно процесса вызова методов?

В контекст рекурсивного метода, дающего решение задачи о Ханойской башне, входят 5 величин — 4 аргумента метода (имена трех башен и число переносимых дисков) и одна локальная переменная. При оптимальной реализации рекурсивного метода достаточно сохранять в записи активации?

Все рекурсивные вызовы в рекурсивном методе должны отличаться контекстом вызова — это необходимое условие корректно определенного рекурсивного метода. А что определяет контекст вызова?

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

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

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

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

Какие свойства являются необходимыми свойствами корректного рекурсивного метода?

Пусть членами семьи являются муж, жена, их родители и их дети. Определим рекурсивно понятие родственника. Члены семьи являются родственниками — родственниками уровня 0. Это не рекурсивная ветвь определения. Определим теперь рекурсивно понятие родственника — родственника некоторого уровня. Некто N является родственником уровня , если он не является родственником уровня k или более низкого уровня, но является родственником уровня 0 любого из родственников уровня k. К какому уровню по отношению к Вам относится внук брата дедушки?

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

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

Пусть аргументом функции является множество пар целых чисел. Пусть также функция :

добавляет в множество пару [0,0];
если в множестве есть пара и , то в множество добавляется пара

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

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

Какие свойства справедливы для варианта рекурсивного метода

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть для конечного множества элементов $A ={a_1, a_2,… a_n}$ задано ациклическое отношение r множеством пар , принадлежащих отношению. На множестве А можно построить n! различных последовательностей этих элементов — перечислений элементов. Какие утверждения справедливы относительно этих перечислений и их топологической отсортированности?

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

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

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

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

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

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

Рассмотрим некоторые задачи. Какие отношения, введенные в этих задачах, являются ациклическими?

Какая из структур данных относится к распределителям с политикой «первым пришел, первым ушел»?

Comments are closed.