СОГЛАСОВАНО						УТВЕРЖДАЮ
Заведующий кабинетом						Директор МУК
Технологического образования					Петроградского района
ГУПМ Санкт-Петербурга						Санкт-Петербурга
________________Н.Е.Жигунов				_________А.А.Борщевский
<___>___________2001г.					<___>____________2001г.

МАТЕРИАЛЫ
для проведения итоговой аттестации
учащихся 11 классов в 2001 г.
профиль.специальность программист-лаборант

Учитель: Дуденков Я.В.

Зам. Директора по УВР:					Т.Д.Цыбульская

Порядок проведения экзамена

1.	Итоговая аттестация проводится в форме устного экзамена по билетам.
2.	В билет входят два теоретических вопроса и одно практическое задание.
3.	На подготовку теоретической части и ответ дается 30 минут. На выполнение практического задания отводится 60-90 минут.
4.	При выставлении оценки за экзамен решающую роль играет оценка за практическую часть.

Экзаменационные вопросы

1.	Каково место Windows 95 среди операционных систем? Есть ли у Windows 95 недостатки?
2.	Как приготовиться к инсталляции и проинсталлировать Windows 95?
3.	Рабочий стол Windows 95, зачем нужны значки и ярлыки?
4.	Что делает приложение My Computer?
5.	Как пользоваться корзинкой "для мусора" Recycle Bin?
6.	Что делать с кнопкой Start?
7.	Как получить помощь и оценить системные ресурсы?
8.	Как подружиться с мышкой, как облегчить работу с мышкой?
9.	Как создать новые ярлыки и папки?
10.	Как запустить приложения, установленные в Windows 95?
11.	Как запустить внешние приложения?
12.	Как работать с окнами приложений, зачем нужен Переключатель задач Taskbar?
13.	Что делают Переключатель языков и приложение Notepad?
14.	Как прогуляться по Windows с ее Проводником Explorer?
15.	Как работать с документами и файлами?
16.	Как завершить работу с Windows 95?
17.	Как работать с калькулятором?
18.	Что такое буфер обмена Clipboard?
19.	Как работать с текстовым редактором WordPad?
20.	Что делает графический редактор Paint?
21.	Как работать с приложениями MS-DOS?
22.	Как просмотреть наборы символов Windows 95?
23.	Можно ли работать с Norton Commander?
24.	Как копировать гибкие диски?
25.	Как отформатировать гибкий диск?
26.	Как выполнить дефрагментацию дисков?
27.	Зачем нужно сканирование дисков?
28.	Зачем нужна контрольная панель?
29.	Что дает Windows 95 для приложений MS-DOS?
30.	Как работают 16-битовые приложения, в чем преимущества 32-битовых приложений?
31.	Каковы улучшения в файловой системе Windows 95?
32.	Каковы улучшения в подсистеме печати Windows 95?
33.	Насколько устойчива Windows 95 к сбоям?
34.	Как Windows 95 поддерживает видеосистему ПК?
35.	Каковы возможности контрольной панели?
36.	Как управлять дисплеем и видеокартой?
37.	Как обеспечивается установка и выбор принтеров?
38.	Как узнать и установить дату и время?
39.	Как настроить клавиатуру ПК, как разобраться с наборами символов?
40.	Что делают Мастера Windows 95, Как установить новые программы и убрать ненужные?

Перечень практических заданий
Задание 1. Пусть a[1], ..., a[n] - целые числа. Требуется построить массив b[1], ..., b[n], содержащий те же числа, для которых b[1] <= ... <= b[n].
Замечание. Среди чисел a[1]...a[n] могут быть равные. Требуется, чтобы каждое целое число входило в b[1]...b[n] столько же раз, сколько и в a[1]...a[n].
Решение. Удобно считать, что числа a[1]..a[n] и b[1]..b[n] представляют собой начальное и конечное значения массива x. Требование "a и b содержат одни и те же числа" будет заведомо выполнено, если в процессе работы мы ограничимся перестановками элементов x.
...
k := 0;
k наименьших элементов массива x установлены на свои места
while k <> n do begin
 s := k + 1; t := k + 1;
 x[s] - наименьший среди x[k+1]...x[t] 
 while t<>n do begin
  t := t + 1;
  if x[t] < x[s] then begin
   s := t;
  end;
 end;
 x[s] - наименьший среди x[k+1]..x[n] 
 ... переставить x[s] и x[k+1];
 k := k + 1;
