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

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

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

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

• такое определение, являясь рекурсивным, всегда порождает бесконечную цепочку объектов, каждый из которых ссылается на свою пару объектов mother и father
• такое определение, являясь рекурсивным, позволяет порождать конечную цепочку объектов, задавая генеалогическое древо до определенного уровня
• такое определение, являясь рекурсивным, будет порождать конечную цепочку объектов, заканчивающуюся парой объектов "ЕВА" и "АДАМ" - праматерью и праотцом
• такое определение, являясь рекурсивным, может и не порождать цепочки объектов, поскольку родители могут быть неизвестны или не указаны по каким либо причинам.
• возможное для ссылки значение void является по умолчанию частью рекурсивного определения любой рекурсивной ссылочной структуры данных, что позволяет создавать конечную структуру связанных ссылками объектов

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

• star :ARRAY[STUDENT]
• intar: ARRAY[INTEGER]
• rar :ARRAY[REAL][1,100]
• my_ar :INTEGER ARRAY[100]

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

• каждая продукция определяет одну нетерминальную категорию
• каждая нетерминальная категория определяется одной продукцией
• каждая продукция должна быть одного вида
• допускаются правила, состоящие из смеси продукций разного вида

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

• возможен анализ отношения клиент - поставщик, позволяющий выяснить для данного класса, какие классы являются его непосредственными клиентами, какие - клиентами. Поскольку отношение транзитивно, то можно анализировать эти связи на любом уровне
• возможен анализ отношения родитель - потомок, позволяющий выяснить для данного класса, какие классы являются его непосредственными родителями, какие - потомками. Поскольку отношение транзитивно, то можно анализировать эти связи на любом уровне
• возможен анализ отношения предпочтения (влюбленности), позволяющий выяснить для данного класса, каким классам нравится использовать данный класс, какие классы предпочитает анализируемый класс. Поскольку отношение транзитивно, то можно анализировать эти связи на любом уровне
• для наследуемого метода F можно выяснить, какой класс создал используемую версию метода F
• для наследуемого метода F можно выяснить, какой класс впервые создал версию метода F

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

• не меняя алгоритма, изменить исходные данные, меняя порядок следования в парах, задающих ограничения
• не меняя исходных данных, изменить алгоритм, заменяя понятие "предшественника" понятием "последователь"
• не меняя исходных данных и алгоритма, провести инверсию полученного результата
• возложить решение задачи на пользователя

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

• рекурсивные методы, такие как p и q, в цепочке вызовов, как правило, существуют в множестве экземпляров
• каждый метод в цепочке вызовов существует в единственном экземпляре
• когда при выполнении тела метода происходит вызов метода, то вызывающий метод приостанавливает свою работу до тех пор, пока не завершится вызванный им метод. Так создается цепочка вызовов методов
• рекурсивные методы, такие как p и q, в цепочке вызовов всегда существуют в множестве экземпляров
• нерекурсивные методы, такие как p и q, в цепочке вызовов существуют в единственном экземпляре

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

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

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

• проход по списку с выполнением некоторой операции над всеми элементами списка
• проход по списку с выполнением некоторой операции над элементом списка при условии, что для этого элемента выполняется некоторое условие
• проход по списку, пока не встретится элемент списка, для которого выполняется некоторое условие
• различные вариации циклической обработки элементов списка
• выполнение некоторой операции над элементами списка, стоящими слева и справа от курсора

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

• исходный код на языке Eiffel компилировать в машинный код
• исходный код на языке Eiffel компилировать в код на языке С для исполняемой среды Eiffel
• исходный код на языке Eiffel компилировать в промежуточный код на CIL для .Net исполняемой среды
• обнаружить синтаксические ошибки, не отвечающие синтаксису, заданному БНФ грамматикой
• обнаружить контекстно-зависимые ошибки, выполняя статический контроль типов и другие проверки

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

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

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

• CHARACTER
• STRING
• CHARACTER_8
• CHARACTER_32

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

• отношение порядка
• ациклическое отношение
• полное отношение порядка
• произвольное отношение, заданное множеством пар с возможными повторами и циклами

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

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

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

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

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

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

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

