Наверх

ОбразованиеЕГЭ в ОмскеЕГЭ по информатике и ИКТ-2013

ЕГЭ по информатике и ИКТ-2013

Скачать бланк ответов №1

Скачать бланк ответов №2


На выполнение экзаменационной работы по информатике и ИКТ отводится 4 часа (240 минут). Экзаменационная работа состоит из 3 частей, содержащих 32 задания. На выполнение частей 1 и 2 работы рекомендуется отводить 1,5 часа (90 минут). На выполнение заданий части 3 – 2,5 часа (150 минут).

  • Часть 1 содержит 13 заданий с выбором ответа. К каждому заданию даётся 4 варианта ответа, из которых только один правильный.
  • Часть 2 состоит из 15 заданий с кратким ответом (к этим заданиям Вы должны самостоятельно сформулировать и записать ответ).
  • Часть 3 состоит из 4 заданий. Для выполнения заданий этой части Вам необходимо написать развёрнутый ответ в произвольной форме.

Все бланки ЕГЭ заполняются яркими черными чернилами. Допускается использование гелевой, капиллярной или перьевой ручек.

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

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

Баллы, полученные Вами за выполненные задания, суммируются. Постарайтесь выполнить как можно больше заданий и набрать наибольшее количество баллов.

В экзаменационных заданиях используются следующие соглашения.

1. Обозначения для логических связок (операций):
a) отрицание (инверсия, логическое НЕ) обозначается ¬ (например, ¬А);
b) конъюнкция (логическое умножение, логическое И) обозначается /\ (например, А /\ В) либо & (например, А & В);
c) дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/ (например, А \/ В);
d) следование (импликация) обозначается → (например, А → В);
e) тождество обозначается ≡ (например, A ≡ B). Выражение A ≡ B истинно тогда и только тогда, когда значения A и B совпадают (либо они оба истинны, либо они оба ложны);
f) символ 1 используется для обозначения истины (истинного высказывания); символ 0 – для обозначения лжи (ложного высказывания).

2. Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А → В и (¬А) \/ В равносильны, а А \/ В и А /\ В – нет (значения выражений разные, например, при А = 1, В = 0).

3. Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), тождество. Таким образом, ¬А /\ В \/ С /\ D означает то же, что и ((¬А) /\ В) \/ (С /\ D).

Возможна запись А /\ В /\ С вместо (А /\ В) /\ С. То же относится и к дизъюнкции: возможна запись А \/ В \/ С вместо (А \/ В) \/ С.

4. Обозначения Мбайт и Кбайт используются в традиционном для информатики смысле – как обозначения единиц измерения, чьё соотношение с единицей "байт" выражается степенью двойки.

Часть 1

При выполнении заданий этой части в бланке ответов № 1 под номером выполняемого Вами задания (А1–А13) поставьте знак «×» в клеточке, номер которой соответствует номеру выбранного Вами ответа.

А1 Сколько единиц в двоичной записи десятичного числа 255?

1) 1
2) 2
3) 7
4) 8 

А2 Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 A B CDEF
A  3
   
B3 747 
C
7 
5 
D 4
 2 
E 752 3
F    3 


Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

1) 11
2) 12
3) 13
4) 18

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

 

x1x2x3x4x5x6x7F
11011110
10101100
01011001

Каким выражением может быть F?

A4 Для групповых операций с файлами используются маски имён файлов. Маска представляет собой последовательность букв, цифр и прочих допустимых в именах файлов символов, в которых также могут встречаться следующие символы. Символ «?» (вопросительный знак) означает ровно один произвольный символ. Символ «*» (звездочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность. В каталоге находится 6 файлов:

asc.wma
casting.wmv
last.wma
pasta.wmvx
pasta.wri
vast.wma

Определите, по какой из перечисленных масок из этих 6 файлов будет отобрана указанная группа файлов:

casting.wmv
last.wma
pasta.wmvx
vast.wma


1) ?as*.wm?
2) *as?.wm*
3) ?as*.wm*
4) ?as*.w*

