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

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

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

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

(1) компьютеры плохо соображают. Они, как Митрофанушка в Недоросле, способны выучить только простейшую систему умножения - "единожды нуль -нуль", "Единожды один - один"

(2) бит просто реализуется

(3) последовательности битов легко сохраняются и легко читаются

(4) удается создать относительно дешевую память на битах большого объема

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

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

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

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

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

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

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

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

(1) Дональд Кнут

(2) Питер Наур

(3) Джон Бэкус

(4) Никлас Вирт

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

(1) CADCAM

(2) VisualStudio

(3) EiffelStudio

(4) CASE

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

(1) цветовая разметка текста программы

(2) интеллектуальная подсказка и построение шаблонов

(3) создание стилей

(4) создание закладок и гиперссылок

(5) документируемые комментарии

(6) вставка и работа с таблицами

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

(1) при объявлении каждой сущности задается ее тип

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

(3) для каждого вызова x.f(p) компилятор может определитьтип сущности x

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

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

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

(1) чтение значения элемента, зная его номер

(2) запись значения элемента, зная его номер

(3) вставка нового элемента

(4) удаление существующего элемента

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

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

(2) оплата наличными

(3) выделение памяти, играющей роль буфера

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

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

(1) определение понятия является рекурсивным, если определение один или несколько раз ссылается на определяемое понятие

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

(3) для любого понятия существует рекурсивное определение

(4) любое рекурсивно определенное понятие можно определить, не используя рекурсию

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

(1) содержит хотя бы одну ветвь, не являющуюся рекурсивной

(2) все ветви метода являются рекурсивными - содержат рекурсивные вызовы

(3) каждый рекурсивный вызов отличается контекстом вызова

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

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

(1) p = 3

(2) p = 4

(3) p = 8

(4) p = 16

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

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

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

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

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

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

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

(1) конечное множество правил задает грамматику языка

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

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

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

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

(1) область применения - общецелевой или проблемно-ориентированный язык

(2) стиль описания - императивный или декларативный

(3) энергоемкость - уровень потребляемой энергии

(4) учет жизненного цикла - возможность использования на этапах спецификации проекта, проектирования и реализации

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

(1) программная система строится из модулей - кластеров, классов, методов

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

(3) собранная из модулей система называется сборкой

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

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

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

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

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

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

(4) успешно скомпилированная программа - это программа, которая при компиляции не обнаружила ошибок в семантических правилах

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

(1) LINKED_LIST

(2) ARRAYED_LIST

(3) LIST

(4) TWO_WAY_LIST

(5) MULTI_ARRAYED_LIST

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

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

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

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

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

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

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

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

(2) понятие "Целое", понимаемое как последовательность цифр, воспринимаемых как терминальные, не определяемые символы

(3) понятие "Целое со знаком", понимаемое как последовательность цифр, воспринимаемых как терминальные, не определяемые символы. Цифрам может предшествовать знак плюс или минус

(4) понятие "ФИО", понимаемое как последовательность трех строк, задающих фамилию, имя и отчество и воспринимаемых в данном контексте как терминальные, не определяемые символы

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

(1) в классических функциональных языках есть рекурсия, но нет циклов

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

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

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

(5) только, используя стеки, можно рекурсию заменить циклами

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

(1) грузинское название байта

(2) 1024 Мебибайта

(3) 1 миллиард байтов

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

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

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

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

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

. Тогда для любого элемента math

найдется в последовательности такой элемент math

, что пара math

принадлежит отношению

(4) перечисление math

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

, где

, не принадлежит отношению r

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

. Тогда для любого элемента math

либо пара

, либо пара math

принадлежит отношению

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

(1) *

(2) [

(3) ]

(4) !

(5) {

(6) }

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

(1) основан на использовании понятия "состояние"

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

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

(4) императивный стиль программ

(5) вычисление по программе рассматривается как вычисление значения функции по вычисленным значениям аргументов без изменения состояния

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

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

(2) порядок предложений в файле определяет порядок сборки

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

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

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

(1) petrov : STUDENT

(2) myarray : ARRAY

(3) mylist : LIST

(4) group : ARRAY[STUDENT]

(5) kurs : LIST[ARRAY[STUDENT]]

(6) kurs_er : LIST[group]

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

(1) список с курсором - это список, в котором есть указатель на направление движения списка

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

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

(4) за константное время O(1) можно удалить элемент, стоящий в позиции, определяемой курсором

(5) зная номер элемента списка, за константное время O(1) можно получить доступ к любому элементу списка с курсором

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

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

(1) доступ к элементу и вставка элемента в контейнер выполняется с указанием ключа или индекса элемента

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

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

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

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

(1) 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

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

(3) 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-2) + fibonacci(n-1); end end

(4) fibonacci(n: INTEGER): INTEGER require 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

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

(1) теорема

(2) аксиома

(3) определение, не включающее рекурсию

(4) определение, включающее рекурсию

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

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

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

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

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

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

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

принадлежит отношению math

, если спортсмен math

выиграл у спортсмена g

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

принадлежит отношению math

, если спортсмен math

выиграл у спортсмена g

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

принадлежит отношению math

, если событие math

предшествует по времени событию g

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

принадлежит отношению r, если деталь math

является частью детали g

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

принадлежит отношению r, если метод math

вызывает метод math

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

(1) конкатенация

(2) выбор

(3) повторение

(4) модуль

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

(1) основной структурой данных является список, как в языке LISP

(2) вызовы функции позволяют не использовать оператор присваивания

(3) рекурсивные вызовы позволяют не использовать оператор цикла

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

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

(1) все изменения хранятся в некотором хранилище

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

(3) в специальном хранилище хранятся официальные версии, прошедшие полный контроль

(4) в другом хранилище хранятся локальные версии

(5) одни и те же команды применимы к локальным и официальным версиям

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

