Олимпиадные задания для фестиваля «Юные интеллектуалы Среднего Урала» (разрабатываются в целях повышения знаний учащихся)

Рекомендации участникам районного тура

по информатике

2012 - 2013 учебный год.

Порядок проведения:

Время проведения - 2 часа.

При проверке все задачи оцениваются в соответствие с выставленными баллами. Максимальное количество баллов за работу 100.

Участникам олимпиады запрещено:

• Использовать для записи решений авторучки с красными или зелёными чернилами;

• Обращаться с вопросами к членам комиссии или учащимся;

• Проносить справочную литературу, учебники, электронные устройства (калькуляторы, телефоны).

Фестиваль «Юные интеллектуалы Среднего Урала»

2012-2013 учебный год

Олимпиада по информатике

Районный тур

8 класс

1. Определите значение целочисленных переменных a и b после выполнения фрагмента программы, записанной на алгоритмическом языке:

a=42

b=14

a=a\b

b=a*b

a=b\a

\ - стандартная операция, вычисляющая результат деления нацело первого аргумента на второй; * - операция умножения.

10 баллов

2. В компьютере любая информация преобразуется в цифровой код, который можно записать с помощью 0 и 1. По таблице справа восстанови рисунок в сетке слева (1- закрасить, 0 - не закрашивать). Что у тебя получилось?

1) корзина, 2) человек, 3) гриб,

4) дорога. 10 баллов

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

1) Желтые 2) Зеленые 3) Синие 10 баллов

4. О чем идет речь в следующем отрывке?

«Так были названы дешевые мясные консервы фирмы Hormel Foods (сокращение от «spied ham» - ветчина со специями). Невысокая цена этого продукта способствовала его популярности среди небогатых американцев. Позже, во время Второй мировой войны, эти консервы были одним из основных продуктов питания солдат американской армии».

1) спам; 2) хостинг; 3) сервер; 4) провайдер. 20 баллов

5. Какое слово лишнее:

1) список; 2) толковый словарь; 3) википедия; 4) энциклопедия.

10 баллов

6. В одной из древних грамот удалось расшифровать сделанную запись.

Н В Ж П С Н Д М К З А Т С Ц Т

Е Е Я И А Е У А А А Х О Е И А В соответствии с предложенным алгоритмом прочти сообщение:

Алгоритм: 1. Прочти букву из первой строки и выпиши в клетку. 2. Прочти букву из второй строки и выпиши в клетку. 3. Повтори последовательность действий 1 и 2, пока не закончатся все буквы во второй строке. На современном русском языке эта надпись означает: ―Незнающий написал, недумающий показал, а кто это читает. А что получилось у тебя? ―Невежа писа, недумая как, а хто се цита; 2) ―Невежя писал, а хто будэ чита; 3) ―Невежда писа, не думая, а кто должен читать; 4) ―Невежя писа, недуми каза, а хто се цита. 20 баллов

1. Главное отличие Смартфона от телефона заключаются в том, что:

1. По габаритам смартфон всегда больше мобильного телефона

2. Размер экрана у смартфона всегда больше чем у мобильника

3. Используя смартфон можно выйти в интернет

4. Смартфон - это мобильный телефон, работающий на операционной системе (ОС) открытого типа. 10 баллов

8. Из уроков физики вам, наверное, известно выражение «Каждый Охотник Желает Знать Где Сидит Фазан». Что общего у этого выражения и принципа получения цветной точки (пикселя) на экране монитора?

1) используются красный, зеленый и голубой;

2) используются красный, зеленый и фиолетовый;

3) используются красный, зеленый и синий. 10 баллов

Фестиваль «Юные интеллектуалы Среднего Урала»

2012-2013 учебный год

Олимпиада по информатике

Районный тур

9 класс

1. Ниже перечислено 8 различных программных средств. Какие из них являются операционными системами? (Выберите ответ, в котором перечислены только операционные системы)

A) Acrobat Reader

Б) ASP Linux

В) IBM PC DOS

Г) Macromedia Dreamweaver

Д) Microsoft Office

Е) Microsoft Windows

Ж) Norton SystemWorks

З) RealOne Player

1) АВЕЗ 2) БВЕ 3) ВДЕ 4) ЕЖ 10 баллов

