Демонстрационный вариант по информатике 2004

Успеха на экзамене!

Часть А.

 

 

A1

 

 

В понедельник в одном из классов должно быть проведено 4 урока – по математике, физике, информатике и биологии. Учителя высказали свои пожелания для составления расписания. Учитель математики хочет иметь первый или второй урок, учитель физики - второй или третий урок, учитель информатики – первый или четвертый, учитель биологии – третий или четвертый. Какой вариант расписания устроит всех учителей школы?

(Обозначения: М – математика, Ф – физика, И – информатика, Б – биология)

 

1)

ИМБФ

2)

МФБИ

3)

МИФБ

4)

МБФИ

 

Можно решить составив дерево вариантов.

 

                    первый Если математика первый урок, информатика

математика                                  может быть только четвёртым уроком, а значит

                                                      биология только третий урок , а физика

                                      второй     будет только вторым уроком

                                                        Итог: МФБИ

                                       второй     Если математика будет вторым уроком, то третьим

физика                                           уроком может быть физика, значит биология

                                      третий      может быть только четвёртым уроком,

                                                      и на информатику остаётся первый урок.

                                      первый      Итого:  ИМФБ

 

информатика

                                      четвёртый Из данных ответов подходит только 2)

 

                                      третий

биология

                                   

                                    четвёртый

 

Верный ответ: 2).

 

A2

Считая, что каждый символ кодируется одним байтом, оцените информационный объем следующего предложения:

«Мой дядя самых честных правил, Когда не в шутку занемог, Он уважать себя заставил И лучше выдумать не мог.»

 

1)

108 бит

2)

864 бит

3)

108 килобайт

4)

864 килобайт

Для того чтобы определить объём следующего предложения необходимо сосчитать все символы, входящие в предложение т.е. буквы, знаки препинания, пробелы.

Букв здесь – 85, пробелов – 18, знаков препинания – 5.

Итого 85+18+5 = 108 символов

1байт = 8бит .Значит объём будет 108*8 = 864 бит.

Верный ответ: 2)

 

 

 

A3

Шахматная доска состоит из 64 полей: 8 столбцов на 8 строк. Какое
минимальное количество бит потребуется для кодирования координат одного шахматного поля?

 

1)

4

2)

5

3)

6

4)

7

Количество  различных информационных сообщений, которые содержит шахматная доска равно 64. Используя, формулу связи количества различных информационных сообщений с количеством информации можно записать: N = 2I => 2I = 64 => I=6.

Верный ответ: 3).

 

А4

Получено сообщение, информационный объём которого равен 32 битам. Чему равен этот объём в байтах?

 

1)

5

2)

2

3)

3

4)

4

 

1байт = 8 бит => 32бит = 4*8бит =>4 байта.

Верный ответ: 4).

 

A5

Как представлено число 2510 в двоичной системе счисления?

 

1)

10012

2)

110012

3)

100112

4)

110102

 

Будем делить 25 на 2 и потом неполное частное снова на 2 пока получим частное  равное 1.

Получим 25 = 2*12 +1

                 12 = 2*6 + 0

                   6 = 2*3 + 0

                   3 = 2*1 + 1 Частное равно 1.Процесс деления окончен.

Ответ записываем в виде последнего частного и последовательной записи остатков от последнего к первому т.е. 11001

Верный ответ 2)

 

 

A6

Вычислите значение суммы 102 + 108 +1016 в двоичной системе счисления.

 

1)

10100010

2)

11110

3)

11010

4)

10100

Переведём сначала числа в двоичную систему счисления

102 + 108 + 1016 = 102 + 10002 + 100002 = 110102.

Верный ответ 3).

 

A7

Понятное и точное предписание исполнителю при заданных начальных данных выполнить конечную последовательность команд, приводящую к искомому результату, называется

 

1)

моделью

2)

системой

3)

алгоритмом

4)

технологией

По определению последовательное выполнение команд это есть алгоритм.

Верный ответ: 3).

 

A8

Алгоритмическая конструкция какого типа изображена на фрагменте блок-схемы?

1)

линейная

2)

циклическая

3)

разветвляющаяся

4)

вспомогательная

 

 

Алгоритмическая структура такого вида

Представляет собой условный оператор т.е. это