(1) inserted: has(i)

(2) inserted: has(key, i)

(3) inserted: has(key)

(4) current: item(key) = i

(5) current: item(i) = key

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

(1) 0

(2) 1

(3) 2

(4) count

(5) count + 1

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

(1) массив

(2) стек

(3) список

(4) очередь

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

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

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

Совершенно очевидно, какие значения принимает эта функция при math

. А каковы ее значения при math

? Оказывается, для таких math

функция имеет одно и то же значение. Какое?

(1) 1

(2) 11

(3) 33

(4) 77

(5) 91

(6) 99

Рекурсивное определение можно рассматривать как уравнение неподвижной точки math

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

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

(1) аргументом функции math

является рекурсивная функция, ее значением является также рекурсивная функция

(2) аргументом функции math

является пара math

- значением является другая пара math

(3) аргументом функции math

является граф функции math

- множество пар math

- значением является множество пар, которое функция строит по исходному множеству

(4) аргументом функции math

является граф функции - множество пар math

- значением является пара math

, которую функция строит по исходному множеству

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

(1) знак числа

(2) порядок числа

(3) признак нормализации мантиссы

(4) нормализованная мантисса числа

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

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

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

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

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

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

(1) начальный символ каждой продукции

(2) категория, определяемая первой продукцией

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

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

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

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

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

(3) возможна глобальная оптимизация выполняемой программы

(4) эффективная скорость выполнения

(5) возможно внесение изменений с практически мгновенной реакцией на эти изменения

(6) эффективная скорость отладки

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

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

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

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

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

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

(1) такой способ является самым надежным и самым точным способом оценки характеристик алгоритма

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

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

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

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

(1) проход по списку с выполнением некоторой операции над всеми элементами списка

(2) выполнение некоторой операции над элементами списка, стоящими слева и справа от курсора

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

(4) проход по списку, пока не встретится элемент списка, для которого выполняется некоторое условие

(5) различные вариации циклической обработки элементов списка

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

(1) 7

(2) 6

(3) 13

(4) 12

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

(1) только один узел бинарного дерева является его корнем

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

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

(4) каждый узел math

бинарного дерева math

определяет бинарное дерево math

Пусть членами семьи являются муж, жена, их родители и их дети. Определим рекурсивно понятие родственника. Члены семьи являются родственниками - родственниками уровня 0. Это не рекурсивная ветвь определения. Определим теперь рекурсивно понятие родственника - родственника некоторого уровня. Некто N является родственником уровня math

, если он не является родственником уровня k или более низкого уровня, но является родственником уровня 0 любого из родственников уровня k. К какому уровню по отношению к Вам относится внук брата дедушки?

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

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

(1) съемная

(2) кратковременная

(3) постоянная

(4) ленивая

(5) рассеянная

(6) встроенная

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

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

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

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

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

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

(1)

(2)

(3)

(4)

(5)

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

(1) JIT-компилятор - это компилятор с языка JIT в код целевой машины

(2) JIT-компилятор - это компилятор с языка Java в код целевой машины

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

(4) JIT компилятор - это компилятор, который при выполнении программы на целевой машине при первом вызове модуля компилирует виртуальный код модуля в машинный код целевой машины

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

(1) число строк кода проекта

(2) число классов проекта

(3) время на разработку отдельных классов

(4) процент реализованной функциональности, предусмотренной требованиями к системе

(5) время, затраченное каждым из участников разработки

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

книг. Гарри наугад выбирает книгу и просматривает ее содержимое, на что у него уходит math

минут. При неудаче он повторяет поиск, выбирая новую книгу. Для такого алгоритма поиска каковы значения времени поиска: минимальное, максимальное, в среднем?

(1)

(2)

(3)

(4)

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

(1) связный список задается двумя классами - один класс описывает элемент связного списка, другой - сам список

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

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

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

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

(1) 1

(2) 2

(3) 4

(4) 8

Пусть

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

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

(1) 1

(2)

(3)

(4)

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

(1) всегда задавать вариант

(2) включать вариант в описание метода как комментарий при условии, что вариант известен

(3) всегда задавать инвариант

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

(5) в предложении ensure задавать постусловие метода. Метод должен гарантировать выполнение постусловия при завершении любого из внутренних рекурсивных вызовов

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

(1) должны находиться непосредственно в оперативной памяти

(2) должны быть в регистрах

(3) должны быть в постоянной памяти

(4) могут находиться в памяти любого из указанных видов

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

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

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

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

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

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

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

(1) у регулярной грамматики нет продукции вида "конкатенация"

(2) у регулярной грамматики нет продукции вида "повторение"

(3) у регулярной грамматики нет продукции вида "выбор"

(4) у регулярной грамматики не допускаются продукции, содержащие прямую или косвенную рекурсию

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

(1) лексический анализ

(2) синтаксический анализ

(3) проверка правильности

(4) семантический анализ

(5) генерация кода

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

(1) включает компилятор и интерпретатор языка Eiffel

(2) позволяет добавлять компилятор любого языка программирования

(3) включает Отладчик

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

(5) является средой с открытым кодом

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

(1) массив это контейнер, содержащий элементы, принадлежащие одному типу или согласованным типам

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

(3) нижняя граница изменения индекса массива фиксирована и равна 0

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

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

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

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

(1) put_right

(2) remove_right

(3) start

(4) finish

(5) forth

(6) back

Какие утверждения являются частью постусловия операции вталкивания элемента в вершину стека - put(x)?

(1) x = 0

(2) item = x

(3) count = old count + 1

(4) is_empty = FALSE

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

, не вошедшие в путь path. Какие утверждения справедливы для процедуры поиска?

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

(2) поиск всегда завершается в городе N успехом или неуспехом

(3) поиск обязательно завершится в одном из городов math