end;
Задание 2. Написать рекурсивную процедуру вычисления факториала целого положительного числа n (т.е. произведения чисел 1..n, обозначаемого n!).
Решение. Используем равенства 1!=1, n!= (n-1)!*n.
procedure factorial (n: integer; var fact: integer);
 положить fact равным факториалу числа y
begin
 if n=1 then begin
  fact:=1;
 end else begin n>1
  factorial (n-1, fact);
  fact:= fact*n;
 end;
end;
С использованием процедур-функций можно написать так:
function factorial (n: integer): integer;
begin
 if n=1 then begin
  factorial:=1;
 end else begin n>1
  factorial:=  factorial (n-1)*n;
 end;
end;
Задание 3. Используя лишь команды write(x) при x=0..9, написать рекурсивную программу печати десятичной записи целого положительного числа n.
Решение. Здесь использование рекурсии облегчает решение (проблема была в том, что цифры легче получать с конца, а печатать надо с начала).
procedure print (n:integer); n>0
begin
 if n<10 then begin
  write (n);
 end else begin
  print (n div 10);
  write (n mod 10);
 end;
end;
Задание 4. Написать программу, которая печатает по одному разу все последовательности длины n, составленные из чисел 1..k (их количество равно k в степени n).
Решение. Программа будет оперировать с массивом a[1]..a[n] и числом t. Рекурсивная процедура generate печатает все последовательности, начинающиеся на a[1]..a[t]; после ее окончания t имеет то же значение, что и в начале:
procedure generate;
 var i,j : integer;
begin
 if t = n then begin
  for i:=1 to n do begin
   write(a[i]);
  end;
  writeln;
 end else begin t < n
  for j:=1 to k do begin
   t:=t+1;
   a[t]:=j;
   generate;
   t:=t-1;
  end;
 end;
end;
Основная программа теперь состоит из двух операторов: t:=0; generate;

Задание 5. Написать программу, которая печатала бы все перестановки чисел 1..n по одному разу.
Решение. Программа оперирует с массивом a[1]..a[n], в котором хранится перестановка чисел 1..n. Рекурсивная процедура generate в такой ситуации печатает все перестановки, которые на первых t позициях совпадают с перестановкой a; по выходе из нее переменные t и a имеют те же значения, что и до входа. Основная программа такова:
for i:=1 to n do begin a[i]:=i; end;
t:=0;
generate;
вот описание процедуры:
procedure generate;
 var i,j : integer;
begin
 if t = n then begin
  for i:=1 to n do begin
   write(a[i]);
  end;
  writeln;
 end else begin t < n
  for j:=t+1 to n do begin
   поменять местами a[t+1] и a[j]
   t:=t+1;
   generate;
   t:=t-1;
   поменять местами a[t+1] и a[j]
  end;
 end;
