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

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

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

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

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

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

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

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

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

Под итерированием списка понимается:

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

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

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

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

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

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

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

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

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

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

Когда мы говорим, что язык программирования является языком со статической типизацией, то это означает:

Интегрированная среда разработки - ИСР EiffelStudio:

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

Укажите причины, по которым грамматика языка не использует правила БНФ для определения синтаксиса построения лексем?

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

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

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

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

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

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

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

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

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

Рассмотрим контейнерный класс, в котором метод вставки элементов put имеет следующую сигнатуру: put (key:STRING; i: G), где key - ключ элемента, i - сам элемент. Какие постусловия должны включаться для этого метода?

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

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

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

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

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

Какие утверждения справедливы для хеш-таблицы?

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

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

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

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

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

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

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

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

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

Что справедливо для закона Мура?

Какие преимущества дает схема двухэтапной компиляции?

В соответствии с определением бинарного дерева поиска для него справедливо?

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

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

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

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

Необходимыми условиями корректно определенного рекурсивного метода является существование у метода ветви без рекурсии и разные контексты у каждого рекурсивного вызова. Рассмотрим метод с циклом: cicle do from Init until Exit loop Body end endЗаменим его методом recursive do Init; loop_eqviv end с вызовом рекурсивного метода: loop_eqviv do if not Exit then Body; loop_eqviv end endКакие утверждения справедливы относительно корректности такой замены?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Классы ARRAY и LIST являются универсальными классами с одним родовым параметром. Класс STUDENT является обычным классом. Какие объявления являются корректными в языке Eiffel?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим два фрагмента программ: -- fragment 1from x := low until x >= high loop Result := Result + f(x) x := x + stepend -- fragment 2 from x := low; i := 0 until x >= high loop Result := Result + f(x) i := i + 1; x := low + i * stepend Какие высказывания справедливы для этих фрагментов?

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

Гибибайт (GiB) - это?

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

Рассмотрим игру, в которой применяется минимаксная стратегия. Напомним, это означает, что в игре участвуют два противника, поочередно выполняющие ходы. Существует оценочная функция, которая выдает оценку (число) для каждой позиции после очередного хода. Положительное значение этой оценки рассматривается как выигрыш для одного игрока и как проигрыш для другого (игра с нулевой суммой). Рассмотрим дерево конкретной игры, в узлах которого записываются оценки позиций. Дерево зададим скобочной записью: (((5, 3) (6, -1, 8))((10, 6, 2) (-2, -4, -7)) ) Здесь цифры, заключенные в скобки - это оценки в листьях, принадлежащих одному родителю. Игрок на нижнем уровне выбирает минимальную оценку. Каково значение цены игры для этого дерева?