успехом или неуспехом

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

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

(1) первым может завершиться экземпляр метода s

(2) первым может завершиться экземпляр метода r

(3) первым может завершиться экземпляр метода q

(4) первым может завершиться экземпляр метода p

(5) первый, пришедший в стек, экземпляр метода r завершится позже первого, пришедшего в стек, экземпляра метода s

(6) последним завершится экземпляр метода p

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

(1) это такой же физический закон, как и закон Ньютона

(2) это эмпирическое наблюдение, справедливое в определенных временных рамках

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

(4) закон Мура выполняется на новом уровне для многоядерных компьютеров

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

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

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

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

, где

- число элементов, math

- число ограничений

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

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

(1) контекстно-свободная грамматика (БНФ) полностью позволяет описать синтаксис таких языков

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

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

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

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

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

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

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

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

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

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

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

(1) инструментарий ПО играет ту же роль для программиста, что и инструментарий CAD для инженера в машиностроении

(2) компиляторы и интерпретаторы не относятся к инструментам разработки ПО

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

(4) инструментарий "контроля версий" должен полностью сохранять весь код всех версий программной системы

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

(1) чтение элемента кортежа

(2) запись элемента кортежа

(3) вставка элемента кортежа

(4) удаление элемента кортежа

Одним из наследников класса LIST является библиотечный класс ARRAYED_LIST. Какие утверждения справедливы для этого класса?

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

(2) этот класс не использует ссылки при организации списка

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

(4) класс ARRAYED_LIST имеет тот же набор запросов и команд, наследуемых от класса LIST, что и классы LINKED_LIST и TWO_WAY_LIST

(5) все операции в классе ARRAYED_LIST реализуются столь же эффективно, как и в классах LINKED_LIST и TWO_WAY_LIST

(6) некоторые операции в классе ARRAYED_LIST реализуются эффективнее, некоторые менее эффективно в сравнении с классами LINKED_LIST и TWO_WAY_LIST

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

(1) справедлива политика "первым пришел, первым уйдешь"

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

(3) справедлива политика "первым пришел в свою группу приоритетности - первым уйдешь из этой группы"

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

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

Алгоритм перебора с возвратами, реализованный рекурсивной процедурой find(path) исключает зацикливание (каждый город на пути встречается только один раз), что позволяет исходный граф рассматривать как дерево. Какие утверждения справедливы для графов, перебора с возвратом, и связанных с ними деревьев вариантов?

(1) граф без циклов является деревом

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

(3) для всякого графа можно построить остовное дерево, удалив часть дуг графа

(4) алгоритм перебора с возвратами сводится к префиксному обходу дерева вариантов

(5) алгоритм перебора с возвратами сводится к инфиксному обходу дерева вариантов

(6) алгоритм перебора с возвратами сводится к постфиксному обходу дерева вариантов

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

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

(1) только имя исходной башни

(2) только имя целевой башни

(3) только число переносимых дисков

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

(5) необходимо сохранять все 5 величин

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

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

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

(1) CHARACTER

(2) STRING

(3) CHARACTER_8

(4) CHARACTER_32

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

(1) 1

(2) 8

(3) 16

(4) 24

(5) 36

(6) 48

(7) 64

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

(1) Дональд Кнут

(2) Питер Наур

(3) Джон Бэкус

(4) Никлас Вирт

(1) CADCAM

(2) VisualStudio

(3) EiffelStudio

(4) CASE

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

(1) цветовая разметка текста программы

(2) интеллектуальная подсказка и построение шаблонов

(3) создание стилей

(4) создание закладок и гиперссылок

(5) документируемые комментарии

(6) вставка и работа с таблицами

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

(1) универсальный класс - это класс, соответствующий любому понятию универсума

(2) универсальный класс - это класс, задающий любой тип данных

(3) универсальный класс, как и всякий класс, задает тип данных

(4) универсальный класс - это класс, имеющий формальные параметры, представляющие типы данных

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

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

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

(1) чтение значения элемента, зная его номер

(2) запись значения элемента, зная его номер

(3) вставка нового элемента в позицию, определяемую курсором

(4) удаление элемента в позиции, определяемой курсором

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

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

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

(1) любую структуру данных

(2) некоторую структуру данных

(3) любой алгоритм - метод класса (процедуру, функцию)

(4) некоторый алгоритм - метод класса (процедуру, функцию)

(5) любые понятия проблемной области - грамматики языков программирования, каталоги операционной системы и так далее

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

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

(1) содержит хотя бы одну ветвь, не являющуюся рекурсивной

(2) все ветви метода являются рекурсивными - содержат рекурсивные вызовы

(3) каждый рекурсивный вызов отличается контекстом вызова

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

(1) 110111010

(2) 25

(3) 37

(4) 43

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

? Отношение полного строгого порядка:

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

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

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

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

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

(6) для любой пары math

из

либо

, либо

принадлежит отношению

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

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

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

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

(4) метакатегории

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

(1) уровень абстракции - на нижнем уровне находятся ассемблеры, близкие к машинному коду

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

(3) элитность - языки, ориентированные на элиту программирования

(4) верифицируемость - ориентация на обнаружение ошибок на этапе трансляции или на этапе выполнения

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

(1) модули

(2) время

(3) алгоритмы

(4) люди

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

(1) тип представляет описание множества значений (объектов) периода выполнения. Типы характеризуют динамику - период выполнения

(2) класс представляет статическое описание структуры объектов (поля класса) и их поведения (методы класса)

(3) каждый класс описывает конкретный тип данных

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

Какие утверждения справедливы для библиотечного класса LIST, определяющего понятие "список"?

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

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

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

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

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

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

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

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

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

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

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

(1) определение понятия "Оператор" является явно рекурсивным определением

(2) определение понятия "Цикл" является явно рекурсивным определением

