Самитов Р.К.
Примеры вопросов письменного экзамена
По курсу «Информатика» 2-й семестр.
Темы курса, вынесенные на экзамен:
§ Обработка файлов - типизированных и текстовых.
§ Данные типа указатель - определение, описание и манипулирование.
§ Методы разработки алгоритмов - структурных диаграмм (для текстов и файлов), конечных состояний, стековые алгоритмы.
Кроме того, в задание входит задача на алгоритмизацию и аккуратную реализацию алгоритма.
Обработка файлов - типизированных и текстовых.
Типизированный файл записей хранит данные о плане выпуска деталей в цехах предприятия, один компонент содержит сведения об одном цехе: наименование цеха (15 символов), данные о 50-ти деталях: о каждой детали - наименование (20 символов), вес одной детали (вещественное число), план выпуска на каждый из 12-ти месяцев (12 целых чисел).
Сформировать текстовый файл: одна строка содержит сведения об одном цехе: наименование цеха, общий вес плана выпуска по этому цеху на каждый из 12-ти месяцев (12 вещественных чисел), «ВЕС ВСЕГО» - сумма весов по строке.
15 позиций. | 10п. | 10п. | 10п. | 20п. | ||||||
НАИМЕНОВАНИЕ | ... | ВЕС ВСЕГО | ||||||||
... | ... | ... | ... | ... | ... | |||||
ИТОГО | S вес | S вес | S вес | S вес |
«Общий вес плана выпуска (по месяцам)» выводить в формате - Х... Х.ХХ, «ВЕС ВСЕГО» и «(суммарный по столбцу) S вес» - в форме с плавающей точкой.
Ответ – Pascal:
PROGRAM pp; TYPE tt= RECORD nc:STRING[15]; d: ARRAY[1..50] OF RECORD
nd:STRING[20]; v:REAL; p: ARRAY[1..12] OF INTEGER END END;
VAR vh: FILE OF tt; vih:TEXTFILE; x:tt; y: ARRAY[1..13] OF REAL; i,j:INTEGER;
s,ss:REAL; BEGIN RESET(vh); REWRITE(vih); FOR j:=1 TO 13 DO y[j]:=0;
WHILE NOT EOF(vh) DO BEGIN READ(vh,x); WRITE(vih,x.nc,’’:15-lenght(x.nc));
ss:=0; FOR j:=1 TO 12 DO BEGIN s:=0; FOR i:=1 TO 50 DO
s:=s+x.d[i].v*x.d[i].p[j]; WRITE(vih,s:11:2); ss:=ss+s; y[j]:=y[j]+s END;
WRITELN(vih,ss:21); y[13]:=y[13]+ss END; WRITE(vih,’ИТОГО’:15);
FOR j:=1 TO 12 DO WRITE(vih,y[j]:11); WRITELN(vih,y[13]:21) END.
Ответ – C/C++:
main(){ typedef struct{char nc[15]; struct{char nd[20]; double v;
int p[12];}d[50];}tt;
ifstream vh; ofstream vih; tt x; double y[13],s,ss; int i,j;
vh.open("vh.BIN",ios::binary); vih.open("vih.txt"); for(j=0;j<13;j++) y[j]=0;
while(vh.peek()!=EOF){ vh.read((char *)&x,sizeof(tt));
vih<<setiosflags(ios::left)<<setw(15)<<x.nc<<resetiosflags(ios::left);
ss=0; for(j=0;j<12;j++){ s=0; for(i=0;i<50;i++) s=s+x.d[i].v*x.d[i].p[j];
vih<<setiosflags(ios::fixed)<<setw(11)<<setprecision(2)<<s
<<resetiosflags(ios::fixed); ss=ss+s; y[j]=y[j]+s;}
vih<<setiosflags(ios::scientific)<<setw(21)<<setprecision(12)<<ss
<<resetiosflags(ios::scientific)<<'\n'; y[12]=y[12]+ss; }
vih<<setw(15)<<"ИТОГО"; for(j=0;j<12;j++)
vih<<setiosflags(ios::scientific)<<setw(11)<<setprecision(2)<<y[j];
vih<<setw(21)<<setprecision(12)<<y[12]<<resetiosflags(ios::scientific)<<'\n';
vih.close();
}
Данные типа указатель.
Элементы некоей динамической структуры данных могут указывать друг на друга, но каждый элемент может указывать не более чем на два. Имеется 5 элементов такой структуры данных, на рисунке обозначенные (1)-(5) и связанные, как показано на этом рисунке. Дана переменная «p» с заданным значением типа указатель на элемент, обозначенный (1).
§ Обменять значениями информации элементы, обозначенные (1) и (4).
§ Добавить 2 новых элемента со значением информации 123 и 234, связать их с имеющимися, как показано на рисунке пунктирными линиями.
§ Исключить элемент, обозначенный (5), и указатели на него.
Запрещено использовать операцию «Взятие адреса».
Ответ – Pascal:
PROGRAM pp; TYPE tt= RECORD d:INTEGER; r,l:^tt END; VAR p,r5:^tt; dd:INTEGER;
BEGIN dd:=p^.d; p^.d:=p^.l^.d; p^.l^.d:=dd;
r5:=p^.r; new(p^.r); p^.r^.d:=123; p^.r^.l:=nil;
new(p^.r^.r); p^.r^.r^.d:=234; p^.r^.r^.l:=nil; p^.r^.r^.r:=r5^.l;
r5^.l^.r:=nil; dispose(r5) END.
Ответ – C/C++:
main(){ struct tt{ int d; tt *r,*l;}; tt *p,*r5; int dd;
dd=p->d; p->d=p->l->d; p->l->d=dd;
r5=p->r; p->r=new(tt); p->r->d=123; p->r->l=NULL;
p->r->r=new(tt); p->r->r->d=234; p->r->r->l=NULL; p->r->r->r=r5->l;
r5->l->r=NULL; delete(r5);}
Методы разработки алгоритмов.
Ø МЕТОД СТРУКТУРНЫХ ДИАГРАММ. Проверить входной текст на правильность в нижеописанном смысле. Синтаксис правильного текста описывается диаграммой:
При решении такого типа задач вполне допустимо предполагать обязательное наличие «упорчика» в конце файла – символа $. Это означает, что входной файл гарантированно не пустой, и позволяет избавиться от типовых технических «заморочек» в таких задачах. Использование массивов (и строковых переменных) для хранения входного текста снижает ценность решения.
Ответ – Pascal:
PROGRAM pp; VAR Vh: FILE OF CHAR; x: CHAR; LABEL 1,2;
BEGIN RESET(Vh); READ(Vh,x);
IF x='g' THEN BEGIN READ(Vh,x); IF x<>'d' THEN GOTO 1; READ(Vh,x) END
ELSE IF x='h' THEN BEGIN READ(Vh,x); IF x<>'g' THEN GOTO 1; READ(Vh,x) END ELSE GOTO 1;
IF x<>'f' THEN GOTO 1; READ(Vh,x);
WHILE x<>'g' DO
IF x='a' THEN BEGIN READ(Vh,x);
WHILE x<>'f' DO
IF x='x' THEN BEGIN READ(Vh,x);
IF x<>'u' THEN GOTO 1; READ(Vh,x) END
ELSE IF x='z' THEN BEGIN READ(Vh,x);
IF x<>'x' THEN GOTO 1; READ(Vh,x) END
ELSE GOTO 1;
READ(Vh,x);
IF x<>'g' THEN GOTO 1; READ(Vh,x)
END ELSE
IF (x='b')OR(x='c') THEN BEGIN
IF x='b' THEN BEGIN READ(Vh,x);
IF x<>'c' THEN GOTO 1; READ(Vh,x) END
ELSE BEGIN READ(Vh,x);
IF x<>'y' THEN GOTO 1; READ(Vh,x) END;
IF x<>'y' THEN GOTO 1; READ(Vh,x)
END ELSE GOTO 1;
READ(Vh,x);
IF x='$' THEN WRITELN('Текст правильный'); GOTO 2;
1: WRITELN('Текст неправильный'); 2: END.
Ответ – C/C++:
main(){ifstream Vh; char x; Vh.open(”Vh5.TXT”); Vh.get(x);
if(x=='g'){ Vh.get(x); if(x!='d') goto m1; Vh.get(x);}
else if(x=='h'){ Vh.get(x); if(x!='g') goto m1; Vh.get(x);}
else goto m1;
if(x!='f') goto m1; Vh.get(x);
while(x!='g')
if(x=='a'){ Vh.get(x);
while(x!='f')
if(x=='x'){ Vh.get(x);
if(x!='u') goto m1; Vh.get(x);}
else if(x=='z'){ Vh.get(x);
if(x!='x') goto m1; Vh.get(x);}
else goto m1;
Vh.get(x);
if(x!='g') goto m1; Vh.get(x);
} else
if((x=='b')||(x=='c')){
if(x=='b'){ Vh.get(x);
if(x!='c') goto m1; Vh.get(x);}
else { Vh.get(x);
if(x!='y') goto m1; Vh.get(x);}
if(x!='y') goto m1; Vh.get(x);
} else goto m1;
Vh.get(x);
if(x=='$') cout<<”Текст правильный”; goto m2;
m1: cout<<”Текст неправильный”; m2:; }
Ø МЕТОД «СТЕКОВЫЕ АЛГОРИТМЫ». Проверить входной текст на правильность в нижеописанном смысле. Синтаксис правильного текста описывается рекурсивной диаграммой:
Пример правильного текста: a[b,c[d[e],f],g[h[i[k]]]]
текущий символ | |||||
a..z | [ | , | ] | ||
в вершине стека | стек пустой | I | |||
I | [ | [I ® [ | I[I ® V | ||
V | [V ® [ | I[V ® V | |||
[ | I |
§ В стеке: символ I соответствует обнаружению «простой переменной» (’a’..’z’) во входном тексте, символ V - «переменной с индексами»;
§ Пустая клетка означает ситуацию обнаружения ошибки; символ в клетке означает выполнение действия: положить в стек этот символ; слово1 ® слово2 означает действие: вытолкнуть из стека слово1 и положить слово2, причем слово должно лежать в стеке левой буквой вниз и, если в верхней части стека находится не слово1, то имеем ситуацию обнаружения ошибки.
§ Начинаем с пустого стека, текст правильный - если он сворачивается в символ стека I или V.
Ответ – Pascal:
PROGRAM pp; VAR vh:FILE OF CHAR; x:CHAR; s:ARRAY[1..100] OF CHAR; js:INTEGER;
LABEL 1,2; BEGIN RESET(vh); js:=0; WHILE NOT EOF(vh) DO BEGIN READ(vh,x);
IF (js=0)OR(s[js]= ’[’) THEN
IF (’a’<=x)AND(x<=’z’) THEN BEGIN js:=js+1; s[js]:=’I’ END ELSE GOTO 1
ELSE IF s[js]=’I’ THEN
IF x=’[’ THEN BEGIN js:=js+1; s[js]:=’[’ END ELSE
IF x=’,’ THEN IF (js>1)AND(s[js-1]=’[’) THEN js:=js-1 ELSE GOTO 1 ELSE
IF x=’]’ THEN IF (js>2)AND(s[js-1]=’[’)AND(s[js-2]=’I’)
THEN BEGIN js:=js-2; s[js]:=’V’ END ELSE GOTO 1 ELSE
GOTO 1
ELSE IF s[js]=’V’ THEN
IF x=’,’ THEN IF (js>1)AND(s[js-1]=’[’) THEN js:=js-1 ELSE GOTO 1 ELSE
IF x=’]’ THEN IF (js>2)AND(s[js-1]=’[’)AND(s[js-2]=’I’)
THEN BEGIN js:=js-2; s[js]:=’V’ END ELSE GOTO 1 ELSE
GOTO 1
END; IF (js=1)AND((s[js]=’I’)OR(s[js]=’V’)) THEN WRITELN(’Да’)
ELSE WRITELN(’Нет’); GOTO 2; 1:WRITELN(’Нет’); 2: END.
Ответ – C/C++:
main(){ifstream vh; char x,s[100]; int js; vh.open("vh.TXT"); js=-1;
while(vh.peek()!=EOF){ vh.get(x);
if((js==-1)||(s[js]=='['))
if(('a'<=x)&&(x<='z')){ js=js+1; s[js]='I';} else goto m1;
else if(s[js]=='I')
if(x=='['){ js=js+1; s[js]='[';} else
if(x==',') if((js>0)&&(s[js-1]=='[')) js=js-1; else goto m1; else
if(x==']') if((js>1)&&(s[js-1]=='[')&&(s[js-2]=='I'))
{ js=js-2; s[js]='V';} else goto m1; else
goto m1;
else if(s[js]=='V')
if(x==',') if((js>0)&&(s[js-1]=='[')) js=js-1; else goto m1; else
if(x==']') if((js>1)&&(s[js-1]=='[')&&(s[js-2]=='I'))
{ js=js-2; s[js]='V';} else goto m1; else
goto m1;
} if((js==0)&&((s[js]=='I')||(s[js]=='V'))) cout<<"YES-Да";
else cout<<"NO-Нет"; goto m2; m1:cout<<"NO-Нет"; m2:;}