2. Обычный дорожный светофор без дополнительных секций подает шесть видов сигналов (непрерывные красный, желтый и зеленый, мигающие желтый и зеленый, красный и желтый одновременно). Электронное устройство управления светофором последовательно воспроизводит записанные сигналы. Подряд записано 100 сигналов светофора. В байтах данный информационный объем составляет ?

1) 37 2) 38 3) 50 4) 100 15 баллов

3. Для хранения растрового изображения размером 128x128 пикселей отвели 4 килобайта памяти. Каково максимально возможное число цветов в палитре изображения?

1. 8 2) 2 3) 16 4) 4 15 баллов

3. Мама, прибежавшая на звон разбившейся вазы, застала всех трех своих сыновей в совершенно невинных позах: Саша, Ваня и Коля делали вид, что происшедшее к ним не относится. Однако футбольный мяч среди осколков явно говорил об обратном.

Кто это сделал? спросила мама.

Коля не бил по мячу, сказал Саша. Это сделал Ваня.

Ваня ответил: Разбил Коля, Саша не играл в футбол дома.

Так я и знала, что вы друг на дружку сваливать будете, рассердилась мама. Ну, а ты что скажешь? спросила она Колю.

Не сердись, мамочка! Я знаю, что Ваня не мог этого сделать. А я сегодня еще не сделал уроки, сказал Коля.

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

Кто разбил вазу? 15 баллов

3. Записано 7 строк, каждая имеет свой номер - от «0»- до «6»-й.

В начальный момент в строке записана цифра 0 (ноль). На каждом из последующих 6 шагов выполняется следующая операция: в очередную строку записывается удвоенная предыдущая строка, а в конец строки приписывается очередная цифра (на i-м шаге приписывается цифра i).

Для удобства в скобках пишется номер строки (начиная с 0).

Ниже показаны первые строки, сформированные по описанному правилу:

(0) 0

(1) 001

(2) 0010012

(3) 001001200100123

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

20 баллов

3. Исполнитель Робот умеет перемещаться по лабиринту, начерченному на плоскости, разбитой на клетки. Между соседними (по сторонам) клетками может стоять стена, через которую Робот пройти не может. У Робота есть восемь команд. Четыре команды - это команды-приказы: вверх вниз влево вправо При выполнении любой из этих команд Робот перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Если Робот получит команду передвижения через стену, то он разрушится. Ещё четыре команды - это команды проверки условий. Эти команды проверяют, свободен ли путь для Робота в каждом из четырёх возможных направлений: сверху свободно снизу свободно слева свободно справа свободно. Эти команды можно использовать вместе с условием «eсли», имеющим следующий вид: если условие то последовательность команд все. Здесь условие - одна из команд проверки условия. Последовательность команд - это одна или несколько любых команд- приказов. Например, для передвижения на одну клетку вправо, если справа нет стенки, можно использовать такой алгоритм: если справа свободно то вправо все. В одном условии можно использовать несколько команд проверки условий, применяя логические связки и, или, не, например: если (справа свободно) и (не снизу свободно) то вправо все. Для повторения последовательности команд можно использовать цикл «пока», имеющий следующий вид: нц пока условие последовательность команд. Например, для движения вправо, пока это возможно, можно использовать следующий алгоритм: нц пока справа свободно вправо кц. Также у Робота есть команда закрасить, при которой закрашивается клетка, в которой Робот находится в настоящий момент. Выполните задание. На бесконечном поле имеется лестница. Сначала лестница спускается вниз справа налево, затем спускается вниз слева направо. Высота каждой ступени - одна клетка, ширина - две клетки. Робот находится справа от верхней ступени лестницы. Количество ступенек, ведущих влево, и количество ступенек, ведущих вправо, неизвестно. На рисунке указан один из возможных способов расположения лестницы и Робота (Робот обозначен буквой «Р»). Р

Напишите для Робота алгоритм, закрашивающий все клетки, расположенные непосредственно над ступенями лестницы, спускающейся слева направо. Требуется закрасить только клетки, удовлетворяющие данному условию. Например, для приведённого выше рисунка Робот должен закрасить следующие клетки (см. рисунок):

Конечное расположение Робота может быть произвольным. Алгоритм должен решать задачу для произвольного размера поля и любого допустимого расположения стен внутри прямоугольного поля. При исполнении алгоритма Робот не должен разрушиться, выполнение алгоритма должно завершиться. Алгоритм может быть выполнен в среде формального исполнителя или записан в текстовом редакторе. Сохраните алгоритм в текстовом файле. Название файла «Робот». 25 баллов

