Информация (10 класс)

Донской государственный технический университет
Отборочный тур муниципального этапа Всероссийской
предметной олимпиады школьников 2013-2014 уч. года
ИНФОРМАТИКА
10 класс - 2013
ТЕСТ № 11
ИНСТРУКЦИЯ
На выполнение олимпиадной работы по информатике отводится 180
минут.
Работа состоит из 3 частей, включающих 22 задания.
Часть 1 включает задания А1-А12 с выбором одного правильного
ответа из 4-х предложенных. Часть 2 включает задания В1-В7 с кратким
ответом. Часть 3 включает задания С1-С3 с развернутым ответом.
При оформлении бланков ответов:
- на задания части «А» в бланке под номером выполненного задания
поставьте знак х в клеточке, соответствующей номеру выбранного вами
ответа;
- на задания части «В» впишите ответ справа от номера задания,
начиная с первой клеточки;
- на задания части «С» дайте развернутый ответ на специальном бланке.
Часть А
А1. Сколько единиц в двоичной записи десятичного числа 194,5?
1) 5
2) 6
3) 3
4) 4
А2. В таблице приведена стоимость перевозок между соседними
железнодорожными станциями. Укажите схему, соответствующую таблице.
A
A
B
C
D
1)
B
4
C
4
5
2)
D
5
6
3
3
6
3)
4)
В олимпиадных заданиях используются следующие соглашения:
1. Обозначения для логических связок (операций):
a) отрицание (инверсия) обозначается  (например,  А);
b) конъюнкция (логическое умножение, логическое И) обозначается /\
(например, А /\ В);
c) дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/
(например, А \/ В);
d) следование (импликация) обозначается -> (например, А -> В);
e) символ 1 используется для обозначения истины (истинного
высказывания); символ 0 – для обозначения лжи (ложного высказывания).
2. Два логических выражения, содержащих переменные, называются
равносильными (эквивалентными), если значения этих выражений
совпадают при любых значениях переменных.
Так, выражения А -> В и ( А) \/ В равносильны, а А \/ В и А /\ В – нет
(значения выражений разные, например, при А=1, В=0).
3. Приоритеты логических операций: отрицание, конъюнкция, дизъюнкция,
следование. Таким образом,  А /\ В \/ С/\ D совпадает с (( А)/\ В) \/ (С/\ D).
Возможна запись А /\ В /\ С вместо (А /\ В) /\ С. То же относится и к
дизъюнкции: возможна запись А \/ В \/ С вместо (А \/ В) \/ С.
А3. Символом F обозначено одно из указанных ниже логических
выражений от трех аргументов: X, Y, Z.
Дан фрагмент таблицы истинности выражения F:
X Y
0
1
1
1
1
0
Какое выражение соответствует F?
1)¬X\/Y\/¬Z
2) X/\Y/\¬Z
3) ¬X/\¬Y/\Z
4) X\/¬Y\/Z
Z
0
0
1
F
0
1
0
А4. Дано дерево каталогов.
А9. Для 5 букв латинского алфавита заданы их двоичные коды (для
некоторых букв - из двух бит, для некоторых - из трех). Эти коды
представлены в таблице:
a
000
Определите полное имя файла Doc3.
1)A:/DOC3
3)A:/ DOC3/Doc1
2) A:/DOC3/Doc3
4)A:/TOM3/Doc3
А6. Сколько записей в нижеследующем фрагменте турнирной таблицы
удовлетворяют условию «Место <=4 И (Н>2 ИЛИ О>6)»?
Место
Участник
В
Н
П
О
1
Силин
5
3
1
6½
2
Клеменс
6
0
3
6
3
Холево
5
1
4
5½
4
Яшвили
3
5
1
5½
5
Бергер
3
3
3
4½
6
Численко
3
2
4
4
2) 2
3) 3
4) 4
А7. В ячейке B1 записана формула =2*$A1. Какой вид приобретет формула,
после того как ячейку B1 скопируют в ячейку C2?
Примечание: знак $ используется для обозначения абсолютной адресации.
1) =2*$B1
2) =2*$A2
3) =3*$A2
c
01
d
001
e
10
Определите, какой набор букв закодирован двоичной строкой
1100000100110
А5. Для составления цепочек используются бусины, помеченные буквами:
M, N, O, P, S. В середине цепочки стоит одна из бусин M, O, S. На третьем
– любая гласная, если первая буква согласная, и любая согласная, если
первая гласная. На первом месте – одна из бусин O, P, S, не стоящая в
цепочке в середине.
Какая из перечисленных цепочек создана по этому правилу?
1) SMP
2) MSO
3) SNO
4) OSN
1) 5
b
110
4) =3*$B2
А8. Определить объем памяти для хранения цифрового аудиофайла, время
звучания которого составляет две минуты при частоте дискретизации 44,1
кГц и разрешении 16 бит.
1) 10 Мб
2) 10 байт
3) 705 бит
4) 2,75 Мб
1) baade
2) badde
3)
bacde
4)
bacdb
А10. Сколько различных решений имеет уравнение
(¬(В/\С)→(В/\(С→¬А))) /\(В\/(К→L))=1, где А, В, С, К, L - логические
переменные?
1) 5
2) 16
3) 32
4) 4
А11. Некоторое изделие маркируется номером длиной в 9 символов,
состоящим из прописных (используется 18различных букв) и десятичных
цифр, взятых в любом порядке.
Каждый номер в компьютерной программе записывается минимально
возможным и одинаковым количеством байт (при этом используется
посимвольное кодирование и все символы кодируются одинаковым
минимально возможным количеством бит).
Определите объём памяти, отводимый этой программой для записи 120
номеров.
1) 675 байт
2) 720 байт
3) 1080 байт 4) 2430 байт
А12. Следующий фрагмент программы записывает в переменную Max
максимальный элемент в двумерном массиве Dist размера NxN,
заполненном целыми неотрицательными числами:
Max:=0;
for i:=1 to N do
for j:=1 to N do
if Dist [i,j]>Max then Max:=Dist [i,j];
На очень медленном компьютере эта программа при N=1000 работала 5
секунд. Оцените время работы этой программы на том же компьютере
при N=2000:
1) 10 сек.
2) 20 сек.
3)
30 сек.
4)
40 сек.
Часть В
Ответом к заданиям этой части (В1 – В7) является набор цифр, букв
или число. Каждую цифру и запятую в записи десятичной дроби пишите
в отдельной клеточке. Если формат записи ответа не указан в задании,
буквы и цифры при перечислении пишите подряд, без пробелов и
запятых.
В1. У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 2
2. умножь на 3
Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а
выполняя вторую, утраивает его. Запишите порядок команд в программе
получения из 0 числа 28, содержащей не более 6 команд, указывая лишь
номера команд.
(Например, программа 21211 – это программа:
умножь на 3
прибавь 2
умножь на 3
прибавь 2
прибавь 2,
которая преобразует число 1 в 19.)
В2. Определите значение целочисленных переменных a и b после
выполнения фрагмента программы (ниже представлена одна и та же
программа, записанная на разных языках программирования):
Бейсик
Паскаль
Алгоритмический
a=42
a:=42;
a:=42
b=14
b:=14;
b:=14
a=a\b
a:=a div b;
a:= div(a, b)
b=a*b
b:=a*b;
b:= a*b
a=b\a
a:=b div a; {div —
a:= div(b, a) | div —
\ — стандартная операция, стандартная операция, стандартная функция,
вычисляющая
вычисляющая
вычисляющая результат
результат деления нацело результат деления
деления нацело первого
первого аргумента на
нацело первого
аргумента на второй|
второй
аргумента на второй}
В ответе укажите сначала значение переменной a, затем через запятую
значение переменной b.
В3. Азбука Морзе позволяет кодировать символы для радиосвязи, задавая
комбинацию точек и тире. Сколько различных символов (цифр, букв,
знаков пунктуации и т.д.) можно закодировать, используя код Морзе
длиной не менее пяти и не более шести сигналов (точек и тире)?
В4. Укажите через запятую в порядке возрастания все основания систем
счисления, в которых запись числа 22 оканчивается на 4.
В5. Известно, что длительность непрерывного подключения к сети
Интернет с помощью модема для некоторых АТС не превышает 10 минут.
Определите максимальный размер файла (в Килобайтах), который может
быть передан за время такого подключения, если модем передает
информацию в среднем со скоростью 32 Килобит/с? (впишите в бланк
только число)
В6. Цепочки символов (строки) создаются по следующему правилу.
Первая строка состоит из одного символа – цифры «1».
Каждая из последующих цепочек создается следующим действием:
в очередную строку дважды записывается предыдущая цепочка цифр (одна
за другой, подряд), а в конец приписывается еще одно число – номер строки
по порядку (на i-м шаге дописывается число «i»).
Вот первые 4 строки, созданные по этому правилу:
(1)
1
(2)
112
(3)
1121123
(4)
112112311211234
Сколько раз в общей сложности встречаются в восьмой строке четные
цифры (2, 4, 6, 8)?
В7. В таблице приведены запросы к поисковому серверу. Расположите
обозначения запросов в порядке возрастания количества страниц, которые
найдет поисковый сервер по каждому запросу.
Для обозначения логической операции “ИЛИ” в запросе используется
символ |, а для логической операции “И” - &.
A
Б
В
Г
чемпионы | (бег & плавание)
чемпионы & плавание
чемпионы | бег | плавание
чемпионы & Европа & бег & плавание
Часть С
Для записи ответа к заданию этой части (С1-С3) используйте бланк
ответов № 2. Запишите полное решение. Ответы записывайте четко и
разборчиво.
С1. Требовалось написать программу, в которой нужно было проверить,
лежит ли число x на числовой оси между числами a и b ("между"
понимается в строгом смысле, т.е. случай x=a или x=b недопустим). Числа
x, a, b являются натуральными, и известно, что a отлично от b (но
неизвестно: a>b или b>a). Входная информация вводится с клавиатуры, а на
выходе должно быть сообщение вида "x между a и b" (если это
действительно так), в противном случае никакой выходной информации не
выдается.
Программист торопился и написал программу некорректно.
С3. Два игрока играют в следующую игру. Перед ними лежат две кучки
камней, в первой из которых 4, а во второй – 3 камня. У каждого игрока
неограниченно много камней. Игроки ходят по очереди. Ход состоит в том,
что игрок или увеличивает в 3 раза число камней в какой-то куче или
добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого
общее число камней в двух кучах становится не менее 24 камней. Кто
выигрывает при безошибочной игре обоих игроков – игрок, делающий
первый ход или игрок, делающий второй ход? Каким должен быть первый
ход выигрывающего игрока? Ответ обоснуйте.
Желаем успехов в выполнении работы!
ПРОГРАММА НА ПАСКАЛЕ
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.
С2. Опишите алгоритм поиска трех последовательных элементов, сумма
которых максимальна, в числовом массиве из 30 элементов. Решение
запишите в словесной форме или на алгоритмических языках Бейсик или
Паскаль.
Информация о ЕГЭ и ГИА-9 на сайтах:
http://rcoi.dstu.edu.ru
http://www.rcoi61.org.ru