• temp: INTEGERyour_list.starttemp := your_list.itemfrom your_list.forthuntil your_list.afterloop temp := temp + your_list.item your_list.forthend
• temp: INTEGERyour_list.starttemp := your_list.itemfrom your_list.forthuntil your_list.afterloop if (temp < your_list.item) temp := your_list.item end your_list.forthend
• temp: INTEGERfrom temp := 0 your_list.startuntil your_list.afterloop if (your_list.item = 5) temp := your_list.index end your_list.forthend
• temp: INTEGERfinish: BOOLEANfrom your_list.start temp := 0 finish := FALSE until your_list.after or else finishloop if (your_list.item = 5) finish := TRUE temp:= your_list.index end your_list.forthend

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

• чтение значения элемента, зная его номер
• запись значения элемента, зная его номер
• вставка нового элемента в позицию, определяемую курсором
• удаление элемента в позиции, определяемой курсором

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

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

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

• при объявлении каждой сущности задается ее тип
• для каждого вызова x.f(p) тип сущности x компилятор определить не может, поскольку он определяется контекстом вызова, но тип может определить исполнительная система динамически в момент выполнения
• для каждого вызова x.f(p) компилятор может определитьтип сущности x
• для каждого вызова x.f(p) компилятор может определить тип сущности x, но он не может определить, обладает ли тип методом f
• для каждого вызова x.f(p) тип сущности x компилятор определить может, он может также определить, обладает ли тип методом f, но он не может определить, соответствуют ли по типу фактические аргументы вызова формальным аргументам метода f

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

• включает компилятор и интерпретатор языка Eiffel
• позволяет добавлять компилятор любого языка программирования
• включает Отладчик
• включает различный инструментарий: просмотра, документирования, метрических измерений, графического интерфейса
• является средой с открытым кодом

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

• любой регулярный язык может быть описан регулярной грамматикой
• регулярный язык может быть описан рекурсивной грамматикой
• регулярные языки поддерживают вложенность понятий
• регулярный язык может быть описан одним регулярным выражением

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

• правила БНФ не достаточно мощны для определения синтаксиса построения лексем
• причина прагматическая - удобнее иметь два уровня описания грамматики - лексический и синтаксический
• на лексическом уровне применяются более простые правила, задающие синтаксис построения лексем
• язык, предложениями которого являются лексемы, относится к простым языкам, для описания синтаксиса которых не требуется мощь БНФ

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

• 10
• 100
• 1000
• 1000000
• 10000000

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

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

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

• массив
• стек
• список
• очередь
• очередь с приоритетом
• хеш-таблица

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

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

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

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

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

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

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

• stud1:= TUPLE
• stud1:= [petrov, "computer science", 22]
• major : STUDENT; major := stud1.who
• stud1. group:= 32
• minor: STUDENT; minor := stud1

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

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

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

• класс TWO_WAY_LIST восстанавливает симметрию, - теперь каждый элемент списка имеет связь, как с правым, так и с левым соседом, если таковые существуют
• для двусвязного списка увеличивается расход памяти, поскольку число связей удваивается
• для двусвязного списка повышается эффективность ряда операций, например, операция перемещения курсора влево - back выполняется в двусвязном списке за время O(1), а не за время O(count), как в односвязном списке
• интерфейс команд и запросов у классов TWO_WAY_LIST и LINKED_LIST различен
• реализации команд и запросов, наследуемых от класса List, у классов TWO_WAY_LIST и LINKED_LIST одинаковы

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

• inserted: has(key)
• inserted: has(key, i)
• current: item(key) = i
• current: item(i) = key
• inserted: has(i)

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

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

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

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

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

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

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

• теорема
• аксиома
• определение, не включающее рекурсию
• определение, включающее рекурсию

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

• перенос с А на В
• перенос с А на С
• не имеет значения, куда переносить на А или на С
• если n - нечетно, то перенос на В, иначе перенос на С

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