Фестиваль «Юные интеллектуалы Среднего Урала»

2012-2013 учебный год

Олимпиада по информатике

Районный тур

10 класс

1. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 23 оканчивается на 2. 10 баллов

2. Сколько различных решений имеет уравнение

(K/\L/\M)\/(¬L/\¬M/\N) = 1

где K, L, M, N - логические переменные?

В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов. 15 баллов

3. У исполнителя Утроитель две команды, которым присвоены номера:

1. вычти 1

2. умножь на 3

Первая из них уменьшает число на экране на 1, вторая - увеличивает его в три раза.

Запишите порядок команд в программе получения из числа 3 числа 16, содержащей не более 5 команд, указывая лишь номера команд. (Например, программа 21211 это программа: умножь на 3 вычти 1 умножь на 3 вычти 1 вычти 1, которая преобразует число 1 в 4.) 10 баллов

4. Сколько секунд потребуется модему, передающему сообщения со скоростью 28800 бит/с, чтобы передать цветное растровое изображение размером 640х480 пикселей, при условии, что цвет каждого пикселя кодируется тремя байтами? 15 баллов

5. Записано 7 строк, каждая имеет свой номер - от «0»- до «6»-й.

В начальный момент в строке записана цифра 0 (ноль). На каждом из последующих 6 шагов выполняется следующая операция: в очередную строку записывается удвоенная предыдущая строка, а в конец строки приписывается очередная цифра (на i-м шаге приписывается цифра i).

Для удобства в скобках пишется номер строки (начиная с 0).

Ниже показаны первые строки, сформированные по описанному правилу:

(0) 0

(1) 001

(2) 0010012

(3) 001001200100123 15 баллов

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

6. Квадратный массив А размера NxN (где N=5) в программе сначала обнуляется, а затем производится некоторая дальнейшая обработка в соответствии с программой. Текст программы приведен ниже.

Требуется выяснить состояние массива А по окончании работы программы, а именно:

1) Какое число будет стоять в элементе массива А[1,2] ?

2) Сколько всего ненулевых чисел будет в массиве А ?

а также ответить на следующий вопрос:

3) В программе после начального обнуления массив А заполняется с помощью следующих операторов

i:=1; j:=1; A[1,1]:=1; k:=1; while (i

begin if (i+j) mod 2 = 0 then j:=j+1 else i:=i+1;

k:= -k; A[i,j]:=k;

end;

На какой более короткий фрагмент программы можно заменить приведенную часть программы, обеспечивая такое же заполнение массива А?

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

CONST N=5;

VAR i, j: integer;{i - строка j - столбец} k: integer;

A: array[1..N,1..N] of integer;

BEGIN

for i:=1 to N do

for j:=1 to N do A[i,j]:=0;

i:=1; j:=1; A[1,1]:=1; k:=1;

while (i

begin

if (i+j) mod 2 = 0

then j:=j+1 else i:=i+1;

k:= -k; A[i,j]:=k;

end;

END.

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

N=5

DIM A(N, N) AS INTEGER

FOR I=1 TO N

FOR J=1 TO N

A (I, J) = 0

NEXT J

NEXT I

I=1

J=1

A(1, 1)=1

K=1

WHILE (I

IF (I+J) MOD 2 = 0 THEN

J=J+1

ELSE

I=I+1

ENDIF

K=-K

A(I,J)=K

WEND

END 35 баллов

Фестиваль «Юные интеллектуалы Среднего Урала»

2012-2013 учебный год

Олимпиада по информатике

Районный тур

11 класс

1. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 23 оканчивается на 2. 10 баллов

2. Сколько различных решений имеет уравнение

(K/\L/\M)\/(¬L/\¬M/\N) = 1

где K, L, M, N - логические переменные?

В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов. 15 баллов

3. У исполнителя Утроитель две команды, которым присвоены номера:

1. вычти 1

2. умножь на 3

Первая из них уменьшает число на экране на 1, вторая - увеличивает его в три раза.

Запишите порядок команд в программе получения из числа 3 числа 16, содержащей не более 5 команд, указывая лишь номера команд. (Например, программа 21211 это программа: умножь на 3 вычти 1 умножь на 3 вычти 1 вычти 1, которая преобразует число 1 в 4.) 10 баллов

4. Сколько секунд потребуется модему, передающему сообщения со скоростью 28800 бит/с, чтобы передать цветное растровое изображение размером 640х480 пикселей, при условии, что цвет каждого пикселя кодируется тремя байтами? 15 баллов

5. Записано 7 строк, каждая имеет свой номер - от «0»- до «6»-й.

В начальный момент в строке записана цифра 0 (ноль). На каждом из последующих 6 шагов выполняется следующая операция: в очередную строку записывается удвоенная предыдущая строка, а в конец строки приписывается очередная цифра (на i-м шаге приписывается цифра i).

Для удобства в скобках пишется номер строки (начиная с 0).

Ниже показаны первые строки, сформированные по описанному правилу:

(0) 0

(1) 001

(2) 0010012

(3) 001001200100123 15 баллов

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

6. Квадратный массив А размера NxN (где N=5) в программе сначала обнуляется, а затем производится некоторая дальнейшая обработка в соответствии с программой. Текст программы приведен ниже.

Требуется выяснить состояние массива А по окончании работы программы, а именно:

1) Какое число будет стоять в элементе массива А[1,2] ?

2) Сколько всего ненулевых чисел будет в массиве А ?

а также ответить на следующий вопрос:

3) В программе после начального обнуления массив А заполняется с помощью следующих операторов