A5 Автомат получает на вход два двузначных шестнадцатеричных числа. В этих числах все цифры не превосходят цифру 6 (если в числе есть цифра больше 6, автомат отказывается работать). По этим числам строится новое шестнадцатеричное число по следующим правилам.
1. Вычисляются два шестнадцатеричных числа – сумма старших разрядов полученных чисел и сумма младших разрядов этих чисел.
2. Полученные два шестнадцатеричных числа записываются друг за другом в порядке возрастания (без разделителей).
Пример. Исходные числа: 66, 43. Поразрядные суммы: A, 9. Результат: 9A.
Определите, какое из предложенных чисел может быть результатом работы автомата.

1) 9F
2) 911
3) 42
4) 7A

A6  Ниже представлены две таблицы из базы данных. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных фамилию и инициалы внучки Петровой С.М.

1) Басис В.В.
2) Ильченко Т.В.
3) Павлыш Н.П.
4) Петрова М.Н.

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

Чему станет равным значение ячейки D1, если в неё скопировать формулу из ячейки С2?
Примечание: знак $ обозначает абсолютную адресацию.

1) 18
2) 12
3) 14
4) 17

А8 Производится одноканальная (моно) цифровая звукозапись. Значение сигнала фиксируется 48 000 раз в секунду, для записи каждого значения используется 32 бит. Запись длится 4 минуты, её результаты записываются в файл, сжатия данных не производится. Какая из приведённых ниже величин наиболее близка к размеру полученного файла?

1) 44 Мбайт
2) 87 Мбайт
3) 125 Мбайт
4) 175 Мбайт

А9 Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 00, Б – 01, В – 100, Г – 101, Д – 110. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны.

Выберите правильный вариант ответа.
1) для буквы Д – 11
2) это невозможно
3) для буквы Г – 10
4) для буквы Д – 10

А10

На числовой прямой даны два отрезка: P = [2, 10] и Q = [6, 14]. Выберите такой отрезок A, что формула  тождественно истинна, то есть принимает значение 1 при любом значении переменной х.

1) [0, 3]
2) [3, 11]
3) [11, 15]
4) [15, 17]

А11 В некоторой стране автомобильный номер длиной 5 символов составляют из заглавных букв (задействовано 30 различных букв) и любых десятичных цифр в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит).
Определите объём памяти, отводимый этой программой для записи 50 номеров.

1) 100 байт
2) 150 байт
3) 200 байт
4) 250 байт

А12  В программе описан одномерный целочисленный массив A с индексами от 0 до 10. Ниже представлен фрагмент этой программы, записанный на разных языках программирования, в котором значения элементов массива сначала задаются, а затем меняются.

Как изменятся элементы этого массива после выполнения фрагмента программы?

1) все элементы, кроме последнего, окажутся равны между собой
2) все элементы окажутся равны своим индексам
3) все элементы, кроме последнего, будут сдвинуты на один элемент вправо
4) все элементы, кроме последнего, уменьшатся на единицу

А13 Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, включает в себя 4 команды-приказа и 4 команды проверки условия.
Команды-приказы:

вверхвнизвлевовправо


При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →.

Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится, и программа прервётся. Другие 4 команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:

сверху свободноснизу свободнослева свободносправа свободно


Цикл
ПОКА < условие > последовательность команд
КОНЕЦ ПОКА выполняется, пока условие истинно

В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Сколько клеток лабиринта соответствуют требованию, что, начав движение в
ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в
закрашенной клетке (клетка А1)?

НАЧАЛО
ПОКА слева свободно ИЛИ сверху свободно
ЕСЛИ слева свободно
ТО влево
ИНАЧЕ вверх
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

 

1) 8
2) 12
3) 17
4) 21

 

Часть 2

Ответом к заданиям этой части (В1–В15) является число, последовательность букв или цифр. Впишите ответы сначала в текст работы, а затем перенесите их в бланк ответов № 1 справа от номера соответствующего задания, начиная с первой клеточки, без пробелов, запятых и других дополнительных символов. Каждую букву или цифру пишите в отдельной клеточке в соответствии с приведёнными в бланке образцами.

B1  У исполнителя Арифметик две команды, которым присвоены номера:

1. прибавь 2,
2. умножь на 3.

Первая из них увеличивает число на экране на 2, вторая утраивает его.
Например, 21211 – это программа

умножь на 3
прибавь 2
умножь на 3
прибавь 2

прибавь 2, которая преобразует число 1 в число 19.