(3) определение понятия "Оператор" является определением с косвенной рекурсией

(4) определение понятия "Цикл" не является рекурсивным определением

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

(1) фактические аргументы, задаваемые при вызове метода

(2) локальные переменные, объявленные в методе

(3) поля класса, в котором объявлен метод, представляющие глобальную информацию для метода

(4) сущность RESULT, определенная в языке Eiffel по умолчанию для всех методов, вычисляющих некоторую функцию

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

(1) любое целое число может быть представлено в памяти компьютера без потери точности

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

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

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

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

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

Пусть для конечного множества элементов math

задано ациклическое отношение r множеством пар math

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

(1) перечисление math

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

не существует math

, где

, такого, что пара math

принадлежит r

(2) для перечисления math

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

существует элемент math

, являющийся предшественником math

в отношении r

(3) каждое перечисление math

задает полный порядок. Пара math

принадлежит этому порядку, если math

(4) перечисление math

задает топологически отсортированную последовательность для отношения math

, если каждая пара из math

содержится в множестве пар полного порядка, определенного перечислением

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

(1) каждая продукция задает определение нетерминальной категории

(2) множество продукций бесконечно

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

(4) в левой части продукции находится определяемая категория

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

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

(1) являются строго функциональными языками

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

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

(4) современные ОО языки в минимальной степени используют свойства функциональных языков

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

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

(1) если указана зависимость, то она всегда будет применяться

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

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

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

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

(1) контейнерный класс - это класс, задающий некоторое хранилище элементов, имеющее свою специфику

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

(3) все контейнерные классы одинаково реализуют операции, общие для контейнерных классов

(4) контейнерные классы отличаются спецификой выполнения операций

(5) существует контейнерный класс, который наиболее эффективно реализует все общие операции

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

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

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

(3) если курсор принимает значение 0, то это означает, что курсор находится вне списка - слева от списка

(4) если курсор принимает значение n + 1, то это означает, что курсор находится вне списка - справа от списка

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

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

(2) экзамен принимают несколько преподавателей. Каждый из них вызывает по фамилии студента и принимает у него экзамен

(3) экзамен принимают несколько преподавателей. Студент выбирает, какому из преподавателей он хочет сдавать экзамен, и записывается к нему в очередь

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

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

(1) циклический вариант имеет временную сложность O(n)

(2) при эффективной реализации рекурсии сложность рекурсивного варианта O(n)

(3) циклический вариант, как правило, работает быстрее

(4) рекурсивный вариант, как правило, работает быстрее

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

(1) функцию можно задать ее графом - множеством пар math

(2) рекурсивное определение можно рассматривать как уравнение неподвижной точки math

(3) в уравнении неподвижной точки math

функция

- это некоторая универсальная функция, заданная на графе функции

(4) в уравнении неподвижной точки math

функция

- это функция, заданная на графе функции и представляющая решение уравнения

Рассмотрим два фрагмента программ:

-- fragment 1

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

(1) первый фрагмент вычисляется быстрее и точнее

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

(3) второй фрагмент вычисляется быстрее и точнее

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

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

(1) 5

(2) 10

(3) 16

(4) 25

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

(1) каждая продукция определяет одну нетерминальную категорию

(2) каждая нетерминальная категория определяется одной продукцией

(3) каждая продукция должна быть одного вида

(4) допускаются правила, состоящие из смеси продукций разного вида

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

(1) Джон Бэкус

(2) Фил Вадлер

(3) Уле Дал

(4) Кристин Нигард

(5) Алан Кей

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

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

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

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

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

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

(1) у каждого контейнерного класса общий по смыслу метод имеет свое оригинальное имя

(2) у каждого контейнерного класса общий по смыслу метод имеет одно и то же имя и одну и ту же сигнатуру

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

(4) методы с одинаковой сигнатурой должны иметь одно и то же имя

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

(1) 1

(2) 2

(3) count

(4) count + 1

(5) count / 2

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

(1) массив

(2) стек

(3) список

(4) очередь

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

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

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

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

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

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

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

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

(1) { [0, -10], [1, -9], [2, -8], … [100, 90], [101, 91], [102, 91], [103, 91], …}

(2) { [0, 11], [1, 12], [2, 13], … [80, 91], [81, 91], [82, 91], [83, 91], …}

(3) { [0, 91], [1, 91], [2, 91], … [100, 91], [101, 91], [102, 92], [103, 93], …}

(4) { [0, 91], [1, 91], [2, 91], … [100, 91], [101, 91], [102, 91], [103, 91], …}

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

(1) память, при обращении к которой возвращается значение слова памяти, выбранное случайным образом

(2) специальный вид памяти, который можно подсоединить к компьютеру

(3) одно из названий оперативной памяти компьютера

(4) одно из названий постоянной памяти на дисках

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(3) возможна глобальная оптимизация выполняемой программы

(4) эффективная скорость выполнения

(5) возможно внесение изменений с практически мгновенной реакцией на эти изменения

(6) эффективная скорость отладки

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

(1) создается репозиторий с поддержкой управления версиями

(2) создается электронный магазин для заказа новых версий и модификации старых

(3) создается ролевой Web-сайт с правами администратора, разработчика, тестировщика, пользователя

(4) создается форум - площадка для обсуждений

(5) для работы над документацией создаются Вики - страницы

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

(1) абстрактная сложность рассматривается как функция, зависящая от размера задачи

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

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

(4) константные множители можно не учитывать при оценке абстрактной сложности

(5) константные слагаемые можно не учитывать при оценке абстрактной сложности

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

(1) temp: INTEGER your_list.start temp := your_list.item from your_list.forth until your_list.after loop temp := temp + your_list.item your_list.forth end

(2) temp: INTEGER your_list.start temp := your_list.item from your_list.forth until your_list.after loop if (temp < your_list.item) temp := your_list.item end your_list.forth end