i:=1; j:=1; A[1,1]:=1; k:=1; while (i

begin if (i+j) mod 2 = 0 then j:=j+1 else i:=i+1;

k:= -k; A[i,j]:=k;

end;

На какой более короткий фрагмент программы можно заменить приведенную часть программы, обеспечивая такое же заполнение массива А?

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

CONST N=5;

VAR i, j: integer;{i - строка j - столбец} k: integer;

A: array[1..N,1..N] of integer;

BEGIN

for i:=1 to N do

for j:=1 to N do A[i,j]:=0;

i:=1; j:=1; A[1,1]:=1; k:=1;

while (i

begin

if (i+j) mod 2 = 0

then j:=j+1 else i:=i+1;

k:= -k; A[i,j]:=k;

end;

END.

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

N=5

DIM A(N, N) AS INTEGER

FOR I=1 TO N

FOR J=1 TO N

A (I, J) = 0

NEXT J

NEXT I

I=1

J=1

A(1, 1)=1

K=1

WHILE (I

IF (I+J) MOD 2 = 0 THEN

J=J+1

ELSE

I=I+1

ENDIF

K=-K

A(I,J)=K

WEND

END 35 баллов

Ответы.

8 класс.

1. А=14. Б= 42.

2. Ответ 3 - гриб

3. Ответ 1 - жёлтый

4. Ответ 1 - спам

5. Ответ 1 - список

6. Ответ 4 ―Невежя писа, недуми каза, а хто се цита.

7. Ответ 4 - Смартфон - это мобильный телефон, работающий на операционной системе (ОС) открытого типа.

8. Ответ 3 - используются красный, зеленый и синий.

9 класс.

1. Решение: По названиям: АГДЖЗ - программы

БВЕ - операционные системы.

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

2. Решение: Найдём информационный объём одного сигнала. 22 < 6 < 23. Значит один сигнал имеет объём 3 бита. Сигналов 100. 100*3 = 300 бит=300/8 байт=37,7байт=38байт.

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

3. Решение: Объём изображения Ii = 128*128*I (I - глубина цвета) Ii = 4*1024*8 бит = 32768 бит => I = 32768/128*128 = 2 бит

Количество цветов N = 2I = 22 = 4.

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

4. Решение: Решим средствами алгебры логики.

Введём буквенные обозначения

V - «Разбил Коля»

B - «Это сделал Ваня»

A - «Разбил Саша»

Можно высказывания записать формулами:

¬V*B=1

V*¬A=1

¬B=1

По условию задачи два мальчика оба раза сказали правду, а один оба раза сказал неправду. Поэтому среди записанных формул две истинны, а одна ложна. Мы не знаем, какая формула ложна, но можно утверждать, что если образовать из формул парные дизъюнкции, то, поскольку в дизъюнкцию входит одна истинная формула то дизъюнкция будет истинна. Запишем их.

¬V*B + ¬A*V=1 (1)

V*¬A + ¬B =1 (2)

¬V*B + ¬B = 1 (3)

Умножим уравнение (1) на (2)

(¬V*B + ¬A*V)*( V*¬A + ¬B)= ¬V*B* V*¬A + ¬A*V *V*¬A+ ¬V*B* ¬B +¬A*V*¬B= V*¬A+¬A*V*¬B= V*¬A(1+¬B)= =V*¬A

Умножим данное выражение на (3)

(¬V*B + ¬B)* V*¬A=¬V*B* V*¬A+¬B* V*¬A=¬B* V*¬A.

Из последнего выражения делаем вывод.

Записать: разбил вазу Коля.

5. Решение: В первой строке 3 элемента.

Во второй строке (3*2+1) = 7 - последняя цифра 2

(3) 7*2+1 = 15- последняя цифра 3

(4) 15*2+1=31- последняя цифра 4

(5) 31*2+1=63- последняя цифра 5

(6) 63*2+1 =127- последняя цифра 6

126 - 5 , 125 - 4, 124 - 3, 123 - 2. Записать ответ 2.

6. Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) Команды исполнителя будем записывать жирным шрифтом, а комментарии, поясняющие алгоритм и не являющиеся его частью, - курсивом. Начало комментария будем обозначать символом «|». | Двигаемся вниз под лестницей справа налево, пока не дойдем до стыка лестниц, нц пока снизу свободно вниз влево влево кц | Двигаемся вниз до конца спускающейся лестницы, закрашивая нужные клетки на пути нц пока не слева свободно закрасить вправо закрасить вправо вниз кц Возможны и другие варианты решения. Допускается использование иного синтаксиса инструкций исполнителя, более привычного для учащихся. Допускается наличие отдельных синтаксических ошибок, не искажающих замысла автора решения

Указания по оцениванию Баллы Алгоритм правильно работает при всех допустимых исходных данных 2 При всех допустимых исходных данных верно следующее:

1) выполнение алгоритма завершается и при этом Робот не разбивается;

2) закрашено не более 10 лишних клеток;