Запишите порядок команд в программе преобразования числа 3 в число 69, содержащей не более 5 команд, указывая лишь номера команд. Если таких программ более одной, то запишите любую из них.

Ответ: ___________________________.

B2 Определите значение переменной c после выполнения следующего фрагмента программы (записанного ниже на разных языках программирования). Ответ запишите в виде целого числа.

Ответ: ___________________________.

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

 

Какое целое число должно быть записано в ячейке C1, чтобы построенная после выполнения вычислений диаграмма по значениям диапазона ячеек A2 : С2 соответствовала рисунку? Известно, что все значения диапазона, по которым построена диаграмма, имеют один и тот же знак.

 

 

 

Ответ:___________________________________

B4  Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее четырёх и не более пяти сигналов (точек и тире)?

Ответ: ___________________________.

B5  Определите, что будет напечатано в результате выполнения программы (записанной ниже на разных языках программирования).

Ответ: ___________________________.

B6 Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями: F(1) = 1
F(n) = F(n–1) * n, при n >1
Чему равно значение функции F(5)?
В ответе запишите только натуральное число.

Ответ:____________________________________

В7 Запись десятичного числа в системах счисления с основаниями 3 и 5 в обоих случаях имеет последней цифрой 0. Какое минимальное натуральное десятичное число удовлетворяет этому требованию?

Ответ: ___________________________.


В8
  Ниже на четырёх языках записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: a и b. Укажите наименьшее из таких чисел x, при вводе которых алгоритм печатает сначала 2, а потом 21.

Ответ: ___________________________.

В9  На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?

Ответ: ___________________________.

В10 Документ объёмом 20 Мбайт можно передать с одного компьютера на другой двумя способами.

А. Сжать архиватором, передать архив по каналу связи, распаковать.
Б. Передать по каналу связи без использования архиватора.
Какой способ быстрее и насколько, если:

  •  средняя скорость передачи данных по каналу связи составляет 220 бит в секунду;
  •  объём сжатого архиватором документа равен 20% исходного;
  • время, требуемое на сжатие документа, – 5 секунд, на распаковку – 1 секунда?

В ответе напишите букву А, если быстрее способ А, или Б, если быстрее способ Б. Сразу после буквы напишите число, обозначающее, на сколько секунд один способ быстрее другого.

Так, например, если способ Б быстрее способа А на 23 секунды, в ответе нужно написать Б23.

Единиц измерения «секунд», «сек.», «с.» к ответу добавлять не нужно.

Ответ: ___________________________.

В11  В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске. По заданным IP-адресу узла и маске определите адрес сети.
IP-адрес узла: 217.19.128.131
Маска: 255.255.192.0
При записи ответа выберите из приведённых в таблице чисел четыре элемента IP-адреса сети и запишите в нужном порядке соответствующие им буквы, без использования точек.

ABCDEFGH
0161964128131192217


Пример.
Пусть искомый IP-адрес 192.168.128.0, и дана таблица

ABCDEFGH
1281682558127017192


В этом случае правильный ответ будет записан в виде: HBAF

Ответ: ___________________________.

B12  В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

ЗапросНайдено страниц (в тысячах)
Фрегат | Эсминец3400
Фрегат & Эсминец900
Фрегат2100

Какое количество страниц (в тысячах) будет найдено по запросу Эсминец? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Ответ: ___________________________.

В13 У исполнителя Удвоитель две команды, которым присвоены номера:
1. прибавь 1,
2. умножь на 2.

Первая из них увеличивает на 1 число на экране, вторая удваивает его.
Программа для Удвоителя – это последовательность команд.
Сколько есть программ, которые число 3 преобразуют в число 23?

Ответ: ___________________________.

В14 Определите, какое число будет напечатано в результате выполнения следующего алгоритма (для Вашего удобства алгоритм представлен на четырёх языках).

Ответ:___________________________________


B15
  Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, y1, y2 y3, y4, которые удовлетворяют всем перечисленным ниже условиям?

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, y1, y2y3, y4, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Ответ: ___________________________.

Не забудьте перенести все ответы в бланк ответов № 1.

Часть 3

Для записи ответов на задания этой части (С1–С4) используйте бланк ответов № 2. Запишите сначала номер задания (С1, С2 и т. д.), а затем полное решение. Ответы записывайте чётко и разборчиво.