(3) temp: INTEGER from temp := 0 your_list.start until your_list.after loop if (your_list.item = 5) temp := your_list.index end your_list.forth end

(4) temp: INTEGER finish: BOOLEAN from your_list.start temp := 0 finish := FALSE until your_list.after or else finish loop if (your_list.item = 5) finish := TRUE temp:= your_list.index end your_list.forth end

(1) 7

(2) 6

(3) 13

(4) 12

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

(1) для ее решения существует только рекурсивный алгоритм

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

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

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

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

является решением уравнения неподвижной точки math

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

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

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

(1)

- пустое множество

(2)

- множество пар вида math

(3)

(4) функция math

добавляет пары в множество math

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

(5) поскольку функция math

добавляет пары и строит новые пары в множество math

, то свойство math

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

(6) по определению граф math

и соответственно сама функция math

представляет объединение всех math

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

(1) 10

(2) 100

(3) 1000

(4) 1000000

(5) 10000000

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

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

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

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

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

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

(1)

(2)

(3)

(4)

(5)

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

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

(2) виртуальная машина Java - это компьютер, специально спроектированный для языка Java

(3) байт-код - это код виртуальной машины Java

(4) байт-код - это универсальный код любой виртуальной машины

(1) число строк кода проекта

(2) число классов проекта

(3) время на разработку отдельных классов

(4) стоимость разработки

(5) процент реализованной функциональности, предусмотренной требованиями к системе

(6) время, затраченное каждым из участников разработки

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

(1) intar: ARRAY[INTEGER]

(2) my_ar :INTEGER ARRAY[100]

(3) star :ARRAY[STUDENT]

(4) rar :ARRAY[REAL][1,100]

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

(1)

Создать новый элемент класса LINKABLE;

Определить связь нового элемента, присвоив ей значение current.right;

Изменить связь current.right, чтобы она стала ссылкой на вновь созданный элемент;

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

(2)

Создать новый элемент класса LINKABLE;

Изменить связь current.right, чтобы она стала ссылкой на вновь созданный элемент;

Определить связь нового элемента, присвоив ей значение current.right;

(3)

Создать новый элемент класса LINKABLE;

Определить связь нового элемента, присвоив ей значение current.right;

Изменить связь current.right, чтобы она стала ссылкой на вновь созданный элемент;

(4)

Определить связь нового элемента, присвоив ей значение current.right;

Изменить связь current.right, чтобы она стала ссылкой на вновь созданный элемент;

Создать новый элемент класса LINKABLE;

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

(1) put

(2) item

(3) remove

(4) is_empty

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

(1) все элементы, хранимые в узлах дерева, различны

(2) для любых двух элементов, хранимых в узлах дерева, один из них "больше другого"

(3) максимальный элемент хранится в корне дерева

(4) максимальный элемент левого дерева меньше минимального элемента правого дерева

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

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

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

(3) инвариант должен включаться в предусловие и постусловие метода

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

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

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

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

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

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

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

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

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

(1) всегда

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

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

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

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

(1) любой регулярный язык может быть описан регулярной грамматикой

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

(3) регулярные языки поддерживают вложенность понятий

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

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

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

(2) лексер может не строить полный список лексем, а выдавать очередную лексему по требованию парсера

(3) в результате работы парсера строится АСТ - абстрактное синтаксическое дерево

(4) лексер распознает идентификаторы

(5) идентификаторы распознает парсер

(6) парсер заносит идентификаторы в таблицу идентификаторов

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

(1) исходный код на языке Eiffel компилировать в машинный код

(2) исходный код на языке Eiffel компилировать в код на языке С для исполняемой среды Eiffel

(3) исходный код на языке Eiffel компилировать в промежуточный код на CIL для .Net исполняемой среды

(4) обнаружить синтаксические ошибки, не отвечающие синтаксису, заданному БНФ грамматикой

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

В класс ARRAY добавлен "синтаксический сахар", позволяющий наряду с чтением и записью элементов массива в объектном стиле использовать и привычную скобочную запись. Отметьте допустимые фрагменты кода Eiffel при работе с массивом ar:

(1) ar[i] := ar[i] + 1

(2) ar[i] := ar.item(i) + 1

(3) ar[i] := ar.put(ar[i] +1, i)

(4) ar.put(ar.item(i) +1, i)

(5) ar.put(ar[i] +1, i)

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

(1) put_right

(2) remove_right

(3) start

(4) finish

(5) forth

(6) back

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

(1) операция вставки put(x) в очередь реализуется за время O(1) выполнением одной операции над списком put_front(x), которая помещает элемент x в начало списка

(2) операция удаления элемента из очереди – remove выполняется за время O(count), поскольку требует перемещения по всему списку, чтобы удалить элемент, стоящий в конце списка

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

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

, не входящие в путь path. Какие утверждения справедливы относительно вызовов процедуры поиска?

(1) если после вызова find(path), в процессе ее работы, достигнут город N, то больше эта процедура вызываться не будет

(2) если город N не является искомой целью - городом В, то процедура find как рекурсивная процедура будет вызвана как минимум один раз

(3) если город N не является искомой целью - городом В, то процедура find как рекурсивная процедура будет вызвана не менее n раз

(4) если город N не является искомой целью - городом В, то процедура find как рекурсивная процедура будет вызвана не более n раз

(5) если город N не является искомой целью - городом В, то процедура find как рекурсивная процедура будет вызвана m раз, где m может быть как больше, так и равно или меньше n

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

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

(2) каждый экземпляр метода имеет собственную копию данных, называемую контекстом метода

(3) фактические аргументы, заданные в момент вызова, входят в контекст метода

(4) локальные переменные метода входят в его контекст

(5) поля класса входят в контекст метода

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

(7) при завершении работы метода запись активации удаляется из стека

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