• хеш-таблица - это контейнер - структура данных, подобная массиву, поскольку использует ключ для доступа к элементам, но в отличие от массива не накладывает столь жестких ограничений на ключ, который может быть элементом произвольного множества, например строкой, идентифицирующей элемент
• для работы с хеш-таблицами в Eiffel предлагается библиотечный класс HASH_TABLE, представляющий универсальный класс с двумя родовыми параметрами, характеризующими тип ключа и тип элемента
• как и для списков, для хеш-таблиц определено понятие курсора и операций, связанных с курсором
• операции вставки и удаления элементов для хеш-таблиц реализуются эффективнее, чем для массивов
• операции вставки и удаления элементов для хеш-таблиц реализуются эффективнее, чем для списков

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

• 1
• 2
• count
• count + 1
• count / 2

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

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

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

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

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

• JIT-компилятор - это компилятор, который в процессе двухэтапной компиляции используется на заключительном этапе
• JIT-компилятор - это компилятор с языка JIT в код целевой машины
• JIT компилятор - это компилятор, который при выполнении программы на целевой машине при первом вызове модуля компилирует виртуальный код модуля в машинный код целевой машины
• JIT-компилятор - это компилятор с языка Java в код целевой машины

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

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

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

• Джон Бэкус
• Фил Вадлер
• Уле Дал
• Кристин Нигард
• Алан Кей

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

• CADCAM
• VisualStudio
• EiffelStudio
• CASE

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

• лексемы, являющиеся ограничителями
• лексемы, являющиеся терминальными категориями, число образцов у которых бесконечно
• символы метаязыка БНФ
• символы праязыка БНФ
• нетерминальные категории

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

• грамматика языка задает описание его синтаксиса
• грамматика языка позволяет определить, какие предложения являются синтаксически правильными для этого языка
• грамматика языка позволяет определить, какие предложения являются семантически правильными для этого языка
• в роли элементарных единиц, из которых строятся предложения языка, выступают лексемы
• лексемы строятся из символов, составляющих алфавит языка

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

• закон Мура выполняется на новом уровне для многоядерных компьютеров
• закон Мура в том виде, каком его сформулировал Мур, уже не выполняется
• это такой же физический закон, как и закон Ньютона
• это эмпирическое наблюдение, справедливое в определенных временных рамках

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

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

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

• все элементы, хранимые в узлах дерева, различны
• для любых двух элементов, хранимых в узлах дерева, один из них "больше другого"
• максимальный элемент хранится в корне дерева
• максимальный элемент левого дерева меньше минимального элемента правого дерева

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

• FIFO - первый пришел - первый ушел
• LIFO - последний пришел - первый ушел
• LILO - последний пришел - последний ушел
• FILO - первый пришел - последний ушел

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

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

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

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

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

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

Необходимыми условиями корректно определенного рекурсивного метода является существование у метода ветви без рекурсии и разные контексты у каждого рекурсивного вызова. Рассмотрим метод с циклом: 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Какие утверждения справедливы относительно корректности такой замены?

• у метода loop_eqviv существует не рекурсивная ветвь. Когда выполняется условие выхода, то можно полагать, что выполняется ветвь без рекурсии (пустая в данном случае), завершающая выполнение метода
• контекст у рекурсивного метода меняется автоматически
• контекст каждого вызова будет меняться только при выполнении условий, предполагаемых по умолчанию для этой схемы замены цикла рекурсией: Все модули Init, Exit, Body определены над полями класса - глобальной для метода информацией;Init задает начальный контекст вызова;Каждое выполнение Body изменяет контекст и уменьшает значение варианта метода, гарантируя завершаемость.
• такая замена некорректна, поскольку не выполняется необходимое условие изменения контекста при каждом вызове рекурсивного метода
• завершаемость метода cicle гарантирует завершаемость метода loop_eqviv
• такая замена некорректна, поскольку не выполняется необходимое условие существования у рекурсивного метода не рекурсивной ветви

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