end;
Задание 6. 10.1.1. Имеется последовательность символов x[1]..x[n]. Определить, имеются ли в ней идущие друг за другом символы "abcd". (Другими словами, требуется выяснить, есть ли в слове x[1]..x[n] подслово "abcd".)
Решение. Имеется примерно n (если быть точным, n-3) позиций, на которых может находиться искомое подслово в исходном слове. Для каждой из позиций можно проверить, действительно ли там оно находится, сравнив четыре символа. Однако есть более эффективный способ. Читая слово x[1]..x[n] слева направо, мы ожидаем появления буквы 'a'. Как только она появилась, мы ждем за ней букву 'b', затем 'c', и, наконец, 'd'. Если наши ожидания оправдываются, то слово "abcd" обнаружено. Если же какая-то из нужных букв не появляется, мы вынуждены начинать все сначала.
Этот простой алгоритм можно описать в разных терминах. Используя терминологию так называемых конечных автоматов, можно сказать, что при чтении слова x слева направо мы в каждый момент находимся в одном из следующих состояний: "начальное" (0), "сразу после a" (1), "сразу после ab" (2), "сразу после abc" (3) и "сразу после abcd" (4). Читая очередную букву, мы переходим в следующее состояние по правилу
Текущее	Очередная	Новое
состояние	буква	состояние
0                a	1
0              кроме a	0
1                b	2
1                a	1
1              кроме a,b	0
2                c	3
2                a	1
2              кроме a,c	0
3                d	4
3                a	1
3              кроме a,d	0
Как только мы попадем в состояние 4,  работа заканчивается.
Соответствующая программа очевидна: i:=1; state:=0;
i - первая непрочитанная буква, state - состояние
while (i<> n+1) and (state <> 4) do begin
if state = 0 then begin
if x[i] = a then begin
state:= 1;
end else begin
state:= 0;
end;
end else if state = 1 then begin
if x[i] = b then begin
state:= 2;
end else if x[i] = a then begin
state:= 1;
end else begin
state:= 0;
end;
end else if state = 2 then begin
if x[i] = c then begin
state:= 3;
end else if x[i] = a then begin
state:= 1;
end else begin
state:= 0;
end;
end else if state = 3 then begin
if x[i] = d then begin
state:= 4;
end else if x[i] = a then begin
state:= 1;
end else begin
state:= 0;
end;
end;
end;
answer := (state = 4);
Иными словами, мы в каждый момент храним информацию о том, какое максимальное начало нашего образца "abcd" является концом прочитанной части. (Его длина и есть то "состояние", о котором шла речь.)

Задание 7. Даны два натуральных числа a и b, не равные нулю одновременно. Вычислить НОД (a,b) - наибольший общий делитель а и b.
Решение (1 вариант).
if a > b then begin
 k := a;
end else begin
 k := b;
end;
k = max (a,b)
инвариант: никакое число, большее k, не является общим делителем
while not (((a mod k)=0) and ((b mod k)=0)) do begin
 k := k - 1;
end;
k - общий делитель, большие - нет
(2 вариант - алгоритм Евклида). Будем считать , что НОД (0,0) = 0. Тогда НОД (a,b) = НОД (a-b,b) = НОД (a,b-a); НОД (a,0) = НОД (0,a) = a для всех a,b>=0.
m := a; n := b;
инвариант: НОД (a,b) = НОД (m,n); m,n >= 0 
while not ((m=0) or (n=0)) do begin
 if m >= n then begin
  m := m - n;
 end else begin
  n := n - m;
 end;
end;
if m = 0 then begin
 k := n;
end else begin
 k := m;
end;

Задание 8. Составить программу, печатающую разложение на простые множители заданного натурального числа n > 0 (другими словами, требуется печатать только простые числа и произведение напечатанных чисел должно быть равно n; если n = 1, печатать ничего не надо).
Решение (1 вариант).
k := n;
инвариант:  произведение напечатанных чисел и k равно
n, напечатаны только простые числа
while not (k = 1) do begin
 l := 2;
 инвариант: k не имеет делителей в интервале (1,l)
 while k mod l <> 0 do begin
  l := l + 1;
 end;
 l - наименьший делитель k, больший 1, следовательно,
  простой
 writeln (l);
 k:=k div l;
end;
(2 вариант).
k := n; l := 2;
произведение k и напечатанных чисел равно n; напечатанные числа просты; k не имеет делителей, меньших l
while not (k = 1) do begin
 if k mod l = 0  then begin
  k делится на l и не имеет делителей,
    меньших l, значит, l просто
  k := k div l;
  writeln (l);
 end else begin
   k не делится на l 
  l := l + 1;
 end;