(1) измерение всех величин, используемых в компьютерной практике, объема памяти, скорости передачи данных и других, использует степени двойки, так что префикс кило означает 1024 = 2¹⁰, мега - 2²⁰ и так далее

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

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

(4) представление вещественных чисел является приближенным. Арифметические операции над ними являются источником появления погрешностей

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

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

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

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

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

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

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

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

(1) тип 3 (регулярные языки)

(2) тип 2 (контекстно-свободные языки)

(3) тип 1 (контекстно-зависимые, неукорачивающие языки)

(4) тип 0 (неограниченные языки, распознаваемые машиной Тьюринга)

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

(1) поддерживает динамическое распределение памяти для создаваемых программой объектов

(2) выполняет сборку мусора, освобождая память от уже не нужных объектов

(3) выполняет оптимизацию кода

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

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

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

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

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

(4) интегрированная среда разработки представляет взаимосвязанную коллекцию инструментов разработчика ПО

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

(1) для работы с кортежами Eiffel предоставляет библиотечный универсальный класс TUPLE

(2) TUPLE - это тип, а не универсальный класс

(3) тип TUPLE[STUDENT, STRING, INTEGER] позволяет описать запись из трех полей, первое из которых задает объект класса STUDENT, второе - может содержать название факультета, а третье поле - номер курса (или номер группы), где учится наш студент

(4) тип TUPLE согласован со всеми кортежными типами, содержащими произвольное число полей. Объекту такого типа можно присвоить значение любого кортежного типа

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

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

(2) реализация такого списка построена на многомерном массиве - мультимассиве

(3) реализация такого списка построена на многосвязном списке - мультисписке

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

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

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

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

(3) стеки и очереди - это распределители с одинаковой политикой доступа к элементам

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

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

(1) 5

(2) 3

(3) -1

(4) 2

(5) -7

(6) 10

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

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

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

(1) INTEGER

(2) REAL

(3) NATURAL

(4) INTEGER_16

(5) REAL_16

(6) NATURAL_16

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

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

(2) бинарным отношением на множестве math

называют некоторое подмножество пар объектов math

этого множества

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

, где первый элемент пары принадлежит множеству А, а второй - множеству math

(4) можно обобщить определение отношения на множестве math

, заменив пару элементов кортежом math

, где каждый элемент math

принадлежит множеству math

. Такое отношение называется n - арным или отношением арности n на множестве math

(5) если пара math

принадлежит отношению, то пара math

не может принадлежать этому отношению

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

(1) грамматика языка задает описание его синтаксиса

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

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

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

(5) лексемы строятся из символов, составляющих алфавит языка

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

(1) CADCAM

(2) VisualStudio

(3) EiffelStudio

(4) CASE

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

(1) текст программы на языке Eiffel может быть создан только в редакторе, входящем в состав EiffelStudio

(2) текст программы на языке Eiffel может быть создан только в специализированном редакторе программ

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

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

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

(1) правильность и корректность программ - это эквивалентные понятия

(2) правильность - это понятие, относящееся к программам, корректность - к программистам

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

(4) корректная программа - это программа, которая будучи скомпилированной, работает в полном соответствии с контрактами

(5) только для правильных программ можно говорить об их корректности

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

(1) чтение значения элемента, зная его номер

(2) запись значения элемента, зная его номер

(3) вставка нового элемента в позицию, определяемую курсором

(4) удаление элемента в позиции, определяемой курсором

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

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

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

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

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

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

(1)

(2)

(3)

(4)

(5)

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

(1) вариантом рекурсивного метода является целочисленное неотрицательное выражение

(2) вариант связывается с каждым рекурсивным вызовом

(3) для всех внутренних рекурсивных вызовов вариант имеет одно и то же значение.

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

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

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

(1) 110111010

(2) 250

(3) 370

(4) 270

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

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

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

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

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

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

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

(1) правила БНФ не достаточно мощны для определения синтаксиса построения лексем

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

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

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

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

(1) С

(2) C#

(3) Eiffel

(4) LISP

(5) Java

(6) Prolog

(7) Assembler

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

(1) когда модуль был последний раз модифицирован?

(2) что изменилось в версии N по сравнению с предыдущей версией?

(3) что послужило причиной изменения?

(4) какое наказание заслуживает программист, допустивший ошибку?

(5) существует ли в текущей версии ранее обнаруженная ошибка?

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

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

(2) описание каждого класса является описанием универсально порожденного типа

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

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

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

(1) список - это упорядоченная последовательность однородных элементов

(2) в языке Eiffel нумерация элементов списка начинается с 1

(3) зная номер элемента списка, за константное время O(1) можно получить доступ к любому элементу списка

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

(5) за константное время O(1) можно удалить элемент, стоящий в позиции, определяемой курсором списка

Какие из операций над хеш-таблицами в классе HASH_TABLE имеют временную сложность O(count), а не O(1)?

(1) extend

(2) has

(3) item

(4) force

(5) put

(6) replace

(7) remove

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

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

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

(3) такое определение, являясь рекурсивным, будет порождать конечную цепочку объектов, заканчивающуюся парой объектов "ЕВА" и "АДАМ" - праматерью и праотцом

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

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

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

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

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

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

(4) контекст у рекурсивного метода меняется автоматически

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

Все модули Init, Exit, Body определены над полями класса - глобальной для метода информацией;

Init задает начальный контекст вызова;

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

(6) завершаемость метода cicle гарантирует завершаемость метода loop_eqviv

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

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

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

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

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

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

(1) 5

(2) 10

(3) 16

(4) 60

(5) 120

(6) 128

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

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

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

(3) символы метаязыка БНФ

(4) символы праязыка БНФ

(5) нетерминальные категории

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

(1) стиль основан на использовании понятия "состояние"

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

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

(4) императивный стиль программ

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

