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

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

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

Ответ:

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

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

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

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

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


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

Ответ:

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

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

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

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

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

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


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

Ответ:

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

 (2) правильность - это понятие, относящееся к программам, корректность - к программистам 

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

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

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


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

Ответ:

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

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

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

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


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

Ответ:

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

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

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

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


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

Ответ:

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

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

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

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


Упражнение 3:
Номер 1
Классы 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] 


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

Ответ:

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

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

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

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

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


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

Ответ:

 (1) is_empty : BOOLEAN 

 (2) count : INTEGER 

 (3) has(v : G): BOOLEAN 

 (4) is_empty = (count = 0) 

 (5) item: G 


Упражнение 4:
Номер 1
Рассмотрим контейнерный класс, в котором метод вставки элементов 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 


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

Ответ:

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

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

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

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


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

Ответ:

 (1) многие контейнерные классы, реализованные в EiffelStudio, имеют процедуру создания с общим именем make. Размер контейнера в этом случае фиксирован и определяется классом 

 (2) многие контейнерные классы, реализованные в EiffelStudio, имеют процедуру создания с общим именем make и сигнатурой make(n:INTEGER). Размер контейнера в этом случае фиксирован и определяется пользователем в момент создания контейнера заданием значения фактического аргумента n 

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

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


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

Ответ:

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

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

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

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


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

Ответ:

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

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

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

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

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


Номер 3
Для некоторых алгоритмов получены оценки сложности. Из приведенных формул укажите две, задающие эквивалентные оценки? 

Ответ:

 (1) math 

 (2) math 

 (3) math 

 (4) math 

 (5) math 

 (6) math 


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

Ответ:

 (1) math 

 (2) math 

 (3) math 

 (4) math 


Номер 2
В языке 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] 


Номер 3
В классе 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) 


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

Ответ:

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

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

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

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

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

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


Номер 2
В класс 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) 


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

Ответ:

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

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

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

 (4) максимальная временная сложность - O(count) 

 (5) минимальная временная сложность - O(count) 

 (6) временная сложность в среднем - O(count) 


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

Ответ:

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

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

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

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


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

Ответ:

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

 (2) TUPLE - это тип, а не универсальный класс 

 (3) тип TUPLE[STUDENT, STRING, INTEGER] позволяет описать запись из трех полей, первое из которых задает объект класса STUDENT, второе - может содержать название факультета, а третье поле - номер курса (или номер группы), где учится наш студент 

 (4) тип TUPLE согласован со всеми кортежными типами, содержащими произвольное число полей. Объекту такого типа можно присвоить значение любого кортежного типа 


Номер 3
Пусть задано объявление объекта кортежного типа: 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 




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