|
«УТВЕРЖДАЮ» Руководитель Федеральной службы по надзору в сфере и науки |
|
«СОГЛАСОВАНО» Председатель Научно-методического совета ФИПИ по информатике
|
Единый государственный экзамен по ИНФОРМАТИКЕ
Демонстрационный вариант КИМ 2006 г.
подготовлен Федеральным государственным научным учреждением
«ФЕДЕРАЛЬНЫЙ ИНСТИТУТ ПЕДАГОГИЧЕСКИХ ИЗМЕРЕНИЙ»
Директор ФИПИ |
|
А.Г. Ершов |
Единый государственный экзамен по ИНФОРМАТИКЕ
Демонстрационный вариант 2006 г.
Инструкция по выполнению работы
На выполнение экзаменационной работы по информатике отводится 4 часа (240 минут). Экзаменационная работа состоит из 3 частей, включающих 32 задания. На выполнение частей 1 и 2 работы рекомендуется отводить 1,5 часа (90 минут). На выполнение заданий части 3 – 2,5 часа (150 минут).
Часть 1 включает двадцать заданий с выбором ответа. К каждому заданию дается четыре ответа, из которых только один правильный. Ответы на задания части 1 записываются на бланке №1.
Часть 2 состоит из восьми заданий с кратким ответом (к этим заданиям вы должны самостоятельно сформулировать и записать ответ). Ответы на задания части 2 записываются на бланке №1.
Часть 3 состоит из четырех заданий. Для выполнения заданий этой части вам необходимо написать развернутый ответ в произвольной форме на бланке №2.
Выполняйте задания в том порядке, в котором они даны. Если какое-то задание вызывает у вас затруднение, пропустите его и постарайтесь выполнить те, в ответах на которые вы уверены. К пропущенным заданиям можно будет вернуться, если останется время.
За каждый правильный ответ в зависимости от сложности задания дается один или более баллов. Баллы, полученные вами за все выполненные задания, суммируются. Постарайтесь выполнить как можно больше заданий и набрать как можно больше баллов.
Желаем успеха!
В экзаменационных заданиях используются следующие соглашения:
- Обозначения для логических связок (операций):
a) отрицание (инверсия, логическое НЕ) обозначается ?
(например, ? А);
b) конъюнкция (логическое умножение, логическое И) обозначается /\
(например, А /\ В) либо & (например, А & В);
c) дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/
(например, А \/ В) либо | (например, А | В);
d) следование (импликация) обозначается -> (например, А -> В);
e) символ 1 используется для обозначения истины (истинного высказывания); символ 0 ? для обозначения лжи (ложного высказывания).
2. Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А -> В и (? А) \/ В равносильны, а А \/ В и А /\ В - нет (значения выражений разные, например, при А=1, В=0).
3. Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), эквивалентность (равносильность). Таким образом, ? А /\ В \/ С/\ D совпадает с ((? А)/\ В) \/ (С/\ D). Возможна запись А /\ В /\ С вместо (А /\ В) /\ С. То же относится и к дизъюнкции: возможна запись А \/ В \/ С вместо (А \/ В) \/ С.
Часть 1
При выполнении заданий этой части в бланке ответов № 1 под номером выполняемого вами задания (А1 – А20) поставьте знак « ? » в клеточку, номер которой соответствует номеру выбранного вами ответа.
|
A1 |
Считая, что каждый символ кодируется двумя байтами, оцените информационный объем следующего предложения в кодировке Unicode:
Один пуд – около 16,4 килограмм.
|
1) |
32 Кбайта |
2) |
512 бит |
3) |
64 бита |
4) |
32 байта |
|
A2 |
Азбука Морзе позволяет кодировать символы для радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т.д.) можно закодировать, используя код Морзе длиной не менее пяти и не более шести сигналов (точек и тире)?
|
1) |
80 |
2) |
120 |
3) |
112 |
4) |
96 |
|
A3 |
Сколько мегабайт информации содержит сообщение объемом 223 бит?
|
1) |
1 |
2) |
8 |
3) |
3 |
4) |
32 |
|
A4 |
Количество значащих нулей в двоичной записи десятичного числа 126 равно
|
1) |
1 |
2) |
2 |
3) |
3 |
4) |
0 |
|
A5 |
Вычислите сумму чисел x и y, при x = 1D16, y = 728.
Результат представьте в двоичной системе счисления.
|
1) |
100011112 |
2) |
11001012 |
3) |
1010112 |
4) |
10101112 |
|
A6 |
Определите значение переменной с после выполнения фрагмента алгоритма:
Примечание: знаком := обозначена операция присваивания.
|
1) |
1 |
2) |
45 |
3) |
55 |
4) |
66 |
|
A7 |
Определите значение целочисленных переменных a и b после выполнения фрагмента программы:
|
Бейсик |
Паскаль |
Алгоритмический |
|
a=2468 a=a\1000+b '\ и MOD — операции, вычисляющие результат деления нацело первого аргумента на второй и остаток от деления соответственно |
a:=2468; b:=(a mod 1000)*10; a:=a div 1000+b; {div и mod — операции, вычисляющие результат деления нацело первого аргумента на второй и остаток от деления соответственно} |
a:=2468 b:=mod(a, 1000)*10 a:=div(a, 1000)+b |
|
1) |
a = 22, b = 20 |
|
2) |
a = 4682, b = 4680 |
|
3) |
a = 8246, b = 246 |
|
4) |
a = 470, b = 468 |
|
A8 |
Значения двумерного массива размера 7?7 задаются с помощью вложенного оператора цикла в представленном фрагменте программы
|
Бейсик |
Паскаль |
Алгоритмический |
|
FOR n=1 TO 7 FOR k=1 TO 7 B(n, k)=k–n NEXT k NEXT n |
for n:=1 to 7 do for k:=1 to 7 do B[n, k]:=k–n; |
нц для n от 1 до 7 нц для k от 1 до 7 B[n, k]=k–n кц кц |
Сколько элементов массива будут иметь положительные значения?
|
1) |
49 |
2) |
28 |
3) |
21 |
4) |
7 |
|
A9 |
Для какого из указанных значений числа X истинно высказывание:
(X>4) \/ ((X>1) ->(X>4))?
|
1) |
1 |
2) |
2 |
3) |
3 |
4) |
4 |
|
A10 |
Какое логическое выражение равносильно выражению
¬ (¬A \/ B) \/ ¬C?
|
1) |
(A /\ ¬B) \/ ¬C |
|
2) |
¬A \/ B \/ ¬C |
|
3) |
A \/ ¬B \/ ¬C |
|
4) |
(¬A /\ B) \/ ¬C |
|
A11 |
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.
Дан фрагмент таблицы истинности выражения F:
|
X |
Y |
Z |
F |
|
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
|
1 |
0 |
0 |
1 |
Какое выражение соответствует F?
|
1) |
¬X \/ ¬Y \/ ¬Z |
|
2) |
X /\ ¬Y /\ ¬Z |
|
3) |
X \/ Y \/ Z |
|
4) |
X /\ Y /\ Z |
|
A12 |
В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите схему, соответствующую таблице.
|
|
A |
B |
C |
D |
Е |
|
A |
|
1 |
4 |
|
1 |
|
B |
1 |
|
|
3 |
|
|
C |
4 |
|
|
|
2 |
|
D |
|
3 |
|
|
|
|
Е |
1 |
|
2 |
|
|
|
1) |
2) |
3) |
4) |
|
|
|
|
|
|
A13 |
Для 5 букв русского алфавита заданы их двоичные коды (для некоторых букв ? из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
|
В |
К |
А |
Р |
Д |
|
000 |
11 |
01 |
001 |
10 |
Из четырех полученных сообщений в этой кодировке, только одно прошло без ошибки и может быть корректно декодировано. Найдите его:
|
1) |
110100000100110011 |
|
2) |
111010000010010011 |
|
3) |
110100001001100111 |
|
4) |
110110000100110010 |
|
A14 |
Для составления цепочек используются бусины, помеченные буквами: M, N, O, P, S. В середине цепочки стоит одна из бусин M, O, S. На третьем – любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На первом месте – одна из бусин O, P, S, не стоящая в цепочке в середине.
Какая из перечисленных цепочек создана по этому правилу?
|
1) |
SMP |
2) |
MSO |
3) |
SNO |
4) |
OSN |
|
A15 |
В некотором каталоге хранился файл Дневник.txt. После того, как в этом каталоге создали подкаталог и переместили в созданный подкаталог файл Дневник.txt, полное имя файла стало
A:\SCHOOL\USER\TXT\MAY\Дневник.txt. Каково полное имя каталога, в котором хранился файл до перемещения?
|
1) |
MAY |
|
2) |
A:\SCHOOL\USER\TXT |
|
3) |
TXT |
|
4) |
A:\SCHOOL\USER\TXT\MAY |
|
A16 |
Ниже в табличной форме представлен фрагмент базы данных о результатах тестирования учащихся (используется стобалльная шкала):
|
Фамилия |
Пол |
Математика |
Русский язык |
Химия |
Информатика |
Биология |
|
Аганян |
ж |
82 |
56 |
46 |
32 |
70 |
|
Воронин |
м |
43 |
62 |
45 |
74 |
23 |
|
Григорчук |
м |
54 |
74 |
68 |
75 |
83 |
|
Роднина |
ж |
71 |
63 |
56 |
82 |
79 |
|
Сергеенко |
ж |
33 |
25 |
74 |
38 |
46 |
|
Черепанова |
ж |
18 |
92 |
83 |
28 |
61 |
Сколько записей в данном фрагменте удовлетворяют условию
«Пол=’м’ ИЛИ Химия>Биология»?
|
1) |
5 |
2) |
2 |
3) |
3 |
4) |
4 |
|
A17 |
Укажите минимальный объем памяти (в килобайтах), достаточный для хранения любого растрового изображения размером 64?64 пикселя, если известно, что в изображении используется палитра из 256 цветов. Саму палитру хранить не нужно.
|
1) |
128 |
2) |
2 |
3) |
256 |
4) |
4 |
|
A18 |
При работе с электронной таблицей в ячейке A1 записана формула
= D1-$D2. Какой вид приобретет формула, после того как ячейку A1 скопируют в ячейку B1?
Примечание: символ $ в формуле обозначает абсолютную адресацию.
|
1) |
= E1-$E2 |
2) |
= E1-$D2 |
3) |
= E2-$D2 |
4) |
= D1-$E2 |
|
A19 |
Дан фрагмент электронной таблицы:
|
|
А |
В |
|
1 |
=B1+1 |
1 |
|
2 |
=A1+2 |
2 |
|
3 |
=B2–1 |
|
|
4 |
=A3 |
|
После выполнения вычислений, была построена диаграмма по значениям диапазона ячеек A1:A4. Укажите получившуюся диаграмму.
|
1) |
|
2) |
|
3) |
|
4) |
|
|
A20 |
Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды:
Вперед n, вызывающая передвижение Черепашки на n шагов в направлении движения.
Направо m, вызывающая изменение направления движения на m градусов по часовой стрелке.
(Вместо n и m должны стоять целые числа).
Запись:
Повтори 5 [Команда1 Команда2]
означает, что последовательность команд в квадратных скобках повторится 5 раз.
Какое число необходимо записать вместо n в следующем алгоритме:
Повтори 7 [Вперед 40 Направо n],
чтобы на экране появился правильный шестиугольник?
|
1) |
30 |
2) |
45 |
3) |
50 |
4) |
60 |
Часть 2
Ответом к заданиям этой части (В1 – В8) является набор символов, которые следует записать в бланк ответов № 1 справа от номера соответствующего задания, начиная с первой клеточки. Каждый символ пишите в отдельной клеточке в соответствии с приведенными образцами.
|
B1 |
В системе счисления с некоторым основанием число 17 записывается в виде 101. Укажите это основание.
|
B2 |
Укажите значения логических переменных K, L, M, N, при которых логическое выражение
(K \/ M)->(M \/ ¬L \/ N)
ложно.
Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 0101 соответствует тому, что K=0, L=1, M=0, N=1.
|
B3 |
Исполнитель Робот действует на клетчатой доске, между соседними клетками которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять команды 1 (вверх), 2 (вниз), 3 (вправо), 4 (влево), переходя на соседнюю клетку в направлении, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается. Робот успешно выполнил программу
3233241.
Какую последовательность из трех команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле?
|
B4 |
Три школьника, Миша (М), Коля (К) и Сергей (С), остававшиеся в классе на перемене, были вызваны к директору по поводу разбитого в это время окна в кабинете. На вопрос директора о том, кто это сделал, мальчики ответили следующее:
Миша: «Я не бил окно, и Коля тоже…»
Коля: «Миша не разбивал окно, это Сергей разбил футбольным мячом!»
Сергей: «Я не делал этого, стекло разбил Миша».
Стало известно, что один из ребят сказал чистую правду, второй в одной части заявления соврал, а другое его высказывание истинно, а третий оба факта исказил. Зная это, директор смог докопаться до истины.
Кто разбил стекло в классе? В ответе запишите только первую букву имени.
|
B5 |
Известно, что длительность непрерывного подключения к сети Интернет с помощью модема для некоторых АТС не превышает 10 минут. Определите максимальный размер файла (в Килобайтах), который может быть передан за время такого подключения, если модем передает информацию в среднем со скоростью 32 Килобит/с? (впишите в бланк только число)
|
B6 |
Цепочки символов (строки) создаются по следующему правилу.
Первая строка состоит из одного символа – цифры «1».
Каждая из последующих цепочек создается такими действиями: в очередную строку дважды записывается цепочка цифр из предыдущей строки (одна за другой, подряд), а в конец приписывается еще одно число – номер строки по порядку (на i-м шаге дописывается число «i»).
Вот первые 4 строки, созданные по этому правилу:
(1) 1
(2) 112
(3) 1121123
(4) 112112311211234
Какая цифра стоит в седьмой строке на 120-м месте (считая слева направо)?
|
B7 |
Доступ к файлу www.txt, находящемуся на сервере ftp.net, осуществляется по протоколу http. В таблице фрагменты адреса файла закодированы буквами от А до Ж. Запишите последовательность этих букв, кодирующую адрес указанного файла.
|
A |
.txt |
|
Б |
http |
|
В |
/ |
|
Г |
:// |
|
Д |
.net |
|
Е |
www |
|
Ж |
ftp |
|
B8 |
В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу.
Для обозначения логической операции “ИЛИ” в запросе используется символ |, а для логической операции “И” – символ &.
|
А |
разведение & содержание & меченосцы & сомики
|
|
Б |
содержание & меченосцы
|
|
В |
(содержание & меченосцы) | сомики
|
|
Г |
содержание & меченосцы & сомики
|
Не забудьте перенести все ответы в бланк ответов № 1
Часть 3
|
Для записи ответов к заданиям этой части (С1 – С5) используйте бланк ответов № 2. Запишите сначала номер задания (С1 и т.д.), а затем полное решение. Ответы записывайте четко и разборчиво. |
|
C1 |
Требовалось написать программу, в которой нужно было проверить, лежит ли число x на числовой оси между числами a и b ("между" понимается в строгом смысле, т.е. случай x=a или x=b недопустим). Числа x, a, b являются натуральными, и известно, что a отлично от b (но неизвестно: a>b или b>a). Входная информация вводится с клавиатуры, а на выходе должно быть сообщение вида "x между a и b" (если это действительно так), в противном случае никакой выходной информации не выдается.
Программист торопился и написал программу некорректно.
|
ПРОГРАММА НА ПАСКАЛЕ |
ПРОГРАММА НА БЕЙСИКЕ |
|
VAR a,b,x: integer; p: integer; BEGIN readln(a,b,x); if (a>x) AND (x>b) then writeln('x между a,b'); END. |
CLS INPUT a, b, x IF (a>x) AND (x>b) THEN PRINT “x между a, b” END |
Последовательно выполните три задания:
1) Приведите пример таких чисел a, b, x, при которых программа работает неправильно.
2) Укажите, как нужно доработать программу, чтобы не было случаев ее неправильной работы. (Это можно сделать несколькими способами, поэтому можно указать любой способ доработки исходной программы).
3) Укажите, как можно доработать программу, соблюдая дополнительное условие: доработанная программа не должна использовать логических операций AND или OR.
|
C2 |
Опишите на русском языке или на одном из языков программирования алгоритм поиска второго по величине (т.е. следующего по величине за максимальным) элемента в числовом массиве из 30 различных элементов.
|
C3 |
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 5, а во второй – 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 4 камня в какую-то кучу. Выигрывает игрок, после хода которого в одной из куч становится не менее 22 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Как должен ходить выигрывающий игрок? Ответ обоснуйте.
|
C4 |
Вступительные испытания в некоторый вуз состоят из трех экзаменов: математика (максимальный балл – 9), информатика (максимальный балл – 9), литература (максимальный балл – 5). На вход программе подаются сведения о сдаче этих экзаменов абитуриентами. В первой строке вводится количество абитуриентов N, во второй – количество мест K (K < N) на которые эти абитуриенты претендуют. Каждая из следующих N строк имеет следующий формат: , где – строка, состоящая не более, чем из 20 символов, оценки – числа от 0 до максимальной оценки по предмету соответственно. (Ноль ставится в случае, если экзамен не сдавался, например, после полученной на предыдущем экзамене двойки. Все баллы, большие 2, считаются удовлетворительными). Пример входных строк:
Иванов 8 9 3
Петров 2 0 0
Требуется написать программу на языке Паскаль или Бейсик, которая определяла бы по имеющимся данным количество абитуриентов, набравших полупроходной балл в данный вуз или сообщала, что такой балл отсутствует. (Полупроходным называется такой балл, что лишь часть абитуриентов, набравших такой балл и не получивших ни одной неудовлетворительной оценки, попадает в K лучших, которые должны быть зачислены на 1 курс) Считается, что абитуриенты, получившие только удовлетворительные оценки, обязательно присутствуют.
Инструкция по проверке и оценке работ учащихся по информатике
ЧАСТЬ 1
|
№ задания |
Ответ |
№ задания |
Ответ |
|
А1 |
2 |
А11 |
3 |
|
А2 |
4 |
А12 |
2 |
|
А3 |
1 |
А13 |
3 |
|
А4 |
1 |
А14 |
4 |
|
А5 |
4 |
А15 |
2 |
|
А6 |
3 |
А16 |
4 |
|
А7 |
2 |
А17 |
4 |
|
А8 |
3 |
А18 |
2 |
|
А9 |
1 |
А19 |
2 |
|
А10 |
1 |
А20 |
4 |
ЧАСТЬ 2
|
№ |
Ответ |
|
В1 |
4 |
|
В2 |
1010 |
|
В3 |
414 |
|
В4 |
М |
|
В5 |
2400 |
|
В6 |
1 |
|
В7 |
БГЖДВЕА |
|
В8 |
АГБВ |
ЧАСТЬ 3
|
C1 |
|
Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) |
Баллы |
|
Элементы ответа:
1) Пример: a=1 x=2 b=3
2) Возможная доработка: if a
if (a>x) AND (x>b) then writeln(' x между a,b'); (могут быть и другие правильные способы доработки). 3) Возможная доработка без использования логических операций AND, OR: p:=(x-a)*(x-b); if p<0 then writeln(' x между a,b'); (могут быть и другие способы доработки с соблюдением дополнительного условия). При оценке других вариантов доработки программы нужно проверять, что поставленная цель достигается.
|
|
|
Указания по оцениванию |
|
|
Правильно выполнены п.1)+п.3) задания (т.к. выполнение п.3 "покрывает" и пункт 2), или правильно выполнены все 3 пункта задания, при этом в работе (во фрагментах программ) допускается не более одной пунктуационной ошибки |
3 |
|
Правильно выполнены 2 пункта задания:1)+2) или 2)+3), (причем способы доработки в п.2 и п.3 различны). При этом в сданной работе допускается не более двух синтаксических ошибок (пропущен или неверно указан знак пунктуации, неверно написано зарезервированное слово языка программирования) |
2 |
|
Правильно выполнен только один пункт задания, при этом, если это был п.2) или п.3), то в нем допускается не более двух синтаксических ошибок (пропущен или неверно указан знак пунктуации, неверно написано зарезервированное слово языка программирования) |
1 |
|
Все пункты задания выполнены неверно |
0 |
|
Максимальный балл |
3 |
|
C2 |
|
Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) |
Баллы |
|
|
Введем числовые переменные Max1 и Max2, в которых будем хранить соответственно максимальный и следующий за максимальным элемент в уже просмотренной части массива. Затем в цикле до конца массива сравниваем очередной элемент массива с двумя максимальными, и если он больше одного из них или обоих, то меняем два отобранных элемента. По окончании цикла переменная Max2 содержит второй по величине элемент массива. |
|
|
|
Указания по оцениванию |
|
|
|
Предложен правильный алгоритм, выдающий верное значение (в том числе и алгоритм, требующий двукратного прохода по массиву). Возможно использование числа 30 вместо константы. Возможно наличие отдельных синтаксических ошибок (пропущенные «;», неверная запись оператора присваивания и т.п.), не искажающих замысла автора программы. В качестве примера правильного и эффективного алгоритма приведен фрагмент программы: |
2 |
|
|
На языке Паскаль |
На языке Бейсик |
|
|
const N=30; var a:array[1..N] of real; Max1, Max2, i: real; begin Max1:=a[1]; Max2:=a[1]; if a[2]>Max1 then Max1:=a[2] else Max2:=a[2]; for i:=3 to N do begin if a[i]>Max1 then begin Max2:=Max1; Max1:=a[i]; end else if a[i]>Max2 then Max2:=a[i]; end; writeln(Max2); end. |
N=30 DIM i, Max1, Max2, a(N) AS REAL Max1=a(1) Max2=a(1) IF a(2)>Max1 THEN Max1=a(2) ELSE Max2=a(2) FOR i = 3 TO N IF a(i)>Max1 THEN Max2=Max1 Max1=a(i) ELSE IF a(i)>Max2 THEN Max2=a(i) ENDIF ENDIF NEXT i PRINT Max2 END |
|
|
Имеется не более двух ошибок из числа следующих: 1) Не задано или неверно задано первое значение Max1 2) Неверно вычисляется первое значение переменной Max2 3) Не указано условие завершения цикла 4) Программа не выводит результат 5) Индексная переменная в цикле не увеличивается (при использовании циклов while или repeat-until) В программе на Паскале неверно расставлены операторные скобки |
1 |
|
|
Ошибок, перечисленных выше, больше двух или алгоритм сформулирован неверно (в частности, не хранится следующий за максимальным элемент). |
0 |
|
|
Максимальный балл |
2 |
|
|
C3 |
|
Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) |
Баллы |
||||||||||||||||||||||||||||||||||||
|
Выигрывает первый игрок. Своим первым ходом он должен удвоить количество камней во второй куче. Для доказательства рассмотрим неполное дерево игры после этого хода первого игрока.
Из таблицы видно, что при первом ходе (5,3)->(5,6) первый игрок выигрывает не позже, чем на третьем ходу при любом ответе второго игрока. |
|
||||||||||||||||||||||||||||||||||||
|
Правильное указание игрока и его ходов со строгим доказательством правильности с помощью или без помощи дерева игры |
3 |
||||||||||||||||||||||||||||||||||||
|
Правильное указание выигрывающего игрока, стратегии игры, приводящей к победе, но при отсутствии доказательства ее правильности. |
2 |
||||||||||||||||||||||||||||||||||||
|
При наличии в представленном решении одного из пунктов: 1. Правильно указаны все варианты хода первого игрока и возможные ответы второго игрока (в том числе, и все выигрышные), но неверно определены дальнейшие действия и неправильно указан победитель. 2. Правильно указан выигрывающий игрок, но отсутствует описание выигрышной стратегии и рассмотрены не все варианты хода первого игрока (а только один или несколько) и частные случаи ответов второго игрока. |
1 |
||||||||||||||||||||||||||||||||||||
|
Задание не выполнено или в представленном решении полностью отсутствует описание элементов выигрышной стратегии, и отсутствует анализ вариантов первого и второго ходов играющих. |
0 |
||||||||||||||||||||||||||||||||||||
|
Максимальный балл |
3 |
|
C4 |
|
Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) |
Баллы |
|
Программа верно читает входные данные, не запоминая их все, а сразу подсчитывая в массиве, хранящем 24 целых числа, количество абитуриентов, набравших тот или иной балл (от 0 до 23). Если при этом абитуриент получил хотя бы одну двойку, то удобно считать, что его общий балл равен 0. Затем вычисляется сумма элементов этого массива, начиная с 23-го, до тех пор пока она не превосходит K. Индекс первого элемента массива, который не войдет в эту сумму и будет искомым полупроходным баллом. Если проходной балл набрали ровно K абитуриентов, то программа сообщает, что полупроходной балл отсутствует. Баллы начисляются только за программу, которая решает задачу хотя бы для частного случая (например, проходной балл набрали строго меньше K абитуриентов). |
|
|
Указания по оцениванию |
|
|
Программа работает верно, т.е. корректно выделяет из входных данных оценки абитуриентов, верно учитывает результаты абитуриентов, получивших двойки, не содержит вложенных циклов (от 1 до N и от 0 до 23). Допускается наличие в тексте программы одной пунктуационной ошибки.
|
4 |
|
Пример правильной и эффективной программы на языке Паскаль: var m:array[0..23] of integer; c:char; i, K, N, S, m1, m2, m3:integer; begin readln(N); readln(K); for i:=0 to 23 do m[i]:=0; for i:=1 to N do begin repeat read(c) until c=’ ’; {считана фамилия абитуриента} readln(m1, m2, m3); if (m1<3)or(m2<3)or(m3<3) then s:=0 else s:=m1+m2+m3; m[s]:=m[s]+1 {учитываем абитуриента в элементе массива, соответствующем его баллам} end; s:=m[23]; i:=23; while s+m[i-1]<=K and (i>9) {9 - минимально возможный балл} do begin i:=i-1; s:=s+m[i] end; if (s9) then writeln(’полупроходной балл набрали’, m[i-1], ’ человек’) else writeln(’полупроходной балл отсутствует’); readln end.
|
|
|
Пример правильной программы на языке Бейсик: DIM i, j, k, n, m1, m2, m3, s, m(23) AS INTEGER DIM ss AS STRING FOR i = 1 TO 23 m(i) = 0 NEXT i INPUT n INPUT k FOR j = 1 TO n LINE INPUT ss i = 1 c$ = MID$(ss, i, 1) WHILE NOT (c$ = " ") i = i + 1 c$ = MID$(ss, i, 1) WEND ss = MID$(ss, i + 1, 5) m1 = ASC(MID$(ss, 1, 1)) - ASC("0") m2 = ASC(MID$(ss, 3, 1)) - ASC("0") m3 = ASC(MID$(ss, 5, 1)) - ASC("0") IF (m1 < 3) OR (m2 < 3) OR (m3 < 3) THEN s = 1 ELSE s = m1 + m2 + m3 END IF m(s) = m(s) + 1 NEXT j s = m(23): i = 23 WHILE (s + m(i - 1) 9) i = i - 1 s = s + m(i) WEND IF (s 9) THEN PRINT "Полупроходной балл набрали"; m(i - 1);” человек” ELSE PRINT "Полупроходной балл отсутствует" END IF END |
|
|
Программа работает верно, но содержит вложенные циклы (oт 0 до 23 и от 1 до N) или несколько операторов IF (по количеству возможных баллов у абитуриента) или оператор CASE, обрабатывающий различные варианты количества баллов абитуриента. Возможно, сохраняет все входные данные в массиве абитуриентов. Допускается наличие от одной до трех различных синтаксических ошибок: пропущен или неверно указан знак пунктуации, неверно написано зарезервированное слово языка программирования, не описана или неверно описана переменная, применяется операция, недопустимая для соответствующего типа данных. |
3 |
|
Программа не учитывает случай, когда ровно K абитуриентов набрали проходной балл или что количество абитуриентов, получивших удовлетворительные оценки, может оказаться меньше K. Возможно, в реализации алгоритма содержатся 1–2 ошибки (используется знак “<” вместо “<=”, “or” вместо “and”, выражение на 1 отличается от верного и т.п.). Допускается наличие от одной до пяти различных синтаксических ошибок. |
2 |
|
Программа неверно работает при некоторых входных данных, возможно, содержит ошибку при учете баллов абитуриентов, получивших неудовлетворительные оценки или в выделении оценок из строки входных данных или в логике определения полупроходного балла. Допускается наличие от одной до семи различных синтаксических ошибок. |
1 |
|
Задание выполнено неверно |
0 |
|
Максимальный балл |
4 |
~EndLATTest
|
«УТВЕРЖДАЮ» Руководитель Федеральной службы по надзору в сфере и науки |
|
«СОГЛАСОВАНО» Председатель Научно-методического совета ФИПИ по информатике
|
Единый государственный экзамен по ИНФОРМАТИКЕ
Демонстрационный вариант КИМ 2006 г.
подготовлен Федеральным государственным научным учреждением
«ФЕДЕРАЛЬНЫЙ ИНСТИТУТ ПЕДАГОГИЧЕСКИХ ИЗМЕРЕНИЙ»
Директор ФИПИ |
|
А.Г. Ершов |
Единый государственный экзамен по ИНФОРМАТИКЕ
Демонстрационный вариант 2006 г.
Инструкция по выполнению работы
На выполнение экзаменационной работы по информатике отводится 4 часа (240 минут). Экзаменационная работа состоит из 3 частей, включающих 32 задания. На выполнение частей 1 и 2 работы рекомендуется отводить 1,5 часа (90 минут). На выполнение заданий части 3 – 2,5 часа (150 минут).
Часть 1 включает двадцать заданий с выбором ответа. К каждому заданию дается четыре ответа, из которых только один правильный. Ответы на задания части 1 записываются на бланке №1.
Часть 2 состоит из восьми заданий с кратким ответом (к этим заданиям вы должны самостоятельно сформулировать и записать ответ). Ответы на задания части 2 записываются на бланке №1.
Часть 3 состоит из четырех заданий. Для выполнения заданий этой части вам необходимо написать развернутый ответ в произвольной форме на бланке №2.
Выполняйте задания в том порядке, в котором они даны. Если какое-то задание вызывает у вас затруднение, пропустите его и постарайтесь выполнить те, в ответах на которые вы уверены. К пропущенным заданиям можно будет вернуться, если останется время.
За каждый правильный ответ в зависимости от сложности задания дается один или более баллов. Баллы, полученные вами за все выполненные задания, суммируются. Постарайтесь выполнить как можно больше заданий и набрать как можно больше баллов.
Желаем успеха!
В экзаменационных заданиях используются следующие соглашения:
- Обозначения для логических связок (операций):
a) отрицание (инверсия, логическое НЕ) обозначается ?
(например, ? А);
b) конъюнкция (логическое умножение, логическое И) обозначается /\
(например, А /\ В) либо & (например, А & В);
c) дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/
(например, А \/ В) либо | (например, А | В);
d) следование (импликация) обозначается -> (например, А -> В);
e) символ 1 используется для обозначения истины (истинного высказывания); символ 0 ? для обозначения лжи (ложного высказывания).
2. Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А -> В и (? А) \/ В равносильны, а А \/ В и А /\ В - нет (значения выражений разные, например, при А=1, В=0).
3. Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), эквивалентность (равносильность). Таким образом, ? А /\ В \/ С/\ D совпадает с ((? А)/\ В) \/ (С/\ D). Возможна запись А /\ В /\ С вместо (А /\ В) /\ С. То же относится и к дизъюнкции: возможна запись А \/ В \/ С вместо (А \/ В) \/ С.
Часть 1
При выполнении заданий этой части в бланке ответов № 1 под номером выполняемого вами задания (А1 – А20) поставьте знак « ? » в клеточку, номер которой соответствует номеру выбранного вами ответа.
|
A1 |
Считая, что каждый символ кодируется двумя байтами, оцените информационный объем следующего предложения в кодировке Unicode:
Один пуд – около 16,4 килограмм.
|
1) |
32 Кбайта |
2) |
512 бит |
3) |
64 бита |
4) |
32 байта |
|
A2 |
Азбука Морзе позволяет кодировать символы для радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т.д.) можно закодировать, используя код Морзе длиной не менее пяти и не более шести сигналов (точек и тире)?
|
1) |
80 |
2) |
120 |
3) |
112 |
4) |
96 |
|
A3 |
Сколько мегабайт информации содержит сообщение объемом 223 бит?
|
1) |
1 |
2) |
8 |
3) |
3 |
4) |
32 |
|
A4 |
Количество значащих нулей в двоичной записи десятичного числа 126 равно
|
1) |
1 |
2) |
2 |
3) |
3 |
4) |
0 |
|
A5 |
Вычислите сумму чисел x и y, при x = 1D16, y = 728.
Результат представьте в двоичной системе счисления.
|
1) |
100011112 |
2) |
11001012 |
3) |
1010112 |
4) |
10101112 |
|
A6 |
Определите значение переменной с после выполнения фрагмента алгоритма:
Примечание: знаком := обозначена операция присваивания.
|
1) |
1 |
2) |
45 |
3) |
55 |
4) |
66 |
|
A7 |
Определите значение целочисленных переменных a и b после выполнения фрагмента программы:
|
Бейсик |
Паскаль |
Алгоритмический |
|
a=2468 a=a\1000+b '\ и MOD — операции, вычисляющие результат деления нацело первого аргумента на второй и остаток от деления соответственно |
a:=2468; b:=(a mod 1000)*10; a:=a div 1000+b; {div и mod — операции, вычисляющие результат деления нацело первого аргумента на второй и остаток от деления соответственно} |
a:=2468 b:=mod(a, 1000)*10 a:=div(a, 1000)+b |
|
1) |
a = 22, b = 20 |
|
2) |
a = 4682, b = 4680 |
|
3) |
a = 8246, b = 246 |
|
4) |
a = 470, b = 468 |
|
A8 |
Значения двумерного массива размера 7?7 задаются с помощью вложенного оператора цикла в представленном фрагменте программы
|
Бейсик |
Паскаль |
Алгоритмический |
|
FOR n=1 TO 7 FOR k=1 TO 7 B(n, k)=k–n NEXT k NEXT n |
for n:=1 to 7 do for k:=1 to 7 do B[n, k]:=k–n; |
нц для n от 1 до 7 нц для k от 1 до 7 B[n, k]=k–n кц кц |
Сколько элементов массива будут иметь положительные значения?
|
1) |
49 |
2) |
28 |
3) |
21 |
4) |
7 |
|
A9 |
Для какого из указанных значений числа X истинно высказывание:
(X>4) \/ ((X>1) ->(X>4))?
|
1) |
1 |
2) |
2 |
3) |
3 |
4) |
4 |
|
A10 |
Какое логическое выражение равносильно выражению
¬ (¬A \/ B) \/ ¬C?
|
1) |
(A /\ ¬B) \/ ¬C |
|
2) |
¬A \/ B \/ ¬C |
|
3) |
A \/ ¬B \/ ¬C |
|
4) |
(¬A /\ B) \/ ¬C |
|
A11 |
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.
Дан фрагмент таблицы истинности выражения F:
|
X |
Y |
Z |
F |
|
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
|
1 |
0 |
0 |
1 |
Какое выражение соответствует F?
|
1) |
¬X \/ ¬Y \/ ¬Z |
|
2) |
X /\ ¬Y /\ ¬Z |
|
3) |
X \/ Y \/ Z |
|
4) |
X /\ Y /\ Z |
|
A12 |
В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите схему, соответствующую таблице.
|
|
A |
B |
C |
D |
Е |
|
A |
|
1 |
4 |
|
1 |
|
B |
1 |
|
|
3 |
|
|
C |
4 |
|
|
|
2 |
|
D |
|
3 |
|
|
|
|
Е |
1 |
|
2 |
|
|
|
1) |
2) |
3) |
4) |
|
|
|
|
|
|
A13 |
Для 5 букв русского алфавита заданы их двоичные коды (для некоторых букв ? из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
|
В |
К |
А |
Р |
Д |
|
000 |
11 |
01 |
001 |
10 |
Из четырех полученных сообщений в этой кодировке, только одно прошло без ошибки и может быть корректно декодировано. Найдите его:
|
1) |
110100000100110011 |
|
2) |
111010000010010011 |
|
3) |
110100001001100111 |
|
4) |
110110000100110010 |
|
A14 |
Для составления цепочек используются бусины, помеченные буквами: M, N, O, P, S. В середине цепочки стоит одна из бусин M, O, S. На третьем – любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На первом месте – одна из бусин O, P, S, не стоящая в цепочке в середине.
Какая из перечисленных цепочек создана по этому правилу?
|
1) |
SMP |
2) |
MSO |
3) |
SNO |
4) |
OSN |
|
A15 |
В некотором каталоге хранился файл Дневник.txt. После того, как в этом каталоге создали подкаталог и переместили в созданный подкаталог файл Дневник.txt, полное имя файла стало
A:\SCHOOL\USER\TXT\MAY\Дневник.txt. Каково полное имя каталога, в котором хранился файл до перемещения?
|
1) |
MAY |
|
2) |
A:\SCHOOL\USER\TXT |
|
3) |
TXT |
|
4) |
A:\SCHOOL\USER\TXT\MAY |
|
A16 |
Ниже в табличной форме представлен фрагмент базы данных о результатах тестирования учащихся (используется стобалльная шкала):
|
Фамилия |
Пол |
Математика |
Русский язык |
Химия |
Информатика |
Биология |
|
Аганян |
ж |
82 |
56 |
46 |
32 |
70 |
|
Воронин |
м |
43 |
62 |
45 |
74 |
23 |
|
Григорчук |
м |
54 |
74 |
68 |
75 |
83 |
|
Роднина |
ж |
71 |
63 |
56 |
82 |
79 |
|
Сергеенко |
ж |
33 |
25 |
74 |
38 |
46 |
|
Черепанова |
ж |
18 |
92 |
83 |
28 |
61 |
Сколько записей в данном фрагменте удовлетворяют условию
«Пол=’м’ ИЛИ Химия>Биология»?
|
1) |
5 |
2) |
2 |
3) |
3 |
4) |
4 |
|
A17 |
Укажите минимальный объем памяти (в килобайтах), достаточный для хранения любого растрового изображения размером 64?64 пикселя, если известно, что в изображении используется палитра из 256 цветов. Саму палитру хранить не нужно.
|
1) |
128 |
2) |
2 |
3) |
256 |
4) |
4 |
|
A18 |
При работе с электронной таблицей в ячейке A1 записана формула
= D1-$D2. Какой вид приобретет формула, после того как ячейку A1 скопируют в ячейку B1?
Примечание: символ $ в формуле обозначает абсолютную адресацию.
|
1) |
= E1-$E2 |
2) |
= E1-$D2 |
3) |
= E2-$D2 |
4) |
= D1-$E2 |
|
A19 |
Дан фрагмент электронной таблицы:
|
|
А |
В |
|
1 |
=B1+1 |
1 |
|
2 |
=A1+2 |
2 |
|
3 |
=B2–1 |
|
|
4 |
=A3 |
|
После выполнения вычислений, была построена диаграмма по значениям диапазона ячеек A1:A4. Укажите получившуюся диаграмму.
|
1) |
|
2) |
|
3) |
|
4) |
|
|
A20 |
Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды:
Вперед n, вызывающая передвижение Черепашки на n шагов в направлении движения.
Направо m, вызывающая изменение направления движения на m градусов по часовой стрелке.
(Вместо n и m должны стоять целые числа).
Запись:
Повтори 5 [Команда1 Команда2]
означает, что последовательность команд в квадратных скобках повторится 5 раз.
Какое число необходимо записать вместо n в следующем алгоритме:
Повтори 7 [Вперед 40 Направо n],
чтобы на экране появился правильный шестиугольник?
|
1) |
30 |
2) |
45 |
3) |
50 |
4) |
60 |
Часть 2
Ответом к заданиям этой части (В1 – В8) является набор символов, которые следует записать в бланк ответов № 1 справа от номера соответствующего задания, начиная с первой клеточки. Каждый символ пишите в отдельной клеточке в соответствии с приведенными образцами.
|
B1 |
В системе счисления с некоторым основанием число 17 записывается в виде 101. Укажите это основание.
|
B2 |
Укажите значения логических переменных K, L, M, N, при которых логическое выражение
(K \/ M)->(M \/ ¬L \/ N)
ложно.
Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 0101 соответствует тому, что K=0, L=1, M=0, N=1.
|
B3 |
Исполнитель Робот действует на клетчатой доске, между соседними клетками которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять команды 1 (вверх), 2 (вниз), 3 (вправо), 4 (влево), переходя на соседнюю клетку в направлении, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается. Робот успешно выполнил программу
3233241.
Какую последовательность из трех команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле?
|
B4 |
Три школьника, Миша (М), Коля (К) и Сергей (С), остававшиеся в классе на перемене, были вызваны к директору по поводу разбитого в это время окна в кабинете. На вопрос директора о том, кто это сделал, мальчики ответили следующее:
Миша: «Я не бил окно, и Коля тоже…»
Коля: «Миша не разбивал окно, это Сергей разбил футбольным мячом!»
Сергей: «Я не делал этого, стекло разбил Миша».
Стало известно, что один из ребят сказал чистую правду, второй в одной части заявления соврал, а другое его высказывание истинно, а третий оба факта исказил. Зная это, директор смог докопаться до истины.
Кто разбил стекло в классе? В ответе запишите только первую букву имени.
|
B5 |
Известно, что длительность непрерывного подключения к сети Интернет с помощью модема для некоторых АТС не превышает 10 минут. Определите максимальный размер файла (в Килобайтах), который может быть передан за время такого подключения, если модем передает информацию в среднем со скоростью 32 Килобит/с? (впишите в бланк только число)
|
B6 |
Цепочки символов (строки) создаются по следующему правилу.
Первая строка состоит из одного символа – цифры «1».
Каждая из последующих цепочек создается такими действиями: в очередную строку дважды записывается цепочка цифр из предыдущей строки (одна за другой, подряд), а в конец приписывается еще одно число – номер строки по порядку (на i-м шаге дописывается число «i»).
Вот первые 4 строки, созданные по этому правилу:
(1) 1
(2) 112
(3) 1121123
(4) 112112311211234
Какая цифра стоит в седьмой строке на 120-м месте (считая слева направо)?
|
B7 |
Доступ к файлу www.txt, находящемуся на сервере ftp.net, осуществляется по протоколу http. В таблице фрагменты адреса файла закодированы буквами от А до Ж. Запишите последовательность этих букв, кодирующую адрес указанного файла.
|
A |
.txt |
|
Б |
http |
|
В |
/ |
|
Г |
:// |
|
Д |
.net |
|
Е |
www |
|
Ж |
ftp |
|
B8 |
В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу.
Для обозначения логической операции “ИЛИ” в запросе используется символ |, а для логической операции “И” – символ &.
|
А |
разведение & содержание & меченосцы & сомики
|
|
Б |
содержание & меченосцы
|
|
В |
(содержание & меченосцы) | сомики
|
|
Г |
содержание & меченосцы & сомики
|
Не забудьте перенести все ответы в бланк ответов № 1
Часть 3
|
Для записи ответов к заданиям этой части (С1 – С5) используйте бланк ответов № 2. Запишите сначала номер задания (С1 и т.д.), а затем полное решение. Ответы записывайте четко и разборчиво. |
|
C1 |
Требовалось написать программу, в которой нужно было проверить, лежит ли число x на числовой оси между числами a и b ("между" понимается в строгом смысле, т.е. случай x=a или x=b недопустим). Числа x, a, b являются натуральными, и известно, что a отлично от b (но неизвестно: a>b или b>a). Входная информация вводится с клавиатуры, а на выходе должно быть сообщение вида "x между a и b" (если это действительно так), в противном случае никакой выходной информации не выдается.
Программист торопился и написал программу некорректно.
|
ПРОГРАММА НА ПАСКАЛЕ |
ПРОГРАММА НА БЕЙСИКЕ |
|
VAR a,b,x: integer; p: integer; BEGIN readln(a,b,x); if (a>x) AND (x>b) then writeln('x между a,b'); END. |
CLS INPUT a, b, x IF (a>x) AND (x>b) THEN PRINT “x между a, b” END |
Последовательно выполните три задания:
1) Приведите пример таких чисел a, b, x, при которых программа работает неправильно.
2) Укажите, как нужно доработать программу, чтобы не было случаев ее неправильной работы. (Это можно сделать несколькими способами, поэтому можно указать любой способ доработки исходной программы).
3) Укажите, как можно доработать программу, соблюдая дополнительное условие: доработанная программа не должна использовать логических операций AND или OR.
|
C2 |
Опишите на русском языке или на одном из языков программирования алгоритм поиска второго по величине (т.е. следующего по величине за максимальным) элемента в числовом массиве из 30 различных элементов.
|
C3 |
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 5, а во второй – 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 4 камня в какую-то кучу. Выигрывает игрок, после хода которого в одной из куч становится не менее 22 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Как должен ходить выигрывающий игрок? Ответ обоснуйте.
|
C4 |
Вступительные испытания в некоторый вуз состоят из трех экзаменов: математика (максимальный балл – 9), информатика (максимальный балл – 9), литература (максимальный балл – 5). На вход программе подаются сведения о сдаче этих экзаменов абитуриентами. В первой строке вводится количество абитуриентов N, во второй – количество мест K (K < N) на которые эти абитуриенты претендуют. Каждая из следующих N строк имеет следующий формат: , где – строка, состоящая не более, чем из 20 символов, оценки – числа от 0 до максимальной оценки по предмету соответственно. (Ноль ставится в случае, если экзамен не сдавался, например, после полученной на предыдущем экзамене двойки. Все баллы, большие 2, считаются удовлетворительными). Пример входных строк:
Иванов 8 9 3
Петров 2 0 0
Требуется написать программу на языке Паскаль или Бейсик, которая определяла бы по имеющимся данным количество абитуриентов, набравших полупроходной балл в данный вуз или сообщала, что такой балл отсутствует. (Полупроходным называется такой балл, что лишь часть абитуриентов, набравших такой балл и не получивших ни одной неудовлетворительной оценки, попадает в K лучших, которые должны быть зачислены на 1 курс) Считается, что абитуриенты, получившие только удовлетворительные оценки, обязательно присутствуют.
Инструкция по проверке и оценке работ учащихся по информатике
ЧАСТЬ 1
|
№ задания |
Ответ |
№ задания |
Ответ |
|
А1 |
2 |
А11 |
3 |
|
А2 |
4 |
А12 |
2 |
|
А3 |
1 |
А13 |
3 |
|
А4 |
1 |
А14 |
4 |
|
А5 |
4 |
А15 |
2 |
|
А6 |
3 |
А16 |
4 |
|
А7 |
2 |
А17 |
4 |
|
А8 |
3 |
А18 |
2 |
|
А9 |
1 |
А19 |
2 |
|
А10 |
1 |
А20 |
4 |
ЧАСТЬ 2
|
№ |
Ответ |
|
В1 |
4 |
|
В2 |
1010 |
|
В3 |
414 |
|
В4 |
М |
|
В5 |
2400 |
|
В6 |
1 |
|
В7 |
БГЖДВЕА |
|
В8 |
АГБВ |
ЧАСТЬ 3
|
C1 |
|
Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) |
Баллы |
|
Элементы ответа:
1) Пример: a=1 x=2 b=3
2) Возможная доработка: if a
if (a>x) AND (x>b) then writeln(' x между a,b'); (могут быть и другие правильные способы доработки). 3) Возможная доработка без использования логических операций AND, OR: p:=(x-a)*(x-b); if p<0 then writeln(' x между a,b'); (могут быть и другие способы доработки с соблюдением дополнительного условия). При оценке других вариантов доработки программы нужно проверять, что поставленная цель достигается.
|
|
|
Указания по оцениванию |
|
|
Правильно выполнены п.1)+п.3) задания (т.к. выполнение п.3 "покрывает" и пункт 2), или правильно выполнены все 3 пункта задания, при этом в работе (во фрагментах программ) допускается не более одной пунктуационной ошибки |
3 |
|
Правильно выполнены 2 пункта задания:1)+2) или 2)+3), (причем способы доработки в п.2 и п.3 различны). При этом в сданной работе допускается не более двух синтаксических ошибок (пропущен или неверно указан знак пунктуации, неверно написано зарезервированное слово языка программирования) |
2 |
|
Правильно выполнен только один пункт задания, при этом, если это был п.2) или п.3), то в нем допускается не более двух синтаксических ошибок (пропущен или неверно указан знак пунктуации, неверно написано зарезервированное слово языка программирования) |
1 |
|
Все пункты задания выполнены неверно |
0 |
|
Максимальный балл |
3 |
|
C2 |
|
Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) |
Баллы |
|
|
Введем числовые переменные Max1 и Max2, в которых будем хранить соответственно максимальный и следующий за максимальным элемент в уже просмотренной части массива. Затем в цикле до конца массива сравниваем очередной элемент массива с двумя максимальными, и если он больше одного из них или обоих, то меняем два отобранных элемента. По окончании цикла переменная Max2 содержит второй по величине элемент массива. |
|
|
|
Указания по оцениванию |
|
|
|
Предложен правильный алгоритм, выдающий верное значение (в том числе и алгоритм, требующий двукратного прохода по массиву). Возможно использование числа 30 вместо константы. Возможно наличие отдельных синтаксических ошибок (пропущенные «;», неверная запись оператора присваивания и т.п.), не искажающих замысла автора программы. В качестве примера правильного и эффективного алгоритма приведен фрагмент программы: |
2 |
|
|
На языке Паскаль |
На языке Бейсик |
|
|
const N=30; var a:array[1..N] of real; Max1, Max2, i: real; begin Max1:=a[1]; Max2:=a[1]; if a[2]>Max1 then Max1:=a[2] else Max2:=a[2]; for i:=3 to N do begin if a[i]>Max1 then begin Max2:=Max1; Max1:=a[i]; end else if a[i]>Max2 then Max2:=a[i]; end; writeln(Max2); end. |
N=30 DIM i, Max1, Max2, a(N) AS REAL Max1=a(1) Max2=a(1) IF a(2)>Max1 THEN Max1=a(2) ELSE Max2=a(2) FOR i = 3 TO N IF a(i)>Max1 THEN Max2=Max1 Max1=a(i) ELSE IF a(i)>Max2 THEN Max2=a(i) ENDIF ENDIF NEXT i PRINT Max2 END |
|
|
Имеется не более двух ошибок из числа следующих: 1) Не задано или неверно задано первое значение Max1 2) Неверно вычисляется первое значение переменной Max2 3) Не указано условие завершения цикла 4) Программа не выводит результат 5) Индексная переменная в цикле не увеличивается (при использовании циклов while или repeat-until) В программе на Паскале неверно расставлены операторные скобки |
1 |
|
|
Ошибок, перечисленных выше, больше двух или алгоритм сформулирован неверно (в частности, не хранится следующий за максимальным элемент). |
0 |
|
|
Максимальный балл |
2 |
|
|
C3 |
|
Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) |
Баллы |
||||||||||||||||||||||||||||||||||||
|
Выигрывает первый игрок. Своим первым ходом он должен удвоить количество камней во второй куче. Для доказательства рассмотрим неполное дерево игры после этого хода первого игрока.
Из таблицы видно, что при первом ходе (5,3)->(5,6) первый игрок выигрывает не позже, чем на третьем ходу при любом ответе второго игрока. |
|
||||||||||||||||||||||||||||||||||||
|
Правильное указание игрока и его ходов со строгим доказательством правильности с помощью или без помощи дерева игры |
3 |
||||||||||||||||||||||||||||||||||||
|
Правильное указание выигрывающего игрока, стратегии игры, приводящей к победе, но при отсутствии доказательства ее правильности. |
2 |
||||||||||||||||||||||||||||||||||||
|
При наличии в представленном решении одного из пунктов: 1. Правильно указаны все варианты хода первого игрока и возможные ответы второго игрока (в том числе, и все выигрышные), но неверно определены дальнейшие действия и неправильно указан победитель. 2. Правильно указан выигрывающий игрок, но отсутствует описание выигрышной стратегии и рассмотрены не все варианты хода первого игрока (а только один или несколько) и частные случаи ответов второго игрока. |
1 |
||||||||||||||||||||||||||||||||||||
|
Задание не выполнено или в представленном решении полностью отсутствует описание элементов выигрышной стратегии, и отсутствует анализ вариантов первого и второго ходов играющих. |
0 |
||||||||||||||||||||||||||||||||||||
|
Максимальный балл |
3 |
|
C4 |
|
Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) |
Баллы |
|
Программа верно читает входные данные, не запоминая их все, а сразу подсчитывая в массиве, хранящем 24 целых числа, количество абитуриентов, набравших тот или иной балл (от 0 до 23). Если при этом абитуриент получил хотя бы одну двойку, то удобно считать, что его общий балл равен 0. Затем вычисляется сумма элементов этого массива, начиная с 23-го, до тех пор пока она не превосходит K. Индекс первого элемента массива, который не войдет в эту сумму и будет искомым полупроходным баллом. Если проходной балл набрали ровно K абитуриентов, то программа сообщает, что полупроходной балл отсутствует. Баллы начисляются только за программу, которая решает задачу хотя бы для частного случая (например, проходной балл набрали строго меньше K абитуриентов). |
|
|
Указания по оцениванию |
|
|
Программа работает верно, т.е. корректно выделяет из входных данных оценки абитуриентов, верно учитывает результаты абитуриентов, получивших двойки, не содержит вложенных циклов (от 1 до N и от 0 до 23). Допускается наличие в тексте программы одной пунктуационной ошибки.
|
4 |
|
Пример правильной и эффективной программы на языке Паскаль: var m:array[0..23] of integer; c:char; i, K, N, S, m1, m2, m3:integer; begin readln(N); readln(K); for i:=0 to 23 do m[i]:=0; for i:=1 to N do begin repeat read(c) until c=’ ’; {считана фамилия абитуриента} readln(m1, m2, m3); if (m1<3)or(m2<3)or(m3<3) then s:=0 else s:=m1+m2+m3; m[s]:=m[s]+1 {учитываем абитуриента в элементе массива, соответствующем его баллам} end; s:=m[23]; i:=23; while s+m[i-1]<=K and (i>9) {9 - минимально возможный балл} do begin i:=i-1; s:=s+m[i] end; if (s9) then writeln(’полупроходной балл набрали’, m[i-1], ’ человек’) else writeln(’полупроходной балл отсутствует’); readln end.
|
|
|
Пример правильной программы на языке Бейсик: DIM i, j, k, n, m1, m2, m3, s, m(23) AS INTEGER DIM ss AS STRING FOR i = 1 TO 23 m(i) = 0 NEXT i INPUT n INPUT k FOR j = 1 TO n LINE INPUT ss i = 1 c$ = MID$(ss, i, 1) WHILE NOT (c$ = " ") i = i + 1 c$ = MID$(ss, i, 1) WEND ss = MID$(ss, i + 1, 5) m1 = ASC(MID$(ss, 1, 1)) - ASC("0") m2 = ASC(MID$(ss, 3, 1)) - ASC("0") m3 = ASC(MID$(ss, 5, 1)) - ASC("0") IF (m1 < 3) OR (m2 < 3) OR (m3 < 3) THEN s = 1 ELSE s = m1 + m2 + m3 END IF m(s) = m(s) + 1 NEXT j s = m(23): i = 23 WHILE (s + m(i - 1) 9) i = i - 1 s = s + m(i) WEND IF (s 9) THEN PRINT "Полупроходной балл набрали"; m(i - 1);” человек” ELSE PRINT "Полупроходной балл отсутствует" END IF END |
|
|
Программа работает верно, но содержит вложенные циклы (oт 0 до 23 и от 1 до N) или несколько операторов IF (по количеству возможных баллов у абитуриента) или оператор CASE, обрабатывающий различные варианты количества баллов абитуриента. Возможно, сохраняет все входные данные в массиве абитуриентов. Допускается наличие от одной до трех различных синтаксических ошибок: пропущен или неверно указан знак пунктуации, неверно написано зарезервированное слово языка программирования, не описана или неверно описана переменная, применяется операция, недопустимая для соответствующего типа данных. |
3 |
|
Программа не учитывает случай, когда ровно K абитуриентов набрали проходной балл или что количество абитуриентов, получивших удовлетворительные оценки, может оказаться меньше K. Возможно, в реализации алгоритма содержатся 1–2 ошибки (используется знак “<” вместо “<=”, “or” вместо “and”, выражение на 1 отличается от верного и т.п.). Допускается наличие от одной до пяти различных синтаксических ошибок. |
2 |
|
Программа неверно работает при некоторых входных данных, возможно, содержит ошибку при учете баллов абитуриентов, получивших неудовлетворительные оценки или в выделении оценок из строки входных данных или в логике определения полупроходного балла. Допускается наличие от одной до семи различных синтаксических ошибок. |
1 |
|
Задание выполнено неверно |
0 |
|
Максимальный балл |
4 |
~EndLATTest
|
«УТВЕРЖДАЮ» Руководитель Федеральной службы по надзору в сфере и науки |
|
«СОГЛАСОВАНО» Председатель Научно-методического совета ФИПИ по информатике
|
Единый государственный экзамен по ИНФОРМАТИКЕ
Демонстрационный вариант КИМ 2006 г.
подготовлен Федеральным государственным научным учреждением
«ФЕДЕРАЛЬНЫЙ ИНСТИТУТ ПЕДАГОГИЧЕСКИХ ИЗМЕРЕНИЙ»
Директор ФИПИ |
|
А.Г. Ершов |
Единый государственный экзамен по ИНФОРМАТИКЕ
Демонстрационный вариант 2006 г.
Инструкция по выполнению работы
На выполнение экзаменационной работы по информатике отводится 4 часа (240 минут). Экзаменационная работа состоит из 3 частей, включающих 32 задания. На выполнение частей 1 и 2 работы рекомендуется отводить 1,5 часа (90 минут). На выполнение заданий части 3 – 2,5 часа (150 минут).
Часть 1 включает двадцать заданий с выбором ответа. К каждому заданию дается четыре ответа, из которых только один правильный. Ответы на задания части 1 записываются на бланке №1.
Часть 2 состоит из восьми заданий с кратким ответом (к этим заданиям вы должны самостоятельно сформулировать и записать ответ). Ответы на задания части 2 записываются на бланке №1.
Часть 3 состоит из четырех заданий. Для выполнения заданий этой части вам необходимо написать развернутый ответ в произвольной форме на бланке №2.
Выполняйте задания в том порядке, в котором они даны. Если какое-то задание вызывает у вас затруднение, пропустите его и постарайтесь выполнить те, в ответах на которые вы уверены. К пропущенным заданиям можно будет вернуться, если останется время.
За каждый правильный ответ в зависимости от сложности задания дается один или более баллов. Баллы, полученные вами за все выполненные задания, суммируются. Постарайтесь выполнить как можно больше заданий и набрать как можно больше баллов.
Желаем успеха!
В экзаменационных заданиях используются следующие соглашения:
- Обозначения для логических связок (операций):
a) отрицание (инверсия, логическое НЕ) обозначается ?
(например, ? А);
b) конъюнкция (логическое умножение, логическое И) обозначается /\
(например, А /\ В) либо & (например, А & В);
c) дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/
(например, А \/ В) либо | (например, А | В);
d) следование (импликация) обозначается -> (например, А -> В);
e) символ 1 используется для обозначения истины (истинного высказывания); символ 0 ? для обозначения лжи (ложного высказывания).
2. Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А -> В и (? А) \/ В равносильны, а А \/ В и А /\ В - нет (значения выражений разные, например, при А=1, В=0).
3. Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), эквивалентность (равносильность). Таким образом, ? А /\ В \/ С/\ D совпадает с ((? А)/\ В) \/ (С/\ D). Возможна запись А /\ В /\ С вместо (А /\ В) /\ С. То же относится и к дизъюнкции: возможна запись А \/ В \/ С вместо (А \/ В) \/ С.
Часть 1
При выполнении заданий этой части в бланке ответов № 1 под номером выполняемого вами задания (А1 – А20) поставьте знак « ? » в клеточку, номер которой соответствует номеру выбранного вами ответа.
|
A1 |
Считая, что каждый символ кодируется двумя байтами, оцените информационный объем следующего предложения в кодировке Unicode:
Один пуд – около 16,4 килограмм.
|
1) |
32 Кбайта |
2) |
512 бит |
3) |
64 бита |
4) |
32 байта |
|
A2 |
Азбука Морзе позволяет кодировать символы для радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т.д.) можно закодировать, используя код Морзе длиной не менее пяти и не более шести сигналов (точек и тире)?
|
1) |
80 |
2) |
120 |
3) |
112 |
4) |
96 |
|
A3 |
Сколько мегабайт информации содержит сообщение объемом 223 бит?
|
1) |
1 |
2) |
8 |
3) |
3 |
4) |
32 |
|
A4 |
Количество значащих нулей в двоичной записи десятичного числа 126 равно
|
1) |
1 |
2) |
2 |
3) |
3 |
4) |
0 |
|
A5 |
Вычислите сумму чисел x и y, при x = 1D16, y = 728.
Результат представьте в двоичной системе счисления.
|
1) |
100011112 |
2) |
11001012 |
3) |
1010112 |
4) |
10101112 |
|
A6 |
Определите значение переменной с после выполнения фрагмента алгоритма:
Примечание: знаком := обозначена операция присваивания.
|
1) |
1 |
2) |
45 |
3) |
55 |
4) |
66 |
|
A7 |
Определите значение целочисленных переменных a и b после выполнения фрагмента программы:
|
Бейсик |
Паскаль |
Алгоритмический |
|
a=2468 a=a\1000+b '\ и MOD — операции, вычисляющие результат деления нацело первого аргумента на второй и остаток от деления соответственно |
a:=2468; b:=(a mod 1000)*10; a:=a div 1000+b; {div и mod — операции, вычисляющие результат деления нацело первого аргумента на второй и остаток от деления соответственно} |
a:=2468 b:=mod(a, 1000)*10 a:=div(a, 1000)+b |
|
1) |
a = 22, b = 20 |
|
2) |
a = 4682, b = 4680 |
|
3) |
a = 8246, b = 246 |
|
4) |
a = 470, b = 468 |
|
A8 |
Значения двумерного массива размера 7?7 задаются с помощью вложенного оператора цикла в представленном фрагменте программы
|
Бейсик |
Паскаль |
Алгоритмический |
|
FOR n=1 TO 7 FOR k=1 TO 7 B(n, k)=k–n NEXT k NEXT n |
for n:=1 to 7 do for k:=1 to 7 do B[n, k]:=k–n; |
нц для n от 1 до 7 нц для k от 1 до 7 B[n, k]=k–n кц кц |
Сколько элементов массива будут иметь положительные значения?
|
1) |
49 |
2) |
28 |
3) |
21 |
4) |
7 |
|
A9 |
Для какого из указанных значений числа X истинно высказывание:
(X>4) \/ ((X>1) ->(X>4))?
|
1) |
1 |
2) |
2 |
3) |
3 |
4) |
4 |
|
A10 |
Какое логическое выражение равносильно выражению
¬ (¬A \/ B) \/ ¬C?
|
1) |
(A /\ ¬B) \/ ¬C |
|
2) |
¬A \/ B \/ ¬C |
|
3) |
A \/ ¬B \/ ¬C |
|
4) |
(¬A /\ B) \/ ¬C |
|
A11 |
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.
Дан фрагмент таблицы истинности выражения F:
|
X |
Y |
Z |
F |
|
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
|
1 |
0 |
0 |
1 |
Какое выражение соответствует F?
|
1) |
¬X \/ ¬Y \/ ¬Z |
|
2) |
X /\ ¬Y /\ ¬Z |
|
3) |
X \/ Y \/ Z |
|
4) |
X /\ Y /\ Z |
|
A12 |
В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите схему, соответствующую таблице.
|
|
A |
B |
C |
D |
Е |
|
A |
|
1 |
4 |
|
1 |
|
B |
1 |
|
|
3 |
|
|
C |
4 |
|
|
|
2 |
|
D |
|
3 |
|
|
|
|
Е |
1 |
|
2 |
|
|
|
1) |
2) |
3) |
4) |
|
|
|
|
|
|
A13 |
Для 5 букв русского алфавита заданы их двоичные коды (для некоторых букв ? из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
|
В |
К |
А |
Р |
Д |
|
000 |
11 |
01 |
001 |
10 |
Из четырех полученных сообщений в этой кодировке, только одно прошло без ошибки и может быть корректно декодировано. Найдите его:
|
1) |
110100000100110011 |
|
2) |
111010000010010011 |
|
3) |
110100001001100111 |
|
4) |
110110000100110010 |
|
A14 |
Для составления цепочек используются бусины, помеченные буквами: M, N, O, P, S. В середине цепочки стоит одна из бусин M, O, S. На третьем – любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На первом месте – одна из бусин O, P, S, не стоящая в цепочке в середине.
Какая из перечисленных цепочек создана по этому правилу?
|
1) |
SMP |
2) |
MSO |
3) |
SNO |
4) |
OSN |
|
A15 |
В некотором каталоге хранился файл Дневник.txt. После того, как в этом каталоге создали подкаталог и переместили в созданный подкаталог файл Дневник.txt, полное имя файла стало
A:\SCHOOL\USER\TXT\MAY\Дневник.txt. Каково полное имя каталога, в котором хранился файл до перемещения?
|
1) |
MAY |
|
2) |
A:\SCHOOL\USER\TXT |
|
3) |
TXT |
|
4) |
A:\SCHOOL\USER\TXT\MAY |
|
A16 |
Ниже в табличной форме представлен фрагмент базы данных о результатах тестирования учащихся (используется стобалльная шкала):
|
Фамилия |
Пол |
Математика |
Русский язык |
Химия |
Информатика |
Биология |
|
Аганян |
ж |
82 |
56 |
46 |
32 |
70 |
|
Воронин |
м |
43 |
62 |
45 |
74 |
23 |
|
Григорчук |
м |
54 |
74 |
68 |
75 |
83 |
|
Роднина |
ж |
71 |
63 |
56 |
82 |
79 |
|
Сергеенко |
ж |
33 |
25 |
74 |
38 |
46 |
|
Черепанова |
ж |
18 |
92 |
83 |
28 |
61 |
Сколько записей в данном фрагменте удовлетворяют условию
«Пол=’м’ ИЛИ Химия>Биология»?
|
1) |
5 |
2) |
2 |
3) |
3 |
4) |
4 |
|
A17 |
Укажите минимальный объем памяти (в килобайтах), достаточный для хранения любого растрового изображения размером 64?64 пикселя, если известно, что в изображении используется палитра из 256 цветов. Саму палитру хранить не нужно.
|
1) |
128 |
2) |
2 |
3) |
256 |
4) |
4 |
|
A18 |
При работе с электронной таблицей в ячейке A1 записана формула
= D1-$D2. Какой вид приобретет формула, после того как ячейку A1 скопируют в ячейку B1?
Примечание: символ $ в формуле обозначает абсолютную адресацию.
|
1) |
= E1-$E2 |
2) |
= E1-$D2 |
3) |
= E2-$D2 |
4) |
= D1-$E2 |
|
A19 |
Дан фрагмент электронной таблицы:
|
|
А |
В |
|
1 |
=B1+1 |
1 |
|
2 |
=A1+2 |
2 |
|
3 |
=B2–1 |
|
|
4 |
=A3 |
|
После выполнения вычислений, была построена диаграмма по значениям диапазона ячеек A1:A4. Укажите получившуюся диаграмму.
|
1) |
|
2) |
|
3) |
|
4) |
|
|
A20 |
Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды:
Вперед n, вызывающая передвижение Черепашки на n шагов в направлении движения.
Направо m, вызывающая изменение направления движения на m градусов по часовой стрелке.
(Вместо n и m должны стоять целые числа).
Запись:
Повтори 5 [Команда1 Команда2]
означает, что последовательность команд в квадратных скобках повторится 5 раз.
Какое число необходимо записать вместо n в следующем алгоритме:
Повтори 7 [Вперед 40 Направо n],
чтобы на экране появился правильный шестиугольник?
|
1) |
30 |
2) |
45 |
3) |
50 |
4) |
60 |
Часть 2
Ответом к заданиям этой части (В1 – В8) является набор символов, которые следует записать в бланк ответов № 1 справа от номера соответствующего задания, начиная с первой клеточки. Каждый символ пишите в отдельной клеточке в соответствии с приведенными образцами.
|
B1 |
В системе счисления с некоторым основанием число 17 записывается в виде 101. Укажите это основание.
|
B2 |
Укажите значения логических переменных K, L, M, N, при которых логическое выражение
(K \/ M)->(M \/ ¬L \/ N)
ложно.
Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 0101 соответствует тому, что K=0, L=1, M=0, N=1.
|
B3 |
Исполнитель Робот действует на клетчатой доске, между соседними клетками которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять команды 1 (вверх), 2 (вниз), 3 (вправо), 4 (влево), переходя на соседнюю клетку в направлении, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается. Робот успешно выполнил программу
3233241.
Какую последовательность из трех команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле?
|
B4 |
Три школьника, Миша (М), Коля (К) и Сергей (С), остававшиеся в классе на перемене, были вызваны к директору по поводу разбитого в это время окна в кабинете. На вопрос директора о том, кто это сделал, мальчики ответили следующее:
Миша: «Я не бил окно, и Коля тоже…»
Коля: «Миша не разбивал окно, это Сергей разбил футбольным мячом!»
Сергей: «Я не делал этого, стекло разбил Миша».
Стало известно, что один из ребят сказал чистую правду, второй в одной части заявления соврал, а другое его высказывание истинно, а третий оба факта исказил. Зная это, директор смог докопаться до истины.
Кто разбил стекло в классе? В ответе запишите только первую букву имени.
|
B5 |
Известно, что длительность непрерывного подключения к сети Интернет с помощью модема для некоторых АТС не превышает 10 минут. Определите максимальный размер файла (в Килобайтах), который может быть передан за время такого подключения, если модем передает информацию в среднем со скоростью 32 Килобит/с? (впишите в бланк только число)
|
B6 |
Цепочки символов (строки) создаются по следующему правилу.
Первая строка состоит из одного символа – цифры «1».
Каждая из последующих цепочек создается такими действиями: в очередную строку дважды записывается цепочка цифр из предыдущей строки (одна за другой, подряд), а в конец приписывается еще одно число – номер строки по порядку (на i-м шаге дописывается число «i»).
Вот первые 4 строки, созданные по этому правилу:
(1) 1
(2) 112
(3) 1121123
(4) 112112311211234
Какая цифра стоит в седьмой строке на 120-м месте (считая слева направо)?
|
B7 |
Доступ к файлу www.txt, находящемуся на сервере ftp.net, осуществляется по протоколу http. В таблице фрагменты адреса файла закодированы буквами от А до Ж. Запишите последовательность этих букв, кодирующую адрес указанного файла.
|
A |
.txt |
|
Б |
http |
|
В |
/ |
|
Г |
:// |
|
Д |
.net |
|
Е |
www |
|
Ж |
ftp |
|
B8 |
В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу.
Для обозначения логической операции “ИЛИ” в запросе используется символ |, а для логической операции “И” – символ &.
|
А |
разведение & содержание & меченосцы & сомики
|
|
Б |
содержание & меченосцы
|
|
В |
(содержание & меченосцы) | сомики
|
|
Г |
содержание & меченосцы & сомики
|
Не забудьте перенести все ответы в бланк ответов № 1
Часть 3
|
Для записи ответов к заданиям этой части (С1 – С5) используйте бланк ответов № 2. Запишите сначала номер задания (С1 и т.д.), а затем полное решение. Ответы записывайте четко и разборчиво. |
|
C1 |
Требовалось написать программу, в которой нужно было проверить, лежит ли число x на числовой оси между числами a и b ("между" понимается в строгом смысле, т.е. случай x=a или x=b недопустим). Числа x, a, b являются натуральными, и известно, что a отлично от b (но неизвестно: a>b или b>a). Входная информация вводится с клавиатуры, а на выходе должно быть сообщение вида "x между a и b" (если это действительно так), в противном случае никакой выходной информации не выдается.
Программист торопился и написал программу некорректно.
|
ПРОГРАММА НА ПАСКАЛЕ |
ПРОГРАММА НА БЕЙСИКЕ |
|
VAR a,b,x: integer; p: integer; BEGIN readln(a,b,x); if (a>x) AND (x>b) then writeln('x между a,b'); END. |
CLS INPUT a, b, x IF (a>x) AND (x>b) THEN PRINT “x между a, b” END |
Последовательно выполните три задания:
1) Приведите пример таких чисел a, b, x, при которых программа работает неправильно.
2) Укажите, как нужно доработать программу, чтобы не было случаев ее неправильной работы. (Это можно сделать несколькими способами, поэтому можно указать любой способ доработки исходной программы).
3) Укажите, как можно доработать программу, соблюдая дополнительное условие: доработанная программа не должна использовать логических операций AND или OR.
|
C2 |
Опишите на русском языке или на одном из языков программирования алгоритм поиска второго по величине (т.е. следующего по величине за максимальным) элемента в числовом массиве из 30 различных элементов.
|
C3 |
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 5, а во второй – 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 4 камня в какую-то кучу. Выигрывает игрок, после хода которого в одной из куч становится не менее 22 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Как должен ходить выигрывающий игрок? Ответ обоснуйте.
|
C4 |
Вступительные испытания в некоторый вуз состоят из трех экзаменов: математика (максимальный балл – 9), информатика (максимальный балл – 9), литература (максимальный балл – 5). На вход программе подаются сведения о сдаче этих экзаменов абитуриентами. В первой строке вводится количество абитуриентов N, во второй – количество мест K (K < N) на которые эти абитуриенты претендуют. Каждая из следующих N строк имеет следующий формат: , где – строка, состоящая не более, чем из 20 символов, оценки – числа от 0 до максимальной оценки по предмету соответственно. (Ноль ставится в случае, если экзамен не сдавался, например, после полученной на предыдущем экзамене двойки. Все баллы, большие 2, считаются удовлетворительными). Пример входных строк:
Иванов 8 9 3
Петров 2 0 0
Требуется написать программу на языке Паскаль или Бейсик, которая определяла бы по имеющимся данным количество абитуриентов, набравших полупроходной балл в данный вуз или сообщала, что такой балл отсутствует. (Полупроходным называется такой балл, что лишь часть абитуриентов, набравших такой балл и не получивших ни одной неудовлетворительной оценки, попадает в K лучших, которые должны быть зачислены на 1 курс) Считается, что абитуриенты, получившие только удовлетворительные оценки, обязательно присутствуют.
Инструкция по проверке и оценке работ учащихся по информатике
ЧАСТЬ 1
|
№ задания |
Ответ |
№ задания |
Ответ |
|
А1 |
2 |
А11 |
3 |
|
А2 |
4 |
А12 |
2 |
|
А3 |
1 |
А13 |
3 |
|
А4 |
1 |
А14 |
4 |
|
А5 |
4 |
А15 |
2 |
|
А6 |
3 |
А16 |
4 |
|
А7 |
2 |
А17 |
4 |
|
А8 |
3 |
А18 |
2 |
|
А9 |
1 |
А19 |
2 |
|
А10 |
1 |
А20 |
4 |
ЧАСТЬ 2
|
№ |
Ответ |
|
В1 |
4 |
|
В2 |
1010 |
|
В3 |
414 |
|
В4 |
М |
|
В5 |
2400 |
|
В6 |
1 |
|
В7 |
БГЖДВЕА |
|
В8 |
АГБВ |
ЧАСТЬ 3
|
C1 |
|
Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) |
Баллы |
|
Элементы ответа:
1) Пример: a=1 x=2 b=3
2) Возможная доработка: if a
if (a>x) AND (x>b) then writeln(' x между a,b'); (могут быть и другие правильные способы доработки). 3) Возможная доработка без использования логических операций AND, OR: p:=(x-a)*(x-b); if p<0 then writeln(' x между a,b'); (могут быть и другие способы доработки с соблюдением дополнительного условия). При оценке других вариантов доработки программы нужно проверять, что поставленная цель достигается.
|
|
|
Указания по оцениванию |
|
|
Правильно выполнены п.1)+п.3) задания (т.к. выполнение п.3 "покрывает" и пункт 2), или правильно выполнены все 3 пункта задания, при этом в работе (во фрагментах программ) допускается не более одной пунктуационной ошибки |
3 |
|
Правильно выполнены 2 пункта задания:1)+2) или 2)+3), (причем способы доработки в п.2 и п.3 различны). При этом в сданной работе допускается не более двух синтаксических ошибок (пропущен или неверно указан знак пунктуации, неверно написано зарезервированное слово языка программирования) |
2 |
|
Правильно выполнен только один пункт задания, при этом, если это был п.2) или п.3), то в нем допускается не более двух синтаксических ошибок (пропущен или неверно указан знак пунктуации, неверно написано зарезервированное слово языка программирования) |
1 |
|
Все пункты задания выполнены неверно |
0 |
|
Максимальный балл |
3 |
|
C2 |
|
Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) |
Баллы |
|
|
Введем числовые переменные Max1 и Max2, в которых будем хранить соответственно максимальный и следующий за максимальным элемент в уже просмотренной части массива. Затем в цикле до конца массива сравниваем очередной элемент массива с двумя максимальными, и если он больше одного из них или обоих, то меняем два отобранных элемента. По окончании цикла переменная Max2 содержит второй по величине элемент массива. |
|
|
|
Указания по оцениванию |
|
|
|
Предложен правильный алгоритм, выдающий верное значение (в том числе и алгоритм, требующий двукратного прохода по массиву). Возможно использование числа 30 вместо константы. Возможно наличие отдельных синтаксических ошибок (пропущенные «;», неверная запись оператора присваивания и т.п.), не искажающих замысла автора программы. В качестве примера правильного и эффективного алгоритма приведен фрагмент программы: |
2 |
|
|
На языке Паскаль |
На языке Бейсик |
|
|
const N=30; var a:array[1..N] of real; Max1, Max2, i: real; begin Max1:=a[1]; Max2:=a[1]; if a[2]>Max1 then Max1:=a[2] else Max2:=a[2]; for i:=3 to N do begin if a[i]>Max1 then begin Max2:=Max1; Max1:=a[i]; end else if a[i]>Max2 then Max2:=a[i]; end; writeln(Max2); end. |
N=30 DIM i, Max1, Max2, a(N) AS REAL Max1=a(1) Max2=a(1) IF a(2)>Max1 THEN Max1=a(2) ELSE Max2=a(2) FOR i = 3 TO N IF a(i)>Max1 THEN Max2=Max1 Max1=a(i) ELSE IF a(i)>Max2 THEN Max2=a(i) ENDIF ENDIF NEXT i PRINT Max2 END |
|
|
Имеется не более двух ошибок из числа следующих: 1) Не задано или неверно задано первое значение Max1 2) Неверно вычисляется первое значение переменной Max2 3) Не указано условие завершения цикла 4) Программа не выводит результат 5) Индексная переменная в цикле не увеличивается (при использовании циклов while или repeat-until) В программе на Паскале неверно расставлены операторные скобки |
1 |
|
|
Ошибок, перечисленных выше, больше двух или алгоритм сформулирован неверно (в частности, не хранится следующий за максимальным элемент). |
0 |
|
|
Максимальный балл |
2 |
|
|
C3 |
|
Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) |
Баллы |
||||||||||||||||||||||||||||||||||||
|
Выигрывает первый игрок. Своим первым ходом он должен удвоить количество камней во второй куче. Для доказательства рассмотрим неполное дерево игры после этого хода первого игрока.
Из таблицы видно, что при первом ходе (5,3)->(5,6) первый игрок выигрывает не позже, чем на третьем ходу при любом ответе второго игрока. |
|
||||||||||||||||||||||||||||||||||||
|
Правильное указание игрока и его ходов со строгим доказательством правильности с помощью или без помощи дерева игры |
3 |
||||||||||||||||||||||||||||||||||||
|
Правильное указание выигрывающего игрока, стратегии игры, приводящей к победе, но при отсутствии доказательства ее правильности. |
2 |
||||||||||||||||||||||||||||||||||||
|
При наличии в представленном решении одного из пунктов: 1. Правильно указаны все варианты хода первого игрока и возможные ответы второго игрока (в том числе, и все выигрышные), но неверно определены дальнейшие действия и неправильно указан победитель. 2. Правильно указан выигрывающий игрок, но отсутствует описание выигрышной стратегии и рассмотрены не все варианты хода первого игрока (а только один или несколько) и частные случаи ответов второго игрока. |
1 |
||||||||||||||||||||||||||||||||||||
|
Задание не выполнено или в представленном решении полностью отсутствует описание элементов выигрышной стратегии, и отсутствует анализ вариантов первого и второго ходов играющих. |
0 |
||||||||||||||||||||||||||||||||||||
|
Максимальный балл |
3 |
|
C4 |
|
Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) |
Баллы |
|
Программа верно читает входные данные, не запоминая их все, а сразу подсчитывая в массиве, хранящем 24 целых числа, количество абитуриентов, набравших тот или иной балл (от 0 до 23). Если при этом абитуриент получил хотя бы одну двойку, то удобно считать, что его общий балл равен 0. Затем вычисляется сумма элементов этого массива, начиная с 23-го, до тех пор пока она не превосходит K. Индекс первого элемента массива, который не войдет в эту сумму и будет искомым полупроходным баллом. Если проходной балл набрали ровно K абитуриентов, то программа сообщает, что полупроходной балл отсутствует. Баллы начисляются только за программу, которая решает задачу хотя бы для частного случая (например, проходной балл набрали строго меньше K абитуриентов). |
|
|
Указания по оцениванию |
|
|
Программа работает верно, т.е. корректно выделяет из входных данных оценки абитуриентов, верно учитывает результаты абитуриентов, получивших двойки, не содержит вложенных циклов (от 1 до N и от 0 до 23). Допускается наличие в тексте программы одной пунктуационной ошибки.
|
4 |
|
Пример правильной и эффективной программы на языке Паскаль: var m:array[0..23] of integer; c:char; i, K, N, S, m1, m2, m3:integer; begin readln(N); readln(K); for i:=0 to 23 do m[i]:=0; for i:=1 to N do begin repeat read(c) until c=’ ’; {считана фамилия абитуриента} readln(m1, m2, m3); if (m1<3)or(m2<3)or(m3<3) then s:=0 else s:=m1+m2+m3; m[s]:=m[s]+1 {учитываем абитуриента в элементе массива, соответствующем его баллам} end; s:=m[23]; i:=23; while s+m[i-1]<=K and (i>9) {9 - минимально возможный балл} do begin i:=i-1; s:=s+m[i] end; if (s9) then writeln(’полупроходной балл набрали’, m[i-1], ’ человек’) else writeln(’полупроходной балл отсутствует’); readln end.
|
|
|
Пример правильной программы на языке Бейсик: DIM i, j, k, n, m1, m2, m3, s, m(23) AS INTEGER DIM ss AS STRING FOR i = 1 TO 23 m(i) = 0 NEXT i INPUT n INPUT k FOR j = 1 TO n LINE INPUT ss i = 1 c$ = MID$(ss, i, 1) WHILE NOT (c$ = " ") i = i + 1 c$ = MID$(ss, i, 1) WEND ss = MID$(ss, i + 1, 5) m1 = ASC(MID$(ss, 1, 1)) - ASC("0") m2 = ASC(MID$(ss, 3, 1)) - ASC("0") m3 = ASC(MID$(ss, 5, 1)) - ASC("0") IF (m1 < 3) OR (m2 < 3) OR (m3 < 3) THEN s = 1 ELSE s = m1 + m2 + m3 END IF m(s) = m(s) + 1 NEXT j s = m(23): i = 23 WHILE (s + m(i - 1) 9) i = i - 1 s = s + m(i) WEND IF (s 9) THEN PRINT "Полупроходной балл набрали"; m(i - 1);” человек” ELSE PRINT "Полупроходной балл отсутствует" END IF END |
|
|
Программа работает верно, но содержит вложенные циклы (oт 0 до 23 и от 1 до N) или несколько операторов IF (по количеству возможных баллов у абитуриента) или оператор CASE, обрабатывающий различные варианты количества баллов абитуриента. Возможно, сохраняет все входные данные в массиве абитуриентов. Допускается наличие от одной до трех различных синтаксических ошибок: пропущен или неверно указан знак пунктуации, неверно написано зарезервированное слово языка программирования, не описана или неверно описана переменная, применяется операция, недопустимая для соответствующего типа данных. |
3 |
|
Программа не учитывает случай, когда ровно K абитуриентов набрали проходной балл или что количество абитуриентов, получивших удовлетворительные оценки, может оказаться меньше K. Возможно, в реализации алгоритма содержатся 1–2 ошибки (используется знак “<” вместо “<=”, “or” вместо “and”, выражение на 1 отличается от верного и т.п.). Допускается наличие от одной до пяти различных синтаксических ошибок. |
2 |
|
Программа неверно работает при некоторых входных данных, возможно, содержит ошибку при учете баллов абитуриентов, получивших неудовлетворительные оценки или в выделении оценок из строки входных данных или в логике определения полупроходного балла. Допускается наличие от одной до семи различных синтаксических ошибок. |
1 |
|
Задание выполнено неверно |
0 |
|
Максимальный балл |
4 |