(1) для сборки используется команда make и соответствующий файл сборки

(2) в среду разработки EiffelStudio включен собственный инструмент Eiffel_make, выполняющий эту работу

(3) в среде EiffelStudio выполнение сборки не требуется

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

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

(1) is_empty : BOOLEAN

(2) count : INTEGER

(3) has(v : G): BOOLEAN

(4) is_empty = (count = 0)

(5) item: G

Укажите, какие из запросов не связаны с курсором?

(1) is_empty

(2) index

(3) before

(4) after

(5) is_first

(6) is_last

(7) off

(8) count

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

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

(1) перенос с А на В

(2) перенос с А на С

(3) не имеет значения, куда переносить на А или на С

(4) если n - нечетно, то перенос на В, иначе перенос на С

Рекурсивное определение функции math

можно рассматривать как уравнение неподвижной точки math

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

(1) решением уравнения неподвижной точки является функция math

, которая, будучи примененной к графу функции math

оставляет этот граф (множество пар) неизменным.

(2) рекурсивное определение math

позволяет построить функцию math

(3) функция math

, также как и функция math

, является рекурсивной

(4) если известно решение уравнения неподвижной точки - функция math

, то можно функцию math

определить без использования рекурсии

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

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

(2) - 127

(3) 11111111

(4) 10000001

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

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

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

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

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

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

(1)

(2)

(3)

(4)

Какие языки относятся к ОО языкам?

(1) Симула

(2) С

(3) С++

(4) LISP

(5) Eiffel

(6) Haskell

(7) C#

(8) Java

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

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

(2) сохранение кода проекта должно выполняться под управлением системы контроля версий

(3) система контроля версий не поддерживает сохранение документации к проекту

(4) репозиторий системы контроля версий со временем превращается в базу знаний, сохраняющую всю историю разработки ПО

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

(1) многие контейнерные классы, реализованные в EiffelStudio, имеют процедуру создания с общим именем make. Размер контейнера в этом случае фиксирован и определяется классом

(2) многие контейнерные классы, реализованные в EiffelStudio, имеют процедуру создания с общим именем make и сигнатурой make(n:INTEGER). Размер контейнера в этом случае фиксирован и определяется пользователем в момент создания контейнера заданием значения фактического аргумента n

(3) для контейнерных классов EiffelStudio выделяет максимально возможный объем памяти независимо от того, задавался ли аргумент n при создании контейнера

(4) для контейнерных классов EiffelStudio выделяет начальный объем памяти, определяемый аргументом n, если он был задан при создании контейнера. Когда в процессе работы с контейнером отведенная ему память близка к исчерпыванию, происходит автоматическая перестройка контейнера с отведением дополнительной памяти

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

(1) start

(2) finish

(3) item

(4) forth

(5) back

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

(1) массив

(2) стек

(3) список

(4) очередь

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

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

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

(1) бинарное дерево можно определить как рекурсивную структуру данных

(2) бинарное дерево всегда имеет узел, называемый корнем дерева

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

(4) бинарное дерево всегда имеет два бинарных поддерева - левое и правое

(5) бинарное дерево может иметь два поддерева, одно поддерево или ни одного поддерева

Пусть аргументом функции math

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

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

если в множестве есть пара math

, то в множество добавляется пара math

Для какой рекурсивно определенной функции math

, где

, функция

является решением уравнения неподвижной точки math

(1) функции Фибоначчи

(2) функции Маккарти "91"

(3)

(4)

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

(1) память на регистрах

(2) память на дисках

(3) RAM - память

(4) FLASH - память

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

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

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

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

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

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

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

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

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

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

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

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

(1) когда строится компилятор, то он не содержит элементов интерпретации

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

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

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

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

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

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

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

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

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

(5) для наследуемого метода F можно выяснить, какой класс впервые создал версию метода F

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

(1)

(2)

(3)

(4)

(5)

(6)

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

(1) temp: INTEGER your_list.start temp := your_list.item from your_list.forth until your_list.after loop temp := temp + your_list.item your_list.forth end

(2) temp: INTEGER your_list.start temp := your_list.item from your_list.forth until your_list.after loop if (temp < your_list.item) temp := your_list.item end your_list.forth end

(3) temp: INTEGER from temp := 0 your_list.start until your_list.after loop if (your_list.item = 5) temp := your_list.index end your_list.forth end

(4) 5.4. temp: INTEGER finish: BOOLEAN from your_list.start temp := 0 finish := FALSE until your_list.after or else finish loop if (your_list.item = 5) finish := TRUE temp:= your_list.index end your_list.forth end

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

(1) стек можно реализовать на массиве, растущем вверх

(2) стек можно реализовать на массиве, растущем вниз

(3) атрибут capacity, характеризующий емкость массива (число его элементов) и атрибут count для стека - эквивалентные понятия и имеют совпадающие значения

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

(5) для стека, реализуемого массивом в языке Eiffel, не требуется задавать емкость - максимальное число элементов, которые можно хранить в стеке. Емкость массива, на котором базируется стек, автоматически увеличивается и массивы в Eiffel перестраиваются, когда число записанных элементов приближается к границе, заданной атрибутом capacity

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

(1) менее наносекунды

(2) менее секунды

(3) менее часа

(4) менее суток

(5) более 100 лет

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

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

(1) 4

(2) 8.

(3) 16

(4) 18

(5) 24

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

(1) память на регистрах

(2) флеш - диск

(3) диск, использующий дисковод

(4) оперативная память

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

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

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

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

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

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

(1)

(2)

(3)

(4)

(5)

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

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

(2) два компилятора строить проще, чем один

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

(4) виртуальным программистам проще писать код для виртуальной машины, чем на ОО языке программирования

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

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

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

(1) ИСР (IDE) - это специальный компьютер, спроектированный для разработки ПО