C1 

Требовалось написать программу, при выполнении которой с клавиатуры считывается координата точки на прямой (x – действительное число) и определяется принадлежность этой точки одному из выделенных отрезков В и D (включая границы). Программист торопился и написал программу неправильно.

Последовательно выполните следующее.
1. Перерисуйте и заполните таблицу, которая показывает, как работает программа при аргументах, принадлежащих различным областям (A, B, C, D и E). Границы (точки –3, 1, 5 и 9) принадлежат заштрихованным областям (B и D соответственно).

В столбцах условий укажите «Да», если условие выполнится; «Нет», если условие не выполнится; «—» (прочерк), если условие не будет проверяться; «не изв.», если программа ведет себя по-разному для разных значений, принадлежащих данной области. В столбце «Программа выведет» укажите, что программа выведет на экран. Если программа ничего не выводит, напишите «—» (прочерк). Если для разных значений, принадлежащих области, будут выведены разные тексты, напишите «не изв.». В последнем столбце укажите «Да» или «Нет».
2. Укажите, как нужно доработать программу, чтобы не было случаев её неправильной работы. (Это можно сделать несколькими способами, достаточно указать любой способ доработки исходной программы.)

C2 Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 100. Опишите на русском языке или на одном из языков программирования алгоритм, позволяющий найти и вывести произведение элементов массива, которые имеют нечётное значение и делятся на 3. Гарантируется, что в исходном массиве есть хотя бы один элемент, значение которого нечётно и кратно 3.
Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них. Исходные данные всегда подобраны так, что результат произведения не выходит за пределы объявленных типов данных.

В качестве ответа Вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например Free Pascal 2.4) или в виде блок-схемы. В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на естественном языке).

С3 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 22. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 22 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 21.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
1. а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
2. Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём
– Петя не может выиграть за один ход, и
– Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня.
Для каждого указанного значения S опишите выигрышную стратегию Пети.

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

Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дереватуказывайте, кто делает ход, в узлах – количество камней в куче.

Система оценивания экзаменационной работы по информатике и ИКТ

Ответы к заданиям с выбором ответа

№ задания

Ответ

A1

4

A2

2

A3

1

A4

3

A5

4

A6

3

A7

1

A8

1

A9

1

A10

2

A11

3

A12

2

A13

4


Ответы к заданиям с кратким ответом

№ задания

Ответ

В1

11212

В2

10

В3

5

В4

48

В5

9

В6

120

В7

15

В8

37

В9

13

В10

А122

В11

НСЕА

В12

2200

В13

22

В14

8

В15

15


Критерии оценивания заданий с развернутым ответом


C1  Требовалось написать программу, при выполнении которой с клавиатуры считывается координата точки на прямой (x – действительное число) и определяется принадлежность этой точки одному из выделенных отрезков В и D (включая границы). Программист торопился и написал программу неправильно.

Последовательно выполните следующее.
1. Перерисуйте и заполните таблицу, которая показывает, как работает программа при аргументах, принадлежащих различным областям (A, B, C, D и E). Границы (точки –3, 1, 5 и 9) принадлежат заштрихованным областям (B и D соответственно).

В столбцах условий укажите «да», если условие выполнится, «нет», если условие не выполнится, «—» (прочерк), если условие не будет проверяться, «не изв.», если программа ведет себя по-разному для разных значений, принадлежащих данной области. В столбце «Программа выведет» укажите, что программа выведет на экран. Если программа ничего не выводит, напишите «—» (прочерк). Если для разных значений, принадлежащих области, будут выведены разные тексты, напишите «не изв.». В последнем столбце укажите «Да» или «Нет».
2. Укажите, как нужно доработать программу, чтобы не было случаев её неправильной работы. (Это можно сделать несколькими способами, достаточно указать любой способ доработки исходной программы.)

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

Баллы