• иерархия памяти включает регистры, оперативную и постоянную память
• машинный код представляет систему команд компьютера - вычисления над операндами в регистрах, обмен данными между разными уровнями памяти, передачу управления командам
• внешняя память на порядок уступает оперативной памяти по скорости доступа, но на несколько порядков превосходит ее по объему хранимых данных
• поддержание выполнения закона Мура на новом уровне потребовало переход к многоядерной архитектуре и параллельному программированию

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

• инвариантом класса LINKED_QUEUE является утверждение, что курсор всегда указывает на последний элемент списка - начало очереди
• операция вставки put(x) в очередь реализуется за время O(1) выполнением одной операции над списком put_front(x), которая помещает элемент x в начало списка
• операция удаления элемента из очереди – remove выполняется за время O(count), поскольку требует перемещения по всему списку, чтобы удалить элемент, стоящий в конце списка
• операция удаления элемента из очереди - remove выполняется за время O(1), поскольку достаточно выполнить операцию remove для списка, удаляя элемент, на который указывает курсор списка

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

• память на регистрах
• память на дисках
• RAM - память
• FLASH - память

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

• стек
• очередь
• хеш-таблицу
• очередь с приоритетами
• список
• массив

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

• найти элемент x, не имеющий предшественников или сообщить, что такого элемента нет
• построить транзитивное замыкание множества ограничений
• удалить элемент x
• удалить из множества ограничений пары, в которых элемент x стоит на первом месте

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

• любое отношение порядка ациклично
• любое подмножество отношения порядка ациклично
• любое ацикличное отношение является отношением порядка
• транзитивное замыкание ацикличного отношения является отношением порядка

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

• для хранения всей информации, необходимой экземпляру метода, в момент его вызова создается специальная запись - запись активации, размещаемая в стеке. Когда экземпляр заканчивает свою работу, запись выталкивается из стека, освобождая память
• сократить объем данных, хранимых в записи активации, можно за счет увеличения времени работы метода, - когда экземпляру требуется некоторое данное, то можно вычислять его значение, не храня его в записи активации. Этот прием называется "вычислить, а не хранить"
• прием "вычислить, а не хранить" всегда применим
• сократить объем данных, хранимых в записи активации, можно за счет увеличения времени работы метода. Требуемое экземпляру данное следует хранить в поле класса -общей памяти всех экземпляров. Когда экземпляру требуется некоторое данное, то значение, хранимое в поле, преобразуется в соответствии с требованиями экземпляра. Когда экземпляр заканчивает свою работу, то выполняется "обратное преобразование", восстанавливающее исходное значение. Этот прием называется "преобразования в общей памяти"
• прием "преобразования в общей памяти" всегда применим

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

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

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

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

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

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

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

• fibonacci(n: INTEGER): INTEGER require positive: n >=0 do if n = 0 then Result := 1 elseif n = 1 then Result := 1 else Result := fibonacci(n-1); n := n-1; Result := Result + fibonacci(n-1); end end
• fibonacci(n: INTEGER): INTEGER require positive: n >=0do Result :=0 if n = 1 then Result := 1 else Result := fibonacci(n-1) + fibonacci(n-2); end end
• fibonacci(n: INTEGER): INTEGERrequire positive: n >=0 do if n = 0 then Result := 1 elseif n = 1 then Result := 1 else Result := fibonacci(n-2) + fibonacci(n-1); end end
• fibonacci(n: INTEGER): INTEGERrequire positive: n >=1 do if n = 1 then Result := 1 elseif n = 2 then Result := 1 else Result := fibonacci(n-1) + fibonacci(n-2); end end

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

• определение понятия является рекурсивным, если определение один или несколько раз ссылается на определяемое понятие
• рекурсивно определенное понятие называют рекурсивным понятием только для простоты, хотя это и не вполне корректно
• для любого понятия существует рекурсивное определение
• любое рекурсивно определенное понятие можно определить, не используя рекурсию

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

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

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

• 1
• 2
• 4
• 8

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

• 13
• 12
• 6
• 7

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

• массив
• стек
• список
• очередь
• очередь с приоритетом
• хеш-таблица

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