3) остались незакрашенными не более 10 клеток из числа тех, которые должны были быть закрашены

1 Задание выполнено неверно, то есть не выполнены условия, позволяющие поставить 1 или 2 балла 0 Максимальный балл 2

10. -11 класс

1. Решение: 2310=101112=2123=1134=435=356=327=278=259=2111=1(11)12=1(10)13=1915=1815=1716=1617=1518=1419=1320=1221=1122=1023=1024=…..

Оканчиваются на 2 системе счисления 3, 7,21.

Записать: 3, 7, 21.

2. Решение:

Дизъюнкция двух высказываний истинна, если истинно хотя бы одно из высказываний.

1.Высказывание K/\L/\M истинно, а высказывание ¬L/\¬M/\N ложно

2.Высказывание K/\L/\M ложно, а высказывание ¬L/\¬M/\N истинно

3.Высказывание K/\L/\M истинно, и высказывание ¬L/\¬M/\N истинно

Вариант1.

Высказывание K/\L/\M истинно, когда K =L=M=1 - один вариант по определению конъюнкции.

Высказывание ¬L/\¬M/\N = 0/\0 /\N - ложно при N = 0 и при N=1 - 2 возможности.

Вариант 3. не выполняется никогда.

Вариант 2. Высказывание K/\L/\M ложно (K=0 или L=0 или M=0). Посмотрим, когда будет высказывание ¬L/\¬M/\N истинно - (L=0,M=0,N=1). В этом случае K/\L/\M ложно при К=1 и при K=0 - 2 возможности.

Значит количество наборов равно 4.

Записать: Уравнение имеет 4 решения.

3. Решение: Например (3-1)*3*3-1-1=2*3*3-2=16. Пять команд 12211.

Записать ответ: 12211.

4. Решение: Определим объём изображения 640*480*3*8 = 7372800 бит.

Определим время передачи изображения. t = 7372800 бит : 28800 бит/с = 256 c.

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

5. Решение: В первой строке 3 элемента.

Во второй строке (3*2+1) = 7 - последняя цифра 2

(3) 7*2+1 = 15- последняя цифра 3

(4) 15*2+1=31- последняя цифра 4

(5) 31*2+1=63- последняя цифра 5

(6) 63*2+1 =127- последняя цифра 6

126 - 5 , 125 - 4, 124 - 3, 123 - 2. Записать ответ 2.

6. Элементы ответа:

1) A[1,2] = -1

2) В массиве А будет 9 ненулевых элементов

(5 значений "1" по главной диагонали и 4 значения "-1" над главной диагональю)

3) Доработку можно провести следующим образом:

for i:=1 to N do

begin A[i,i]:=1; if i

end;