Обратите внимание! В задаче требуется выполнить три действия.
1. Заполнить таблицу.
2. Исправить ошибку в условном операторе.
3. Исправить ошибку, связанную с неправильным набором условий.
Баллы за данное задание начисляются как сумма баллов за верное выполнение каждого действия. Рассмотрим отдельно каждое действие.
1. Действие по заполнению таблицы считается выполненным, если в таблице нет ошибок или ошибки присутствуют только в одной строке.
2. Неправильное использование условного оператора, в результате чего при невыполнении первого или второго условия программа не выдавала ничего (отсутствуют случаи ELSE). Исправлением этой ошибки может быть либо добавление случая ELSE к каждому условию IF, либо объединение всех условий IF в одно при помощи конъюнкции.
В сложных случаях это действие считается выполненным, если программа выдает одно из двух сообщений: «принадлежит» или «не принадлежит» – для любых чисел x, при этом программа не стала работать хуже, чем раньше, т.е. для всех точек, для которых программа ранее выдавала верный ответ, доработанная программа также должна выдавать верный ответ.
3. Приведённых трёх ограничений недостаточно для описания двух областей (потеряно условие x>=5). Кроме того, необходимо учесть, что области не соединены. Исправлением этой ошибки может быть разбиение области на две части и использование дизъюнкции, либо использование сложной (для выведения) математической конструкции (||x–3|–4|≤2), либо использование сложной комбинации каскадных условий.
В сложных случаях это действие считается выполненным, если верно определены заштрихованные области, т.е. программа выводит сообщение «принадлежит» для всех точек закрашенных областей, и только для них, для точек вне заштрихованных областей программа выводит «не принадлежит» или не выводит ничего. В работе (во фрагментах программ) допускается наличие отдельных синтаксических ошибок, не искажающих замысла автора решения

 

Выполнены все три действия

3

Правильно выполнены два действия из трёх (исправлены обе ошибки, но в пункте 1 задания не приведена таблица (либо таблица содержит ошибки в двух и более строках), либо приведена таблица (которая содержит ошибки не более чем в одной строке), но исправлена только одна ошибка программы). При написании операций сравнения допускается одно неправильное использование строгих/нестрогих неравенств (считается несущественной ошибкой, погрешностью записи). Например, вместо «x>=5» используется «x>5»

2

Правильно выполнено только одно действие из трёх, т.е. либо только приведена таблица, которая содержит ошибки в не более чем одной строке, либо таблица не приведена (или приведена и содержит ошибки более чем в одной строке), но исправлена одна ошибка программы. При оценивании этого задания на 1 балл допускается не учитывать корректность работы программ на точках границ областей (вместо нестрогих неравенств в решении были использованы строгие неравенства или наоборот)

1

Все пункты задания выполнены неверно (таблица анализа правильности алгоритма не приведена либо содержит ошибки в двух и более строках, программа не приведена либо ни одна из двух ошибок не исправлена)

0

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

3


C2
  Дан целочисленный массив из 30 элементов. Элементы массива могут

принимать целые значения от 0 до 100. Опишите на русском языке или на

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

произведение элементов массива, которые имеют нечётное значение и

делятся на 3. Гарантируется, что в исходном массиве есть хотя бы один

элемент, значение которого нечётно и кратно 3.

Исходные данные объявлены так, как показано ниже. Запрещается

использовать переменные, не описанные ниже, но разрешается не

использовать часть из них. Исходные данные всегда подобраны так, что

результат произведения не выходит за пределы объявленных типов данных.