• для вставки элемента в контейнер и для доступа к нему указание ключа или индекса элемента не требуется
• доступ к элементу и вставка элемента в контейнер выполняется с указанием ключа или индекса элемента
• доступ к элементу контейнера выполняется с указанием ключа или индекса элемента, а для вставки ключа не требуется
• вставка элемента в контейнер выполняется с указанием ключа или индекса элемента, а для доступа ключа не требуется

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

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

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

• 1
• 2
• count
• 0
• count + 1

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

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

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

• чтение значения элемента, зная его номер
• запись значения элемента, зная его номер
• вставка нового элемента
• удаление существующего элемента

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

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

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

• group : ARRAY[STUDENT]
• kurs_er : LIST[group]
• mylist : LIST
• myarray : ARRAY
• petrov : STUDENT
• kurs : LIST[ARRAY[STUDENT]]

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

• время, затраченное каждым из участников разработки
• стоимость разработки
• процент реализованной функциональности, предусмотренной требованиями к системе
• число классов проекта
• время на разработку отдельных классов
• число строк кода проекта

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

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

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

• порядок предложений в файле определяет порядок сборки
• этот файл содержит типичные конструкции языка программирования - условный оператор и оператор цикла
• файл состоит из описания зависимостей одних модулей от других и команд, которые нужно выполнить, если зависимость следует применить
• этот файл можно рассматривать как программу на языке программирования декларативного типа

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

• модули
• время
• алгоритмы
• люди

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

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

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

• проверка правильности
• синтаксический анализ
• генерация кода
• лексический анализ
• семантический анализ

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

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

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

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

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

• CADCAM
• VisualStudio
• EiffelStudio
• CASE

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

• контекстно-свободная грамматика (БНФ) не позволяет полностью описать синтаксис таких языков из-за существования контекстных зависимостей
• контекстно-свободная грамматика (БНФ) полностью позволяет описать синтаксис таких языков
• для описания синтаксиса языка приходится строить контекстно-зависимую грамматику
• для описания контекстно-свободной части синтаксиса языка используется БНФ грамматика, дополненная формальными или неформальными правилами, отражающими контекстные зависимости

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

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

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

• Дональд Кнут
• Питер Наур
• Джон Бэкус
• Никлас Вирт

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

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

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

• знак числа
• порядок числа
• признак нормализации мантиссы
• нормализованная мантисса числа

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

• p = 3
• p = 4
• p = 8
• p = 16

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

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

Рассмотрим два фрагмента программ: -- 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:

• Создать новый элемент класса LINKABLE;Определить связь нового элемента, присвоив ей значение current.right;Изменить связь current.right, чтобы она стала ссылкой на вновь созданный элемент;Задать значение информационного поля у нового элемента (предполагается, что при вставке нового элемента известна информация, которую должен хранить этот элемент).
• Создать новый элемент класса LINKABLE;Изменить связь current.right, чтобы она стала ссылкой на вновь созданный элемент;Определить связь нового элемента, присвоив ей значение current.right;Задать значение информационного поля у нового элемента (предполагается, что при вставке нового элемента известна информация, которую должен хранить этот элемент).
• Создать новый элемент класса LINKABLE;Задать значение информационного поля у нового элемента (предполагается, что при вставке нового элемента известна информация, которую должен хранить этот элемент).Определить связь нового элемента, присвоив ей значение current.right;Изменить связь current.right, чтобы она стала ссылкой на вновь созданный элемент;
• Определить связь нового элемента, присвоив ей значение current.right;Изменить связь current.right, чтобы она стала ссылкой на вновь созданный элемент;Создать новый элемент класса LINKABLE;Задать значение информационного поля у нового элемента (предполагается, что при вставке нового элемента известна информация, которую должен хранить этот элемент).

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

• грузинское название байта
• 1024 Мебибайта
• 1 миллиард байтов
• в соответствии с международным стандартом обозначения кило, мега, гига отведены для степеней 10, а для степеней двойки должны применяться новые имена - киби, меби, гиби, так что гибибайт равен 1073741824 байта

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

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

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

• 5
• 3
• -1
• 2
• -7
• 10