end;
Задание 9. Разрешим использовать команды write (i) лишь при i = 0,1,2,...,9. Составить программу, печатающую десятичную запись заданного натурального числа n > 0. (Случай n = 0 явился бы некоторым исключением, так как обычно нули в начале числа не печатаются, а для n = 0 - печатаются.)
Решение.
base:=1;
base - степень 10, не превосходящая n
while 10 * base <= n do begin
 base:= base * 10;
end;
base - максимальная степень 10, не превосходящая n
k:=n;
инвариант: осталось напечатать k с тем же числом
знаков, что в base; base = 100..00
while base <> 1 do begin
 write(k div base);
 k:= k mod base;
 base:= base div 10;
end;
base=1; осталось напечатать однозначное число k
write(k);
(Типичная ошибка при решении этой задачи: неправильно обрабатываются числа с нулями посередине. Приведенный инвариант допускает случай, когда k < base; в этом случае печатание k начинается со старших нулей.)
Задание 10. Дано натуральное число n > 1. Определить длину периода десятичной записи дроби 1/n.
Решение. Период дроби равен периоду в последовательности остатков (докажите это; в частности, надо доказать, что он не может быть меньше). Кроме того, в этой последовательности все периодически повторяющиеся все члены различны, а предпериод имеет длину не более n. Поэтому достаточно найти (n+1)-ый член последовательности остатков и затем минимальное k, при котором (n+1+k)-ый член совпадает с (n+1)-ым.
l := 0; r := 1;
инвариант: r/n = результат отбрасывания l знаков в 1/n
while l <> n+1 do begin
 r := (10 * r) mod n;
 l := l + 1;
end;
c :=	r;
c =	(n+1)-ый член последовательности остатков
r :=	(10 * r) mod n;
k :=	0;
r =	(n+k+1)-ый член последовательности остатков
while r <> c do begin
 r := (10 * r) mod n;
 k := k + 1;
end;
Задание 11. Дан массив x: array [1..n] of integer. Найти количество различных чисел среди элементов этого массива. Оформить решение в виде функции. (Число действий должно быть порядка n*n.)

Задание 12. Коэффициенты многочлена хранятся в массиве a: array [0..n] of integer (n - натуральное число, степень многочлена). Вычислить значение этого многочлена в точке x (т. е. a[n]*(x в степени n)+...+a[1]*x+a[0]).
Решение. (Описываемый алгоритм называется схемой Горнера.)
k := 0; y := a[n];
инвариант: 0 <= k <= n,
y= a[n]*(x в степени k)+...+a[n-1]*(x в степени k-1)+...+
+ a[n-k]*(x в степени 0)
while k<>n do begin
 k := k + 1;
 y := y * x + a [n - k];
end;

Задание 13. Даны два возрастающих массива x: array [1..k] of integer и y: array [1..l] of integer. Найти количество общих элементов в этих массивах (т. е. количество тех целых t, для которых t = x[i] = y[j] для некоторых i и j). (Число действий порядка k+l.)
Решение.
k1:=0; l1:=0; n:=0;
инвариант: 0<=k1<=k; 0<=l1<=l; искомый ответ = n + количество
общих элементов в x[k1+1]...x[k] и y[l1+1]..y[l]
while (k1 <> k) and (l1 <> l) do begin
 if x[k1+1] < y[l1+1] then begin
  k1 := k1 + 1;
 end else if x[k1+1] > y[l1+1] then begin
  l1 := l1 + 1;
 end else begin x[k1+1] = y[l1+1]
  k1 := k1 + 1;
  l1 := l1 + 1;
  n := n + 1;
 end;
end;
k1 = k или l1 = l, поэтому одно из множеств, упомянутых в инварианте, пусто, а n равно искомому ответу

