Знакомство с элементами языка программирования C. Разработка, спецификация, реализация, верификация и тестирование алгоритмов и программ

Проверочный Тест

Новосибирский Государственный Университет	Фамилия, имя, отчество студента:
Механико-математический факультет	Номер зачетной книжки:
Поток I	Подпись:
Преподаватель: Шилов Николай Вячеславович	Дата: среда, 27 мая 2009 г.

 1.  Знакомство с элементами языка программирования C.

 1.1.   (3) Пусть  в программе на C переменные a, b, c, x, y и z описаны следующим образом:  char a; int b; int * c; float x; double y; float * z;  Отметьте символами “C”, “N” и “D” корректные (Correct), некорректные (Non-correct) и опасные (или сомнительные) с вашей точки зрения (Dangerous) присваивания

  b = c;

  x = a;

  b = y;

  z = &a;

1.2. (3) Предположим, что  в программе на C переменные a, b и x определены следующим образом: int a=1, b=10; float x=3.13; Укажите против каждого цикла сколько раз будут итерировано его:

 do a++; while (0);

 do a++; while (1);

 for( ; a<b ; b--)x=x*x;

 for( ; a<b ; ) a++;

 1.2.   (4) Дана следующая С-программа:

int N= 5; float S; float X[100] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

void oper (float * X, float Y[ ], int Z)

{float S=1; int I; for (I=0 ; I<Z ; I++) S=S*Y[I]; *X=S-10; }

void main (void) {X[5]=100; oper(&S, X, 5); }

Укажите значение переменной S после выполнения этой программы: S=

(5) Структура данных – это реализация средствами языка программирования абстрактного типа данных. Предложите на языке C структуру данных для для эффективной реализации двусвязного списка из записей сведений о неболее чем 100 студентах, в котором каждая запись содержит фамилию, номер зачетной книжки, и средний балл.  Для представления решения используйте дополнительный чистый лист.

 1.3.   (4) Какие из перечисленных ниже утверждений корректны для языка C? Корректные утверждения обвести овалом, ложные – зачеркнуть и привести контрпример на языке C (на свободном месте после утверждения). 

 a)   if (CONDITION) STATEMENT1 else STATEMENT2 ;

эквивалентно

if (CONDITION) STATEMENT1 ; if !(CONDITION) STATEMENT2 ;

 b)  switch (CONDITION) { case VALUE1 : STATEMENT1 ;

case VALUE2 : STATEMENT2 ;

  .........

case VALUE3 : STATEMENT3 ;

default : STATEMENT4} ;

эквивалентно

if (CONDITION = VALUE1) STATEMENT1 else {

if (CONDITION = VALUE2) STATEMENT2 else {

......... {

if (CONDITION = VALUE3) STATEMENT3 else STATEMENT4

} .........  } } ;

 c)  for (INITIALIZATION ; CONDITION ; INCREMENT) STATEMENT

эквивалентно

INITIALIZATION ; while (CONDITION) {STATEMENT ; INCREMENT}

 2.  Разработка, спецификация, реализация, верификация и тестирование алгоритмов и программ.

 2.1.   Утверждается, что следующий алгоритм вычисляет в переменной C квадрат начального значения переменной A.

VAR A, B, C : Z+; /* Z+ - целые положительные числа */ 

B:=A ; C:= 0 ;

WHILE B>1 DO

{IF odd(B) DO C:=C+A ; /* odd – проверка нечетности числа */

A:= A+A ; B:= B div(2) /* div – деление нацело */

} ;

C:= A+C

 a)  (3) Предложите и мотивируйте систему тестов методом черного ящика для этого алгоритма. Ответ представьте на свободном пространстве ниже.

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

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

 a)  (база=3) Спроектируйте на псевдокоде и специфицируйте предусловием и постусловием алгоритм проверки пересекаются ли отрезки [B1, W1] и [B2, W2], где B1 и B2 – пара черных точек, а  W1 и W2 – пара белых точек на плоскости.

 b)  (+2 к базе) Докажите методом Флойда частичную корректность спроектированного и специфицированного алгоритма. 

 c)  (+1 к базе) Реализуйте на языке C спроектированный алгоритм в виде функции bool intersect(float XB1, float YB1, float XW1, float YW1, float XB2, float YB2, float XW2, float YW2), где  (XB1,YB1), (XW1,YW1), (XB2,YB2) и (XW2,YW2) – Евклидовы координаты точек B1, W1,  B2 и W2.

 d)  (+2 к базе) Предложите и мотивируйте систему тестов методом черного ящика для функции float cubroot(float Y, double E) на языке C, которая  возвращает значение кубического корня из Y с точностью E.

 3.  Дополнительные вопросы из разных тем.

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

 3.1.   (4) Какова асимптотическая сложность T(N) следующего алгоритма? T(N) = ...................... (где N – это начальное значение переменной A).  

VAR A, B, C : Z+; /* Z+ - целые положительные числа */ 

B:=A ; C:= 0 ;

WHILE B>1 DO

{IF odd(B) DO C:=C+A ; /* odd – проверка нечетности числа */

A:= A+A ; B:= B div(2) /* div – деление нацело */

} ;

C:= A+C

 3.2.   (3) Алгоритмы сортировки выбором и вставкой состоят из двух вложенных циклов каждый. Будем называть этапом итерацию самого внешнего цикла. Показать поэтапное состояние массива из 9 целых чисел, начальное состояние которого 9, 1, 2, 8, 4, 3, 7, 5, 6 при сортировке выбором и вставкой. Ответы представить в следующей таблице.

Сортировка выбором	Сортировка вставкой
9,     1,     2,     8,     4,     3,     7,     5,     6	9,     1,     2,     8,     4,     3,     7,     5,     6