разветвляющая конструкция.

Верный ответ: 3).

 

A9

Определите значение целочисленных переменных x, y и t после выполнения фрагмента программы:

Бейсик

Паскаль

Алгоритмический

x=5
y=7
t=x
' MOD -  стандартная операция, вычисляющая
остаток от деления нацело первого аргумента на второй `
x= y MOD x
y=t

x:=5;

y:=7;
t:=x;
x:= y mod x; {mod -  стандартная операция, вычисляющая остаток от деления нацело первого аргумента на
второй}
y:=t;

x:=5;

y:=7;
t:=x;
x:=mod (y,x); | mod - стандартная функция, вычисляющая      остаток от деления нацело первого аргумента на второй|
y:=t;

 

1)

x=2, y=5, t=5

2)

x=7, y=5, t=5

3)

x=2, y=2, t=2

4)

x=5, y=5, t=5

Сначала в ячейку x положили 5, в у положили 7в  t положили5, затем нашли остаток от деления у на х т.е. 7 = 5*1+2 Получили остаток 2и его положили в ячейку х т.е. заменили 5 на 2 и в у положили t т.е. 7 заменили на 5. Значит ответ будет:

х = 2, у= 5, t = 5.

Верный ответ: 1).

 

 

 

 

 

 

 

A10

Значения двумерного массива задаются с помощью вложенного оператора цикла в представленном фрагменте программы

Бейсик

Паскаль

Алгоритмический

FOR n=1 TO 5

FOR k=1 TO 5

B(n, k)=n+k

NEXT k

NEXT n

for n:=1 to 5 do

for k:=1 to 5 do

          B[n,k]:=n+k;

нц для n от 1 до 5

нц для k от 1 до 5

B[n, k]=n+k

кц

кц

Чему будет равно значение B(2,4)?

 

1)

9

2)

8

3)

7

4)

6

Первый цикл даёт второе значение т.е. 2.

Второй цикл задаёт четвертое значение т.е. 4

Значит B(2,4)=2+4=6.

Верный ответ: 4).

 

 

A11

Для какого имени истинно высказывание:

¬ (Первая буква имени гласная  -> Четвертая буква имени согласная)?

 

1)

ЕЛЕНА

2)

ВАДИМ

3)

АНТОН

4)

ФЕДОР

Импликация ложна, если посылка истинная, а следствие ложно

Первая гласная (ЕЛЕНА, АНТОН) истинная посылка, если следствие будет ЕЛЕНА, то оно будет истинно т.е. импликация будет истинна, а отрицание импликации ложно.

Значит нужно взять следствие АНТОН – оно ложно, значит импликация АНТОН®АНТОН будет  ложна, а отрицание истинно.

Четвёртая согласная (ЕЛЕНА)

Верный ответ: 3.

 

 

A12

Какое логическое выражение равносильно выражению ¬ (А \/ ¬B) ?

 

1)

A \/ B

2)

A /\ B

3)

¬A \/ ¬B

4)

¬A /\ B

 

На основании формулы де Моргана ¬(А \/ В) = ¬А /\ ¬В Мы можем выбрать ответ 4) т.к. ¬(¬В) = В.

Верный ответ: 4).

 

A13

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.

Дан фрагмент таблицы истинности выражения F:

 

X

Y

Z

F

0

0

0

1

0

0

1

0

0

1

0

1

 

Какое выражение соответствует F?

 

1)

¬X/\¬Y/\Z

2)

¬X\/¬Y\/Z

3)

X\/Y\/¬Z

4)

X\/Y\/Z

 

Это будет выражение 3)

Построим таблицу истинности

X

Y

Z

¬Z

X\/Y\/¬Z

0

0

0

1

1

0

0

1

0

0

0

1

0

1

1

 

Верный ответ 3).

 

A14

Укажите верное утверждение:

 

 

1)

Статическая модель системы описывает ее состояние, а динамическая – поведение

2)

Динамическая модель системы описывает ее состояние, а статическая – поведение

3)

Динамическая модель системы всегда представляется в виде формул или графиков

4)

Статическая модель системы всегда представляется в виде формул или графиков

По определению статическая модель описывает состояние модели, а динамическая поведение.

Верный ответ: 1).

 

 

 

А15

Какой из приведенных ниже графиков лучше всего описывает зависимость размера архива от размера исходного файла?

 

1)

 

 

 

 

 

 

3)

 

 

2)

 

 

 

 

 

 

4)

 

Между размером архива и размером файла существует прямо пропорциональная зависимость, т.е. чем больше размер файла тем больше архив.

Верный ответ: 1).

 

A16

Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв - из двух бит, для некоторых - из трех). Эти  коды представлены в таблице:

 

a

b

c

d

e

000

110

01

001

10

 

Определите, какой набор букв закодирован двоичной строкой

1100000100110   

 

1)

baade

2)

badde

3)

bacde

4)

bacdb

110.000.01.001.10

Первая b т.к. 11 нет, а 110 – b, следующая a – 000, потом 01 – c, 001 – d, 10 – e .

Получили bacde.

Верный ответ 3).

 

A17

Цепочка из трех бусин формируется по следующему правилу:
На первом месте в цепочке стоит одна из бусин А, Б, В. На втором – одна из бусин Б, В, Г. На третьем месте – одна из бусин А, В, Г, не стоящая в цепочке на первом или втором месте.

Какая из следующих цепочек создана по этому правилу:

 

1)

АГБ

2)

ВАГ

3)

БГГ

4)

ББГ

 

Варианты могут быть такие:

АБВ, АБГ, АВГ, АГВ

ББА, ББВ, ББГ

БВА, БВГ

БГА, БГВ

ВБА, ВБГ

ВВА, ВВГ

ВГА

 

Верный ответ 4).

А18

Название какого устройства необходимо вписать в пустой блок общей схемы компьютера?

 

 

 

 

 

 

 

 


1)

модем

2)

дисковод

3)

контроллер устройства вывода

4)

внутренняя память

Первые три отвечают за ввод и вывод информации.

Значит это только внутренняя память.

Верный ответ 4).

 

А19

Как называется устройство, выполняющее  арифметические и логические операции, и управляющее другими устройствами компьютера?

 

1)

контроллер

2)

клавиатура

3)

монитор

4)

процессор

 

По определению это устройство процессор.

Верный ответ 4).

 

A20

В каком направлении от ЭЛТ-монитора вредное для человека электромагнитное излучение наибольшее?

 

 

 

 

 

 

 

 

 


1)

A

2)

B

3)

C

4)

D

 

Наиболее вредное для человека излучение с задней стороны монитора.

Верный ответ 4).

 

 

A21

Программы, управляющие оперативной памятью, процессором, внешними устройствами и обеспечивающие возможность работы других программ, называют

 

1)

утилитами

2)

драйверами

3)

операционными системами

4)

системами программирования

 

Такие программы называют операционными системами.

Верный ответ 3).

 

A22

Дано дерево каталогов.

 

 

 

 

 


Определите полное имя файла Doc3.

 

1)

A:/DOC3

2)

A:/DOC3/Doc3

3)

A:/ DOC3/Doc1

4)

A:/TOM3/Doc3

Полное имя A:/TOM3/DOC3.

Верный ответ 4).

 

A23

Сколько записей в нижеследующем фрагменте турнирной таблицы удовлетворяют условию «Место <=5 И (В>4 ИЛИ MЗ>12)» (символ <= означает «меньше или равно»)?

 

Место

Команда
В

Н

П

О

МЗ

МП

1

Боец

5

3

1

18

9

5

2

Авангард

6

0

3

18

13

7

3

Опушка

4

1

4

16

13

7

4

Звезда

3

6

0

15

5

2

5

Химик

3

3

3

12

14

17

6

Пират

3

2

4

11

13

7

 

1)

5

2)

2

3)

3

4)

4

 

Место <= 5 (1,2,3,4,5)

B > 4 (место- 1, 2)

M3 > 12 (место – 2, 3, 5)

Значит общее – 1, 2, 3, 5

Таких записей будет четыре.

Верный ответ 4).

 

A24

Записано 6 строк, каждая имеет свой номер – от “0”- до “5”.

В “0”-й строке записана цифра 0 (ноль).

Каждая последующая строка состоит из двух повторений предыдущей и добавленного в конец своего номера (в “i”-й строке в конце приписана цифра i). Ниже показаны первые четыре строки, сформированные по описанному правилу (в скобках записан номер строки):

(0)   0

(1)   001

(2)   0010012

(3)   001001200100123

Какая цифра стоит в последней строке на 62-м месте (считая слева направо)?

 

1)

1

2)

2

3)

3

4)

4

 

(4) 0010012001001230010012001001234

(5) 001001200100123001001200100123400100120010012300100120010012345

Четвертая строка имеет 31 и последняя  цифра – 4, значит и 62 тоже 4.

Верный ответ 4).

 

 

A25

Следующий фрагмент программы записывает в переменную Max максимальный элемент в двумерном массиве Dist размера NxN, заполненном целыми неотрицательными числами:

 

Max:=0;

for i:=1 to N do

for j:=1 to N do

if Dist [i,j]>Max then Max:=Dist [i,j];

На очень медленном компьютере эта программа при N=1000 работала 5 секунд. Оцените время работы этой программы  на том же компьютере при N=2000:

 

1)

10 сек.

2)

20 сек.

3)

30 сек.

4)

40 сек.

 

Каждая структура for увеличит время своей работы в 2 раза, значит время работы программы возрастёт в 4 раза т.е.программа будет работать 20 сек.

Верный ответ 2).

 

 

A26

Растровое изображение представляется в памяти компьютера в виде

 

 

1)

графических примитивов и описывающих их формул

2)

последовательности расположения и цвета каждого пиксела

3)

математических формул, содержащихся в программе

4)

параметров графических примитивов

 

По определению растровое изображение это последовательность расположения и цвета каждого пиксела.

Верный ответ 2).

 

A27

Дан фрагмент электронной таблицы:

 

 

 

A

B

C

D

1

5

2

4

 

2

10

1

6

 

 

В ячейку D2 введена формула =А2*В1+С1

В результате в ячейке D2 появится значение:

 

1)

6

2)

14

3)

16

4)

24

 

В ячейке D появится A2=10, B1=2, C1=4 => D2=10*2+4=24.

Верный ответ 4).

 

A28

В ячейке А1 электронной таблицы записана формула =D1-$D2. Какой вид приобретет формула после того, как ячейку А1 скопируют в ячейку В1?

 

1)

=E1-$E2

2)

=E1-$D2

3)

=E2-$D2

4)

=D1-$E2

 

 

Значение D1 меняется, а значение D2 остаётся постоянным, значит при копировании в ячейку B1 формула примет вид =E1-$D2.

Верный ответ 2).

 

 

A29

Определите значение целочисленной переменной х после выполнения следующего фрагмента программы:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1)

1

2)

5

3)

10

4)

15

 

Выполняем фрагмент программы х присвоили 55, а у присвоили 75значит 55<>75 истинно, проверяем x>y – неравенство ложно, значит у присвоим разность у – х т.е. у:=20, Возвращаемся к сравнению 55<>20 и 55>20 истинно и х:=55-20=35, продолжим анологично35<>20 и 35>20 => x:=35-20=15, => 15<>20 15>20 – false y:=20-15=5, 15<>5, 15>5 x:=15-5=10 => x:=10, y:=5 10<>5, 10>5 x:=10-5=5 и y:=5- выходим из цикла т.к. х = у.

Верный ответ 2).

 

A30

Дан фрагмент базы данных

 

номер

Фамилия

Имя

Отчество

класс

школа

1

Иванов

Петр

Олегович

10

135

2

Катаев

Сергей

Иванович

9

195

3

Беляев

Иван

Петрович

11

45

4

Носов

Антон

Павлович

7

4

Какую строку будет занимать фамилия ИВАНОВ после проведения сортировки по возрастанию в поле КЛАСС?

 

1)

1

2)

2

3)

3

4)

4

  При сортировке по возрастанию первую строку будет занимать наименьшее значение класса т.е. 7,вторую 9, третью,10. Т.к. Иванов в 10 классе значит фамилия Иванов будет занимать третью строку.

Верный ответ 3).

 

A31

Идентификатор некоторого ресурса сети Интернет имеет следующий вид: http://www.ftp.ru/index.html

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

 

1)

www

2)

ftp

3)

http

4)

html

 

На это указывает первая часть идентификатора т.е. http

Верный ответ 3).

 

A32

Каким условием нужно воспользоваться для поиска в сети Интернет информации о цветах, растущих на острове Тайвань или Хонсю (для обозначения логической операции «ИЛИ» используется символ |, а для операции «И» - символ &)?

 

1)

цветы&(Тайвань|Хонсю)

2)

цветы&Тайвань&Хонсю

3)

цветы|Тайвань|Хонсю

4)

цветы&(остров|Тайвань|Хонсю)

 

Нужно выбрать вариант Цветы и (Тайвань или Хонсю).

Верный ответ 1).

Часть В.

 

B1

В системе счисления с некоторым основанием число 12 записывается в виде 110. Укажите это основание.

Можно записать уравнение 1*x2 +1* x +0 =12 => x2 + x – 12=0. Корни уравнения х1= - 4, х2 = 3. Основание системы положительно и равно 3. Значит

1103 = 12.

Записать ответ 3.

 

 

B2

Укажите значения переменных K, L, M, N, при которых логическое выражение (¬K \/ M)->(¬L \/ M \/ N) ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.

Импликация ложна, когда посылка истинна, а следствие ложно.

Выполним с помощью таблицы истинности.

 

 

 

K

M

¬K

¬K\/M

1

1

0

1

1

0

0

0

0

1

1

1

0

0

1

1

 

K

L

M

N

¬L

¬L \/ M \/ N

1

1

1

1

0

1

1

1

0

1

0

1

1

0

1

1

1

1

1

0

0

1

1

1

0

1

1

1

0

1

0

1

0

1

0

1

0

0

1

1

1

1

0

0

0

1

1

1

1

1

1

0

0

1

1

1

0

0

0

1

1

0

1

0

1

1

1

0

0

0

1

1

0

1

1

0

0

1

0

1

0

0

0

0

0

0

1

0

1

1

0

0

0

0

1

1


Это возможно, когда К = 0, М = 0, L = 1, N = 0

Записать ответ KLMN = 0100.

 

B3

Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика: “Вперед N” (Кузнечик прыгает вперед на N единиц); “Назад M” (Кузнечик прыгает назад на M единиц). Переменные N и M могут принимать любые целые положительные значения. Известно, что Кузнечик выполнил программу из 50 команд, в которой команд “Назад 2” на 12 больше, чем команд “Вперед 3”. Других команд в программе не было. На какую одну команду можно заменить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы?

Пусть «Назад2» было х, «Вперёд3» было у , тогда можно получить систему

 

От какой-то начальной точки вперёд кузнечик переместился на 19*3 =57 единиц, а назад 31*2=62 единицы. Значит кузнечик от начального положения переместился назад на 62-57=5 единиц. Значит данную программу можно заменить одной командой «Назад5»

Записать ответ «Назад5».

Решение вариантов С также, как на http://www.ege.edu.ru

Часть С.

 

C1

Следующая программа, содержащая, по крайней мере, одну ошибку, после устранения ошибок должна определять день недели для произвольного дня месяца. В ней считается, что первое число данного месяца — понедельник. Укажите в листе ответа все ошибки. Взяв эту программу за основу, напишите программу, которая будет решать ту же задачу при условии, что w1 — день недели для первого числа месяца. Значение w1 (целое число от 1 до 7) должно запрашиваться программой. Интересующее нас число месяца d (от 1 до 31) также должно запрашиваться. Предполагается, что ввод данных будет корректным.

 

Программа на языке Паскаль

Программа на языке Бейсик

Var d,w:integer;

begin

  readln(d);

  w:=d div 7;

  case w of

  1:writeln(’понедельник’);

  2:writeln(’вторник’);

  3:writeln(’среда’);

  4:writeln(’четверг’);

  5:writeln(’пятница’);

  6:writeln(’суббота’);

  7:writeln(’воскресенье’);

  end

end.

DIM w, d AS INTEGER

INPUT d

w = d \ 7

IF w = 1 THEN PRINT "понедельник"

IF w = 2 THEN PRINT "вторник"

IF w = 3 THEN PRINT "среда"

IF w = 4 THEN PRINT "четверг"

IF w = 5 THEN PRINT "пятница"

IF w = 6 THEN PRINT "суббота"

IF w = 7 THEN PRINT "воскресенье"

END

 

С1.

Содержание правильного ответа и указания по оцениванию

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

Баллы

В приведенной в тексте задания программе содержатся две ошибки. Вместо операции целочисленного деления (div и \ соответственно) следует использовать операцию mod; воскресенью соответствует остаток 0, а не 7. Исправленная и дополненная программа может выглядеть, например, так

 

Программа на языке Паскаль

Программа на языке Бейсик

var d, w1, w:integer;

begin

  readln(w1, d);

  w:=(d+w1-1) mod 7;

  case w of

  1:writeln(’понедельник’);

  2:writeln(’вторник’);

  3:writeln(’среда’);

  4:writeln(’четверг’);

  5:writeln(’пятница’);

  6:writeln(’суббота’);

  0:writeln(’воскресенье’);

  end

end.

DIM w, w1,d AS INTEGER

INPUT w1, d

w = (d+w1-1) MOD 7

IF w = 1 THEN PRINT "понедельник"

IF w = 2 THEN PRINT "вторник"

IF w = 3 THEN PRINT "среда"

IF w = 4 THEN PRINT "четверг"

IF w = 5 THEN PRINT "пятница"

IF w = 6 THEN PRINT "суббота"

IF w = 0 THEN PRINT "воскресенье"

END

Указаны обе ошибки в исходной программе, программа дополнена верно

3

Указаны обе ошибки в исходной программе, но программа дополнена неверно

2

Указана только одна из двух ошибок

1

Задание не выполнено или выполнено неверно (не найдено ни одной ошибки)

0

Максимальный балл

3

 

C2

Определите, что делает следующая программа. Опишите в бланке ответа, что служит входными данными для программы. Что выводит программа в зависимости от входных данных?

 

Программа на языке Паскаль

Программа на языке Бейсик

Var a:array[1..1000] of integer;

    K,L,R,m,i,n:integer;

    b:boolean;

begin

  readln(K);

  readln(n);

  for i:=1 to n do read(a[i]);

  b:=true;

  for i:=2 to n do

    if a[i-1]>=a[i] then b:=false;

  if not b then

    writeln(’данные некорректны’)

  else

  begin

    L:=1; R:=n;

    b:=false;

    while (L<=R)and not b do

    begin

      m:=(L+R)div 2;

      b:=(a[m]=K);

      if a[m]<K then L:=m+1

                else R:=m-1

    end;

    if b then writeln(m)

         else writeln(0)

  end

end.

DIM K,n,i,b,L,R, a(1000) AS INTEGER

INPUT K

INPUT n

FOR i = 1 TO n

INPUT a(i)

NEXT i

b = 1

FOR i = 2 TO n

IF a(i – 1) >= a(i) THEN b = 0

NEXT i

IF b = 0 THEN

 PRINT "данные некорректны"

 GOTO 10

END IF

L = 1: R = n

b = 0

WHILE (L <= R) AND (b = 0)

m = (L + R) \ 2

IF a(m) = K THEN b = 1 ELSE b = 0

IF a(m) < K THEN

  L = m + 1

 ELSE R = m – 1

END IF

WEND

IF b = 1 THEN PRINT m ELSE PRINT 0

10 END

 

С2.

Содержание правильного ответа и указания по оцениванию

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

Баллы

В условии задания приведена следующая программа:

 

Программа на языке Паскаль

Программа на языке Бейсик

Var a:array[1..1000] of integer;

    K,L,R,m,i,n:integer;

    b:boolean;

begin

  readln(K);

  readln(n);

  for i:=1 to n do read(a[i]);

  b:=true;

  for i:=2 to n do

    if a[i-1]>=a[i] then b:=false;

  if not b then

    writeln(’данные некорректны’)

  else

  begin

    L:=1; R:=n;

    b:=false;

    while (L<=R)and not b do

    begin

      m:=(L+R)div 2;

      b:=(a[m]=K);

      if a[m]<K then L:=m+1

                else R:=m-1

    end;

    if b then writeln(m)

         else writeln(0)

  end

end.

DIM K,n,i,b,L,R, a(1000) AS INTEGER

INPUT K

INPUT n

FOR i = 1 TO n

INPUT a(i)

NEXT i

b = 1

FOR i = 2 TO n

IF a(i – 1) >= a(i) THEN b = 0

NEXT i

IF b = 0 THEN

 PRINT "данные некорректны"

 GOTO 10

END IF

L = 1: R = n

b = 0

WHILE (L <= R) AND (b = 0)

m = (L + R) \ 2

IF a(m) = K THEN b = 1 ELSE b = 0

IF a(m) < K THEN

  L = m + 1

 ELSE R = m – 1

END IF

WEND

IF b = 1 THEN PRINT m ELSE PRINT 0

10 END

Данная программа в упорядоченном по возрастанию массиве методом двоичного поиска ищет индекс элемента, значение которого равно K. Возможны три результата работы программы:

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

2)     если элемент, равный K, в упорядоченном по возрастанию массиве присутствует, то программа выдает его индекс (номер в массиве);

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

 

Верно описаны все варианты 1)–3) результата работы программы в зависимости от входных данных.

3

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

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

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

2

Верно описан только один из трех результатов работы программы (пункт 1), 2) или 3) в описании результатов) или указано назначение программы в целом — поиск элемента, равного К, в массиве. При описании результатов возможны те же неточности, что и в ответе на 2 балла

1

Назначение программы не определено

0

Максимальный балл

3

 

 

C3

Опишите алгоритм поиска трех последовательных элементов, сумма которых максимальна, в числовом массиве из 30 элементов. Решение запишите в словесной форме или на алгоритмических языках Бейсик или Паскаль.

 

 

С3.

Содержание правильного ответа и указания по оцениванию

Баллы

Введем числовые переменные Max и Trio, в которые занесем сумму первых трех элементов массива. Затем в цикле до конца массива: прибавляем к переменной Trio очередной элемент массива, вычитаем из нее первый элемент четверки, сумму которой она содержит, сравниваем результат со значением переменной Max; если он больше, то заносим его в переменную Max. По окончании работы алгоритма переменная Max содержит максимальную сумму трех подряд идущих элементов массива.

 

Примеры правильных и эффективных программ:

На языке Паскаль

На языке Бейсик

const N=30;

var a:array[1..N] of integer;

    Max, Trio, i: integer;

begin

 Trio:=a[1]+a[2]+a[3];

 Max:=Trio;

 for i:=4 to N do

  begin

   Trio:=Trio+a[i]-a[i-3];

   if Trio>Max then Max:=Trio;

  end;

  writeln(Max);

end.

N=30

DIM i, Max, Trio, a(N) AS INTEGER

Trio=a(1)+a(2)+a(3)

Max=Trio

LOOP

FOR i = 4 TO N

  Trio=Trio+a(i)-a(i-4)

  IF Trio > Max THEN Max = Trio

NEXT i

PRINT Max

END

Описан правильный алгоритм, время работы которого линейно зависит от длины массива

2

Описан правильный алгоритм, не допускающий немедленного обобщения на произвольное число элементов или время работы которого более чем линейно по длине массива

1

Задание не выполнено или выполнено неверно

0

Максимальный балл

2

 

C4

Два игрока играют в следующую игру. Перед ними лежат три кучки камней, в первой из которых 2, во второй – 3, в третьей – 4 камня.  У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче или добавляет по два камня в каждую из куч. Выигрывает игрок, после хода которого либо в одной из куч становится не менее 15 камней, либо общее число камней во всех трех кучах становится не менее 25. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

С4.

Содержание правильного ответа и указания по оцениванию

Баллы

Выигрывает первый игрок. Своим первым ходом он должен добавить по два камня в каждую из кучек. Для доказательства рассмотрим неполное дерево игры, обрывая те ветви полного дерева, на которых первый игрок неизбежно проигрывает.

 

Начальное состояние

1-й ход первого игрока

1-й ход второго игрока

2-й ход первого игрока

 

 

 

 

 

4,3,4

4,6,4

приводит к выигрышу второго игрока при любом втором ходе первого игрока

 

 

 

 

 

2,3,4

2,6,4

4,6,4

приводит к выигрышу второго игрока при любом втором ходе первого игрока

 

 

 

 

 

 

2,3,8

2,3,16

выигрыш второго игрока

 

 

 

 

 

 

 

8,5,6

16,5,6 выигрыш первого игрока

 

4,5,6

4,10,6

4,20,6 выигрыш первого игрока

 

 

4,5,12

4,5,24 выигрыш первого игрока

 

 

6,7,8

6,7,16 выигрыш первого игрока

 

Из таблицы видно, что при первом ходе (2,3,4)->(4,5,6) первый игрок выигрывает вторым ходом при любом первом ходе второго игрока, а при любом другом своем первом ходе он проигрывает при правильной игре второго игрока.

 

 

Правильное указание игрока и его первого хода со строгим доказательством правильности с помощью или без помощи дерева игры

3

Правильное указание игрока и его первого хода

2

Правильное указание игрока с неправильным указанием или без указания первого хода

1

Задание не выполнено или выполнено неверно

0

Максимальный балл

3

 

C5

Во входном файле text.dat содержится текст на английском языке, заканчивающийся точкой (другие символы “.” в этом файле отсутствуют). Требуется написать программу на языке Паскаль или Бейсик, которая будет определять и выводить на экран английскую букву, встречающуюся в этом тексте чаще всего, и количество там таких букв. Строчные и прописные буквы при этом считаются не различимыми. Если искомых букв несколько, то программа должна выводить на экран первую из них по алфавиту. Например, пусть файл содержит следующую запись: It is not a simple task. Yes! Чаще всего здесь встречаются буквы I, S и T (слово Yes в подсчете не учитывается, так как расположено после точки). Следовательно, в данном случае программа должна вывести два символа, разделенных пробелом:  I 3

 

С5.

Содержание правильного ответа

Программа читает текст из файла до точки один раз, подсчитывая в массиве, хранящем 26 целых чисел, количество каждой из букв. Сам текст, при этом, не запоминается. Затем в этом массиве ищется первое вхождение максимального элемента. Баллы начисляются только за программу, которая решает задачу хотя бы для частного случая (например, для строк, состоящих не более чем из 255 символов).

Указания по оцениванию

Баллы

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

4

Примеры правильных и эффективных программ:

На языке Паскаль

На языке Бейсик

var a:array['A'..'Z'] of integer;

    c, cmax: char;

begin

  assign(input,'text.dat');

  reset(input);

  for c:='A' to 'Z' do a[c]:=0;

  repeat

    read(c);

    c:= upcase(c);

    if c in ['A'..'Z'] then

      a[c]:=a[c]+1

  until c='.';

  cmax := 'A';

  for c:= 'B' to 'Z' do

    if a[c] > a[cmax] then

      cmax := c;

  writeln(cmax,' ',a[cmax])

end.

DIM i, imax, c, a(26) AS INTEGER

OPEN "TEXT.DAT" FOR INPUT AS #1

S$ = INPUT$(1, #1)

DO WHILE NOT (S$ = ".")

  c = ASC(S$)

  IF(c>=ASC("A")AND c<=ASC("Z")) THEN

   c = c - ASC("A") + 1

  ENDIF

  IF(c>=ASC("a")AND c<=ASC("z")) THEN

   с = c - ASC("a") + 1

  ENDIF

  IF(c>=1 AND c<=26) THEN a(c)=a(c)+1

  S$ = INPUT$(1, #1)

LOOP

imax = 1

FOR i = 2 TO 26

  IF a(i) > a(imax) THEN imax = i

NEXT i

PRINT CHR$(imax + 64), a(imax)

END

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

3

Программа работает в целом верно, но выводит значение не первой по алфавиту из искомых букв. Допускается наличие от одной до пяти синтаксических ошибок: пропущен или неверно указан знак пунктуации, неверно написано зарезервированное слово языка программирования, не описана или неверно описана переменная.

2

Программа обрабатывает каждую букву явным образом (26 или 52 оператора IF или оператор CASE, содержащий 26 или 52 вариантов), и, возможно, неверно работает при некоторых входных данных (например, со строчными буквами или текстами, содержащими символы, отличные от латинских букв, или содержит ошибку в алгоритме поиска максимума, в результате которой не всегда находится максимальный элемент). Допускается наличие от одной до семи синтаксических ошибок: пропущен или неверно указан знак пунктуации, неверно написано зарезервированное слово языка программирования, не описана или неверно описана переменная.

1

Задание не выполнено или выполнено неверно

0

Максимальный балл

4


 

 

Используются технологии uCoz