Задание 14. Даны два неубывающих массива x: array [1..k] of integer и y: array [1..l] of integer. Найти число различных элементов среди x[1],...,x[k], y[1],...,y[l]. (Число действий порядка k+l.)

Задание 15. Даны два массива x[1] <= ... <= x[k] и y[1] <= ... <= y[l]. "Соединить" их в массив z[1] <= ... <= z[m] (m = k+l; каждый элемент должен входить в массив z столько раз, сколько раз он входит в общей сложности в массивы x и y). Число действий порядка m.
Решение.
k1 := 0; l1 := 0;
инвариант: ответ получится, если к  z[1]..z[k1+l1]  приписать справа соединение массивов x[k1+1]..x[k] и y[l1+1]..y[l] while (k1 <> k) or (l1 <> l) do begin
 if k1 = k then begin
  l1 < l
  l1 := l1 + 1;
  z[k1+l1] := y[l1];
 end else if l1 = l then begin
  k1 < k
  k1 := k1 + 1;
  z[k1+l1] := x[k1];
 end else if x[k1+1] <= y[l1+1] then begin
  k1 := k1 + 1;
  z[k1+l1] := x[k1];
 end else if x[k1+1] >= y[l1+1] then begin
  l1 := l1 + 1;
  z[k1+l1] := y[l1];
 end else begin
   такого не бывает 
 end;
end;
k1 = k, l1 = l, массивы соединены
Этот процесс можно пояснить так. Пусть у нас есть две стопки карточек, отсортированных по алфавиту. Мы соединяем их в одну стопку, выбирая каждый раз ту из верхних карточек обеих стопок, которая идет раньше в алфавитном порядке.

Задание 16. Некоторое число содержится в каждом из трех целочисленных неубывающих массивов x[1] <= ... <= x[p],  y[1]  <=  ... <= y[q], z[1] <= ... <= z[r]. Найти одно из таких чисел. Число действий должно быть порядка p + q + r.
Решение.
p1:=1; q1=1; r1:=1;
инвариант: x[p1]..x[p], y[q1]..y[q], z[r1]..z[r]
содержат общий элемент 
while not ((x[p1]=y[q1]) and (y[q1]=z[r1])) do begin
 if x[p1]<y[q1] then begin
  p1:=p1+1;
 end else if y[q1]<z[r1] then begin
  q1:=q1+1;
 end else if z[r1]<x[p1] then begin
  r1:=r1+1;
 end else begin
   так не бывает 
 end;
end;
x[p1] = y[q1] = z[r1]
writeln (x[p1]);

Задание 17. Элементами массива a[1..n] являются неубывающие массивы [1..m] целых чисел (a: array [1..n] of array [1..m] of integer; a[1][1] <= ... <= a[1][m], ..., a[n][1] <= ... <= a[n][m]). Известно, что существует число, входящее во все массивы a[i] (существует такое х, что для всякого i из [1..n] найдётся j из [1..m], для которого a[i][j]=x). Найти одно из таких чисел х.
Решение. Введем массив b[1]..b[n], отмечающий начало "остающейся части" массивов a[1]..a[n].
for k:=1 to n do begin
  b[k]:=1;
end;
eq := true;
for k := 2 to n do begin
 eq := eq and (a[1][b[1]] = a[k][b[k]]);
end;
инвариант: оставшиеся части  пересекаются,  т.е.  существует такое  х,  что для всякого i из [1..n] найдётся j из [1..m], не меньшее b[i], для которого a[i][j] =  х;  eq  <=>  первые элементы оставшихся частей равны
while not eq do begin
 s := 1; k := 1;
 a[s][b[s]] - минимальное среди a[1][b[1]]..a[k][b[k]]
 while k <> n do begin
  k := k + 1;
  if a[k][b[k]] < a[s][b[s]] then begin
   s := k;
  end;
 end;
 a[s][b[s]] - минимальное среди a[1][b[1]]..a[n][b[n]]
 b [s] := b [s] + 1;
 for k := 2 to n do begin
  eq := eq and (a[1][b[1]] = a[k][b[k]]);
 end;
