Основы программирования

Упражнение 1:

Номер 1

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

Ответ:

(1) последовательность – последовательное выполнение ряда задач, дающее решение исходной задачи. Из K достичь H, из H достичь G

(2) выбор – разбиение K на два или более непересекающихся множества K1, K2, …KN. Найти решение каждой более простой задачи – из KJ достичь G

(3) гадание – стратегия, позволяющая угадать решение, дающее G

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

(5) подпрограмма (процедура, функция) – сведение задачи к другой задаче, решение которой уже известно

Номер 2

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

Ответ:

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

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

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

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

Номер 3

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

Ответ:

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

(2) недетерминированный

(3) вероятностный

(4) параллельный

Упражнение 2:

Номер 1

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

Ответ:

(1) алгоритм описывает единственный процесс

(2) программная система описывает множество процессов

(3) алгоритм описывает множество процессов

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

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

(6) алгоритм+Структуры данных = Программа

Номер 2

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

Ответ:

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

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

(3) составной оператор – это последовательность подряд записанных операторов, начинающаяся ключевым термином begin и заканчивающаяся термином end

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

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

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

Номер 3

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

Ответ:

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

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

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

(4) из истинности выполнения постусловия i-го оператора последовательности должно следовать предусловие i+1-го оператора последовательности, если таковой существует

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

Упражнение 3:

Номер 1

Какие составляющие у оператора цикла в языке Eiffel?

Ответ:

(1) from – инициализация цикла

(2) comment – комментарий

(3) loop – тело цикла – повторяющиеся действия

(4) until - условие выхода из цикла

(5) require – предусловие цикла

Номер 2

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

Ответ:

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

(2) у цикла может быть только один инвариант

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

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

(5) нахождение подходящего инварианта – это творческая задача

Номер 3

Когда каменщику нужно выложить стенку из кирпичей, то он, начиная с первого ряда, кладет ряд за рядом, пока стена не достигнет заданной высоты. Многие циклы, хотя и не все, следует этой стратегии, задавая аппроксимацию – последовательное приближение к достижению цели цикла. Построим цикл, моделирующий работу каменщика. Предположим, что высота одного ряда равна h, и каменщику нужно возвести стену высотой H = n * h. В качестве подходящего инварианта цикла выберем условие H = i * h (содержательно это означает, что выложена стена из i рядов кирпичей). Отметьте корректные составляющие цикла, позволяющие решить эту задачу и доказать ее корректность. Доказательство корректности предполагает доказательство трех утверждений: после инициализации инвариант цикла становится истинным, тело цикла сохраняет истинность инварианта, из истинности условия выхода и инварианта следует выполнение цели цикла

Ответ:

(1) from i = 0

(2) from i = 1

(3) until i = n

(4) loop – "положить ряд кирпичей" i = i+1

(5) loop – "положить ряд кирпичей" i = i+2

Упражнение 4:

Номер 1

Какими свойствами должен обладать инвариант цикла?

Ответ:

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

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

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

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

Номер 2

Укажите корректные высказывания о завершении цикла?

Ответ:

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

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

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

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

Номер 3

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

Ответ:

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

(2) после инициализации вариант цикла получает неотрицательное значение

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

(4) у каждого цикла есть вариант

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

Упражнение 5:

Номер 1

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

Ответ:

(1) команда start – устанавливает курсор в позицию первого элемента списка

(2) команда any – устанавливает курсор в позицию некоторого произвольного элемента списка

(3) запрос between – возвращает значение True, если курсор указывает на некоторый элемент списка

(4) запрос is_after – возвращает значение True, если курсор находится в позиции справа от последнего элемента списка

(5) команда forth – передвигает курсор в следующую справа позицию

(6) запрос item – возвращает элемент списка, если он существует в позиции курсора

Номер 2

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

Ответ:

(1) if-часть в форме if условие

(2) then-часть в форме then составной оператор

(3) else – if часть в форме elseif условие then составной оператор

(4) else – часть в форме else составной оператор

(5) ключевое слово end

Номер 3

Каковы условия корректности условного оператора if c then a else b?

Ответ:

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

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

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

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

(5) непосредственно после завершения выполнения условного оператора, если не выполнялось условие c, то из постусловия оператора b должно следовать постусловие составного оператора

(6) непосредственно после завершения выполнения условного оператора из конъюнкции постусловий операторов a и b должно следовать постусловие составного оператора

Упражнение 6:

Номер 1

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

Ответ:

(1) оператор goto синтаксически очень прост – goto метка

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

(3) оператор goto позволяет превратить программу в "блюдо спагетти"

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

(5) "Э. Дейкстра показал, что оператор goto вреден, применять его не следует

Номер 2

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

Ответ:

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

(2) вложенность одних управляющих структур в другие не допускается

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

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

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

Номер 3

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

Ответ:

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

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

(3) практика профессионального ОО программирования использует только две управляющие структуры в соответствии с теоремой Бёма – Джакопини

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

Упражнение 7:

Номер 1

Оператор множественного выбора в языке Eiffel синтаксически имеет следующий вид:
inspect
choice-выражение
when val_1 then составной оператор_1
when val_2 then составной оператор_2
…
else составной оператор
end

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

Ответ:

(1) выражение choice может быть целочисленным

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

(3) выражение choice может быть строкового типа

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

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

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

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

Номер 2

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

Ответ:

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

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

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

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

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

Номер 3

Какое утверждение является неверным по отношению к механизму обработки исключительных ситуаций Retry - resque в языке Eiffel:

Ответ:

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

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

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

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

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

Упражнение 8:

Номер 1

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

Ответ:

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

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

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

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

Номер 2

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

Ответ:

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

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

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

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

Номер 3

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

Ответ:

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

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

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

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

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

Основы программирования - тест 7