В качестве ответа Вам необходимо привести фрагмент программы (или

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

месте многоточия. Вы можете записать решение также на другом языке

программирования (укажите название и используемую версию языка

программирования, например Free Pascal 2.4) или в виде блок-схемы. В этом случае Вы должны использовать те же самые исходные данные и

переменные, какие были предложены в условии (например, в образце,

записанном на естественном языке).

 

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

Баллы

Предложен правильный алгоритм, выдающий верное значение.

Допускается запись алгоритма на другом языке, использующая

аналогичные переменные. В случае, если язык программирования

использует типизированные переменные, описания переменных

должны быть аналогичны описаниям переменных на

естественном языке. Использование нетипизированных или

необъявленных переменных возможно только в случае, если это

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

переменных и их идентификаторы должны соответствовать

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

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

синтаксических ошибок, не искажающих замысла автора

программы

2

В любом варианте решения может присутствовать не более одной

ошибки из числа следующих.

1. Не инициализируется или неверно инициализируется

переменная P (например, присваивается начальное

значение, равное 0).

2. Неверно осуществляется проверка на нечётность.

3. На нечётность проверяется не значение элемента, а его

индекс.

4. Неверно осуществляется проверка делимости на 3.

5. На делимость на 3 проверяется не значение элемента, а его

индекс.

6. В сложном условии вместо логической операции «И»

используется логическая операция «ИЛИ».

7. Неверно осуществляется накопление произведения в

цикле (например, p := a[i]).

8. Отсутствует вывод ответа.

9. Используется переменная, не объявленная в разделе

описания переменных.

10. Не указано или неверно указано условие завершения

цикла.

11. Индексная переменная в цикле не меняется (например,

в цикле while) или меняется неверно.

12. Неверно расставлены операторные скобки

1

Ошибок, перечисленных в п. 1–12, две или больше, или алгоритм

сформулирован неверно

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


С3

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит

куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход

игрок может добавить в кучу один камень или увеличить количество камней

в куче в два раза. Например, имея кучу из 15 камней, за один ход можно

получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы,

есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится

не менее 22. Победителем считается игрок, сделавший последний ход, то есть

первым получивший кучу, в которой будет 22 или больше камней.

В начальный момент в куче было S камней, 1 ≤ S ≤ 21.

Будем говорить, что игрок имеет выигрышную стратегию, если он

может выиграть при любых ходах противника. Описать стратегию

игрока – значит описать, какой ход он должен сделать в любой

ситуации, которая ему может встретиться при различной игре

противника.

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

4. а) Укажите все такие значения числа S, при которых Петя может

выиграть в один ход. Обоснуйте, что найдены все нужные значения S,

и укажите выигрывающий ход для каждого указанного значения S.

б) Укажите такое значение S, при котором Петя не может выиграть за

один ход, но при любом ходе Пети Ваня может выиграть своим первым

ходом. Опишите выигрышную стратегию Вани.

5. Укажите два таких значения S, при которых у Пети есть выигрышная

стратегия, причём

– Петя не может выиграть за один ход, и

– Петя может выиграть своим вторым ходом, независимо от того, как

будет ходить Ваня.

Для каждого указанного значения S опишите выигрышную стратегию

Пети.

6. Укажите значение S, при котором:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым

или вторым ходом при любой игре Пети, и

– у Вани нет стратегии, которая позволит ему гарантированно выиграть

первым ходом Для указанного значения S опишите выигрышную стратегию Вани.

Постройте дерево всех партий, возможных при этой выигрышной

стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева

указывайте, кто делает ход, в узлах – количество камней в куче.

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

1. а) Петя может выиграть первым ходом, если S =11, …, 21. Во всех случаях нужно удвоить количество камней в куче. При меньших значениях S за один ход нельзя получить кучу, в которой больше 21 камня.
б) Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S =10 камней. Тогда после первого хода Пети в куче будет 11 камней или 20 камней. В обоих случаях Ваня удваивает количество камней и выигрывает своим первым ходом.
2. Возможные значения S: 5 и 9. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 10 камней. Эта позиция разобрана в п. 1б. В ней игрок, который будет ходить (теперь это Ваня), выиграть не может, а его противник (то есть, Петя) следующим ходом выиграет.
3. Возможное значение S: 8. После первого хода Пети в куче будет 9 или 16 камней. Если в куче станет 16 камней, Ваня удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 9 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Ваня), выигрывает своим вторым ходом.
В таблице изображено дерево возможных партий при описанной стратегии Вани. Заключительные позиции (в них выигрывает Ваня) подчеркнуты. На рисунке это же дерево изображено в графическом виде (оба способа изображения дерева допустимы).

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

Баллы

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

3

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

2

Представленное решение обладает одним из свойств
1. Указано, что нужно рассматривать значения n, меньшие, чем 29, и приведены правильные рекуррентные соотношения (см. выше), возможно, неполные.
2. Правильно выписаны и обоснованы значения R(n) для небольших n.
3. Правильно написан ответ, но нет его обоснования.

1
Не выполнено ни одно из перечисленных выше условий0
Максимальный балл3


С4 В командных олимпиадах по программированию для решения предлагается не больше 11 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систему соревнований. Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет статистически обрабатывать пришедшие запросы, чтобы определить наиболее популярные задачи. Следует учитывать, что количество запросов в списке может быть очень велико, так как многие соревнования проходят с использованием Интернет.

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

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

Пример входных данных:

6
А+B
Крестики-Нолики
Прямоугольник
Простой делитель
А+В
Простой делитель

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

Пример выходных данных для приведённого выше примера входных данных:

А+В 2
Простой делитель 2
Крестики-Нолики 1
Прямоугольник 1

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

Программа читает все входные данные один раз, не запоминая их в массиве, размер которого равен N, а составляя только список встретившихся задач и количества запросов по каждой из них. Во время чтения данных об очередной задаче просматривается список ранее сохраненных задач; если она уже есть в списке, то количество запросов по ней увеличивается на 1, иначе задача добавляется в массив упомянутых в запросах задач (при корректных данных он не может быть больше 11). После окончания ввода производится сортировка массивов задач и количества запросов, отданных за них, в порядке убывания количества запросов, затем выводится список из трёх первых задач с указанием частоты встречаемости (или весь список, если его длина меньше трёх). Вместо сортировки можно применить и алгоритм поиска трёх максимальных элементов в массиве. Затем выводятся задачи, частота встречаемости которых не ниже, чем у третьей задачи. Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая. Ниже приведены примеры решения задания на Алгоритмическом языке, а также на языках Паскаль и Бейсик. Допускаются решения, записанные на других языках программирования. При оценивании решений на других языках программирования необходимо учитывать особенности этих языков программирования. Так, на языке C++ при считывании строковой переменной будет считано не все название задачи, а только его первое слово, поэтому следует использовать функцию getline(cin,s), аналогичная проблема возникает и в языке Си.

Пример правильной и эффективной программы на языке Паскаль:

Var N, Num, i, j, t: integer;
       Count: array[1..11] of integer;
       s: string;
       Names: array[1..11] of string;
Begin
       Num:=0; {Число различных задач в списке запросов}
       ReadLn(N); {Считываем количество запросов}
       for i:=1 to N do
       begin
            ReadLn(s); {считали очередную задачу}
           {Осуществляем ее поиск в списке уже встретившихся}
            j:=1;
            while (j<=Num) and (s<>Names[j]) do j:=j+1;
            {Если она найдена}
             if j<=Num then {Увеличиваем счетчик числа запросов}
                   Count[j]:=Count[j]+1
             else begin {Иначе добавляем задачу в конец списка}
                        Names[j]:=s;
                        Count[j]:=1;
                        Num:=Num+1
                    end
              end;
{Сортируем массивы Names и Count в порядке убывания значений
массива Count}
         for i:=Num downto 2 do
         for j:=2 to i do if Count[j-1]         begin
               t:=Count[j]; Count[j]:=Count[j-1]; Count[j-1]:=t;
               s:=Names[j]; Names[j]:=Names[j-1]; Names[j-1]:=s;
          end;
          if Num >= 3 then j := 3 else j := Num;
          i := 1;
          while (i <= Num) and (Count[i] >= Count[j]) do
          begin
                 WriteLn(Names[i], ' ', Count[i]);
                  i := i + 1;
           end
end.

Пример правильной и эффективной программы на Алгоритмическом языке:

литтаб Names[1:11]  |  названия задач
целтаб Count[1:11]   |  счетчики числа запросов по каждой задаче
цел i, j, t
лит s
|                       1. Чтение списка запросов
|                 1.1. Инициализация количества запросов и счетчика задач
Num:=0           |Число различных задач в списке запросов
ввод N             |Считываем количество запросов
|                 1.2. Цикл чтения
нц для i от 1 до N
ввод s              |Считали очередную задачу
                        |Осуществляем ее поиск в списке уже встретившихся
j:=1
нц пока(j<=Num) и (s<>Names[j])
       j:=j+1
кц
                        | Обрабатываем очередную задачу
   если j<=Num | Если задача найдена в списке
       то              | Увеличиваем счетчик числа запросов
             Count[j]:=Count[j]+1
        иначе       | Добавляем задачу в конец списка
             Names[j]:=s
             Count[j]:=1
             Num:=Num+1
    все
кц
|                       2. Совместно сортируем массивы Names и Count
|                            в порядке убывания значений массива Count
нц для i от Num до 2 шаг -1
          нц для j от 2 до i
              если Count[j-1]                      t:=Count[j]; Count[j]:=Count[j-1]; Count[j-1]:=t
                      s:=Names[j]; Names[j]:=Names[j-1]; Names[j-1]:=s
                все
       кц