end;
writeln (a[1][b[1]]);

Задание 18. Подсчитать количество нулей в массиве x. (Составить фрагмент программы, не меняющий значения x, после исполнения которого значение некоторой целой переменной k равнялось бы числу нулей среди компонент массива x.) Решение оформить в виде функции.
Решение.
...
инвариант: k= число нулей среди x[1]...x[i] 
...

Билеты
для проведения государственной (итоговой) аттестации 
учащихся 11 класса
профиль: программист-лаборант

Билет № 1.
1.	Каково место Windows 95 среди операционных систем? Есть ли у Windows 95 недостатки?
2.	Как работать с приложениями MS-DOS?
3.	Практическое задание № 1

Билет № 2.
1.	Как приготовиться к инсталляции и проинсталлировать Windows 95?
2.	Как просмотреть наборы символов Windows 95?
3.	Практическое задание № 2

Билет № 3.
1.	Рабочий стол Windows 95, зачем нужны значки и ярлыки?
2.	Можно ли работать с Norton Commander?
3.	Практическое задание № 3

Билет № 4.
1.	Что делает приложение My Computer?
2.	Как копировать гибкие диски?
3.	Практическое задание № 4

Билет № 5.
1.	Как пользоваться корзинкой "для мусора" Recycle Bin?
2.	Как отформатировать гибкий диск?
3.	Практическое задание № 5

Билет № 6.
1.	Что делать с кнопкой Start?
2.	Как выполнить дефрагментацию дисков?
3.	Практическое задание № 6

Билет № 7.
1.	Как получить помощь и оценить системные ресурсы?
2.	Зачем нужно сканирование дисков?
3.	Практическое задание № 7

Билет № 8.
1.	Как настроить с мышь, как облегчить работу с мышкой?
2.	Зачем нужна контрольная панель?
3.	Практическое задание № 8

Билет № 9.
1.	Как создать новые ярлыки и папки?
2.	Что дает Windows 95 для приложений MS-DOS?
3.	Практическое задание № 9

Билет № 10.
1.	Как запустить приложения, установленные в Windows 95?
2.	Как работают 16-битовые приложения, в чем преимущества 32-битовых приложений?
3.	Практическое задание № 10

Билет № 11.
1.	Как запустить внешние приложения?
2.	Каковы улучшения в файловой системе Windows 95?
3.	Практическое задание № 11

Билет № 12.
1.	Как работать с окнами приложений, зачем нужен Переключатель задач Taskbar?
2.	Каковы улучшения в подсистеме печати Windows 95?
3.	Практическое задание № 12

Билет № 13.
1.	Что делают Переключатель языков и приложение Notepad?
2.	Насколько устойчива Windows 95 к сбоям?
3.	Практическое задание № 13

Билет № 14.
1.	Как работать в Windows с ее Проводником Explorer?
2.	Как Windows 95 поддерживает видеосистему ПК?
3.	Практическое задание № 14

Билет № 15.
1.	Как работать с документами и файлами?
2.	Каковы возможности контрольной панели?
3.	Практическое задание № 15

Билет № 16.
1.	Как завершить работу с Windows 95?
2.	Как управлять дисплеем и видеокартой?
3.	Практическое задание № 16

Билет № 17.
1.	Как работать с калькулятором?
2.	Как обеспечивается установка и выбор принтеров?
3.	Практическое задание № 17

Билет № 18.
1.	Что такое буфер обмена Clipboard?
2.	Как узнать и установить дату и время?
3.	Практическое задание № 18

Билет № 19.
1.	Как работать с текстовым редактором WordPad?
2.	Как настроить клавиатуру ПК, как разобраться с наборами символов?
3.	Практическое задание № 19

Билет № 20.
1.	Что делает графический редактор Paint?
2.	Что делают Мастера Windows 95, Как установить новые программы и убрать ненужные?
3.	Практическое задание № 20