(2) ИСР - это программная система, представляющая набор взаимосвязанных инструментов, необходимых и полезных для разработки ПО

(3) ИСР может быть открытой для языков программирования, позволяя разрабатывать ПО на разных языках программирования

(4) ИСР может быть программной системой с открытым кодом со свободным доступом или быть коммерческой системой

(5) все программные инструменты, используемые при разработке ПО, должны быть частью ИСР

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

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

(2) у item и put разные предусловия

(3) у item и put одинаковые предусловия: valid_lower: i > lower; valid_upper: i < upper

(4) у item и put одинаковое предусловие: valid_key: valid_index(i)

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

(1) 1

(2) 2

(3) 4

(4) 8

(5) 16

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

(1) для работы со стеками в библиотеке EiffelBase имеется только один класс - ARRAYED_STACK

(2) для работы со стеками в библиотеке EiffelBase предлагается три класса - ARRAYED_STACK, BOUNDED_STACK, LINKED_STACK

(3) все классы Eiffel для работы со стеками имеют эквивалентный набор операций - запросов и команд

(4) только для класса ARRAYED_STACK среднее время выполнения всех операций - O(1), для других классов - O(count)

(5) для класса ARRAYED_STACK максимальное время выполнения операции вставки put - O(count), достигаемое в тех редких случаях, когда происходит перестройка массива

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

(1) для любого дерева поиска средняя сложность равна math

(2) для любого дерева поиска средняя сложность равна math

(3) для полного дерева поиска средняя сложность равна math

(4) для полного дерева поиска средняя сложность равна math

(5) для произвольного дерева поиска максимальная сложность равна math

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

(1) при вызове рекурсивного метода клиент обязан гарантировать выполнение предусловия метода

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

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

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

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

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

(1) операции - арифметические, логические, сравнения

(2) операции языка ассемблера

(3) операции обмена данными между разными уровнями памяти

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

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

(1) стек

(2) очередь

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

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

(5) список

(6) массив

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

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

(2) любой регулярный язык распознается конечным автоматом

(3) язык, распознаваемый автоматом, является регулярным языком

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

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

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

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

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

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

Какие утверждения справедливы по отношению к технологии "тающего льда" в EiffelStudio?

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

(2) эффективно сочетает компиляцию и интерпретацию

(3) отвечает принципу: "Время реакции системы на внесенные изменения зависит от размера изменений, но не от размера самой системы

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

(5) часть кода, в которую вносятся изменения, может интерпретироваться

(6) При внесении изменений перекомпилироваться должна вся система

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

(1) метод всегда применим, потому не имеет предусловия

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

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

(4) максимальная временная сложность - O(count)

(5) минимальная временная сложность - O(count)

(6) временная сложность в среднем - O(count)

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

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

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

(3) для двусвязного списка повышается эффективность ряда операций, например, операция перемещения курсора влево - back выполняется в двусвязном списке за время O(1), а не за время O(count), как в односвязном списке

(4) интерфейс команд и запросов у классов TWO_WAY_LIST и LINKED_LIST различен

(5) реализации команд и запросов, наследуемых от класса List, у классов TWO_WAY_LIST и LINKED_LIST одинаковы

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

(1) очередь реализуется массивом, растущим вверх

(2) очередь реализуется массивом, растущим вниз

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

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

(5) все операции над очередью в среднем выполняются за время O(1)

, не входящие в путь path. Какие утверждения справедливы относительно возвратов в процессе поиска?

(1) если в процессе поиска путь поведет в следующий город, то возврата в город N никогда не будет

(2) в процессе поиска всегда будет происходить возврат в город N

(3) если путь math

ведет к успеху, то возврата в город N не будет

(4) в процессе поиска может произойти возврат из города N в город, путь из которого привел в N

(5) в процессе поиска с возвратами можно вернуться к исходной точке - городу А

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

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

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

(3) нерекурсивные методы, такие как p и q, в цепочке вызовов существуют в единственном экземпляре

(4) рекурсивные методы, такие как p и q, в цепочке вызовов всегда существуют в множестве экземпляров

(5) рекурсивные методы, такие как p и q, в цепочке вызовов, как правило, существуют в множестве экземпляров

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

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

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

(3) внешняя память на порядок уступает оперативной памяти по скорости доступа, но на несколько порядков превосходит ее по объему хранимых данных

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

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

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

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

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

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

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

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

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

(3) БНФ позволяет описать конкретный синтаксис, но не позволяет описать абстрактный синтаксис языка

(4) БНФ позволяет задать грамматику контекстно-зависимого языка

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

(1) задавать точки останова

(2) пошаговое выполнение программ

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

(4) наблюдать за состоянием программы в момент останова

(5) изменять состояние программы в момент останова, продолжая вычисление в измененном состоянии

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

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

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

(2) код, созданный компилятором, может быть непосредственно выполнен процессором компьютера

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

(4) редакторы и CASE-инструментарий позволяют строить программу из текстового и графического описания

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

(1) stud1:= TUPLE

(2) stud1:= [petrov, "computer science", 22]

(3) major : STUDENT; major := stud1.who

(4) stud1. group:= 32

(5) minor: STUDENT; minor := stud1

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

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

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

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

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

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

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

(1) FIFO - первый пришел - первый ушел

(2) LIFO - последний пришел - первый ушел

(3) LILO - последний пришел - последний ушел

(4) FILO - первый пришел - последний ушел

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

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

(6) 6

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

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

(2) сократить объем данных, хранимых в записи активации, можно за счет увеличения времени работы метода, - когда экземпляру требуется некоторое данное, то можно вычислять его значение, не храня его в записи активации. Этот прием называется "вычислить, а не хранить"

(3) прием "вычислить, а не хранить" всегда применим

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

(5) прием "преобразования в общей памяти" всегда применим