кц
|                      3. Вывод задач-"призеров"
|                 3.1. Определение порога для количества запросов по задаче
|                         Порог равен Count[j]
если Num >= 3
      то j := 3
      иначе j := Num
все
|                 3.2. Цикл вывода
i := 1;
нц пока (i <= Num) и (Count[i] >= Count[j])
         вывод нс, Names[i], ' ', Count[i]
         i := i+ 1
      кц
кон

Пример правильной и эффективной программы на языке Бейсик:

DIM N, Num, i, j, t AS INTEGER
DIM Count(11) AS INTEGER
DIM s AS STRING
DIM Names(11) AS STRING
REM Число различных задач в списке запросов
Num = 0
REM Считываем количество запросов
INPUT N
FOR i = 1 TO N
REM Считываем очередную задачу
        INPUT s
REM Осуществляем ее поиск в списке уже встретившихся
        j = 1
        WHILE j <= Num AND s <> Names(j)
             j = j + 1

        WEND
        IF j <= Num THEN
REM Если она найдена, увеличиваем счетчик числа запросов
            Count(j) = Count(j)+1
         ELSE
REM Иначе добавляем задачу в конец списка
             Names(j) = s: Count(j) = 1
             Num = Num + 1
         ENDIF
NEXT i
REM Сортируем массивы Names и Count
REM в порядке убывания значений массива Count
FOR i = Num TO 2 Step -1
         FOR j =2 TO i
            IF Count(j-1) < Count(j) THEN
                t = Count(j)
                Count(j) = Count(j-1)
                Count(j - 1)=t
                s = Names(j)
                Names(j) = Names(j-1)
                Names(j - 1)=s
            END IF
       NEXT j
NEXT i
REM определение порога для количества появлений
REM задач из списка вывода; порог равен Count(j)
IF Num >= 3 THEN
       j = 3
ELSE
       j = Num
END IF
i = 1
REM Вывод наиболее популярных задач
WHILE i <= Num AND Count(i) >= Count(j)
       PRINT Names(i), Count(i)
       i = i + 1
WEND

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

Баллы

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

4

Программа работает верно, но входные данные запоминаются в массиве, размер которого соответствует числу N. Этот массив, возможно, потом сортируется. Допускается наличие от одной до трех синтаксических ошибок. Возможно, в принципиально верно организованном вводе данных есть одна ошибка (например, использование read вместо readln в Паскале или неверное считывание строки в C++). Три балла также выставляется, если в эффективной программе, удовлетворяющей критериям выстав­ления 4 баллов, есть одна ошибка, в результате которой программа работает неверно на некоторых наборах нетипичных входных данных (например, все запросы относятся к одной и той же задаче).

3

Программа работает в целом верно, эффективно или нет, но в реализации алгоритма содержится до двух ошибок (неверная инициализация счётчиков - хотя в предложенных выше решениях обнулять их не требуется; возможно, программа неверно работает, если в списке упомянуто меньше 11 задач, выход за границу массива, допущена ошибка в принципиально верно организованной сортировке или алгоритме поиска минимальных элементов, используется знак "<" вместо "<=", "or" вместо "and" и т. п.). Возможно, некорректно организовано считывание входных данных. Допускается наличие от одной до пяти синтаксических ошибок, описанных выше.

2

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

1

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

0

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

4

Все тесты по ЕГЭ

 

Скачать бланк ответов №1

Скачать бланк ответов №2

Рассказать

Наши партнеры:

Добавить комментарий
Текст *:
Информация о пользователе
Ваше имя *:
Ваш e-mail:
 
Укажите цифры с картинки *:
Зарегистрируйтесь и авторизуйтесь на сайте, чтобы задавать вопросы без проверочного кода.

Поступление-2013

Ближайшие экзамены

Информация будет опубликована, как только появится официальное расписание ЕГЭ-2013

Проверка слова

Вопросы по ЕГЭ

Иван спрашивает:

Вопрос: Помогите решить задачу по математике

Иван отвечает:

Ответ: задача из олимпиады для 8 класса, неужели никто не знает решение???????????...

дима отвечает:

Ответ: ну и задачки у вас в школе!!!! а какой это класс???

Наши партнёры: