ЧАСТЬ 1 При выполнении заданий этой части в бланке от­ветов № 1 Под номером…

ЧАСТЬ 1

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

3) 9 4) 10

Что передвигаться можно

 

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

*1	Х2	Хз	Х4	Х5	Х6	X7	F
1	0	1	1	0	0	1	1
0	1	0	0	1	1	0	1
1	1	1	0	0	1	1	1

Каким из приведённых ниже выражений может быть F?

1) — Xj V X2V ~,χ3 V ~,χ4 V X5 V XQ V ~,χ7

2) X1 V -χ2 V X3 V X4 V -χ5 V — X6 V X7

3) Xj V X2∖/ X3 V ~»X4 V ~,*3c5 V X6 V X7

4) X1 V χ2 V — X3 V -χ4 V χ5 V -χ6 V χ7

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

Символ «?» (вопросительный знак) означает ровно один произвольный символ;

Символ «*» (звёздочка) означает любую последова­тельность символов произвольной длины, в том числе «*» может задавать и пустую последовательность.

В каталоге находятся 5 файлов:

Boom, pas bloom. ppt loom, pas bottom. pdf bom. pps

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

Boom, pas bloom. ppt loom, pas

1) b*om.77? 3) 7oo*m. p*

2) 7o*om.*p7? 4) *om.*

A5. Автомат получает на вход два двузначных шест­надцатеричных числа. В этих числах все цифры не пре­восходят цифру 6 (если в числе есть цифра больше 6, автомат отказывается работать). По этим числам стро­ится новое шестнадцатеричное число по следующим правилам.

1. Вычисляются два шестнадцатеричных числа — сумма старших разрядов полученных чисел и сумма младших разрядов этих чисел.

2. Полученные два шестнадцатеричных числа запи­сываются друг за другом в порядке убывания (без раз­делителей).

Пример. Исходные числа: 25, 66. Поразрядные сум­мы: 8, В. Результат: В8.

Определите, какое из следующих чисел может быть результатом работы автомата.

1) D8 2) Bl 3)А2 4)78

А6. Дан фрагмент базы данных, содержащий ин­формацию о родственных отношениях. Определите на основании приведённых данных фамилию и инициалы племянницы Иренко Е. О.

Таблица1

Таблица 2

 

1) Кирта У. Т.

2) Кименко З. Т.

3) Вирк Я. М.

4) Олинг К. Л.

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

	А	В	C	D
1		5	3	4
2		=С2+$С2	1	2
3		=C1+D1	6	7

Чему станет равным значение ячейки АЗ, если в нее скопировать формулу из ячейки В2?

Примечание’, знак $ обозначает абсолютную адре­сацию.

1) 7 2) 2 3) 14 4) 13

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

1) 2 Мбайт 3) 15 Мбайт

2) 8 Мбайт 4) 120 Мбайт

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

Выберите правильный вариант ответа.

1) это невозможно 3) для буквы В — 01

2) для буквы А — 10 4) для буквы Д — 01

А10. Для какого из указанных значений числа X истинно высказывание:

((X < 4) → (X < 3)) A ((X < 3) → (X < 1)) ?

1) 1 2) 2 3) 3 4) 4

АН. Для регистрации на сайте некоторой страны пользователю требуется придумать пароль. Длина па­роля — ровно 10 символов. В качестве символов ис­пользуются десятичные цифры и 28 различных букв местного алфавита, причём все буквы используются в двух начертаниях: как строчные, так и заглавные (ре­гистр буквы имеет значение’.).

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

Определите объём памяти, который занимает хране­ние 90 паролей.

1) 990 байт 3) 1080 байт

2) 900 байт 4) 810 байт

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

Бейсик	Паскаль
FOR i = 0 TO 10 A(10-i) = i NEXT i k = А(9) FOR i = 1 ТО 9 A(10-i) = A(9-i) NEXT i A(I) = к	For i := 0 to 10 do A[10-i] := i; К := А[9]; For i := 1 to 9 do A[10-i] := A[9-i]; A[l] := к;
Си	Алгоритмический язык
For (i = 0; i <= 10; i++) A[10-i] = i; К = А[9] ; For (i = 1; i <= 9; i++) A[10-i] = A[9-i]; A[l] = к;	Ни для i от 0 до 10 A^[Tθ-i] := i KU E-: = А[9] Нц для i от 1 до 9 ApTO-i] := A[9-i] кц ATI] := к

Чему i	Будут равны элементы этого массива?
D	9	8	7	6	5	4	3	2	1	0	10
2)	10	1	9	8	7	6	5	4	3	2	0
3)	0	10	9	8	7	6	5	4	3	2	1
4)	10	0	9	8	7	6	5	4	3	2	1

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

Команды-приказы:

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

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

Другие четыре команды проверяют истинность Условия отсутст­вия стены у каждой стороны той клетки, где находится РОБОТ:

Сверху свободно

Снизу свободно

Слева свободно

Справа свободно

Цикл

ПОКА <условие> последовательность команд

КОНЕЦ ПОКА выполняется, пока условие истинно. В конструкции

ЕСЛИ <условие>

ТО Команда!

ИНАЧЕ Команда2

КОНЕЦ ЕСЛИ выполняется Команда! (если условие истинно) или Команда2 (если условие ложно).

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

НАЧАЛО

ПОКА <Cnpaβa свободно ИЛИ Сверху свободы»

ЕСЛИ <Cβepxy свободы»

ТО Вверх

ИНАЧЕ Вправо

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

1) 18 2) 23 3) 27 4) 30

Ч АСТЬ 2

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

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

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

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

Запишите порядок команд в программе преобразо­вания числа 3 в число 41, содержащей не более 5 ко­манд, указывая лишь номера команд. (Например, 21212 — это программа

Прибавь 4

Умножь на 3

Прибавь 4

Умножь на 3

Прибавь 4,

Которая преобразует число 1 в 61.)

Если таких программ более одной, то запишите лю­бую из них.

Ответ:.

В2. Определите значение переменной «с» после вы­полнения следующего фрагмента программы:

Бейсик	Паскаль
А = -2 B = -3 A = b + а * 3 IF а < b THEN с = а - b ELSE с = b — а ENDIF	А := -2; B := -3; А : = b + а * 3 ; If а < b then с : = а - b else с := b - а;
Си	Алгоритмический язык
А = -2; B = -3; А = b + а * 3; If (а < b) с = а - Ь; else с = b - а;	А := -2, b := -3 а : = b + а * 3 Если а < b то с := а - b Иначе с : = b — а Все

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

	А	В	C	D
1	3		7
2	=(B1-D2)/5	=Cl-Al	=Al-2	=C2*3

Какое число должно быть записано в ячейке Bl, чтобы построенная после выполнения вычислений диаграмма по зна­чениям диапазона ячеек A2:D2 соответствовала рисунку?

Ответ:.

В4. Вася и Петя передают друг другу сообщения, ис­пользуя флажки 3-х цветов (синий, зелёный и крас­ный). Эти они делают, поднимая последовательно один из флажков, потом опускают его и поднимают ещё ка­кой-то. Наименьшее количество поднятий флажков в сообщении — 3, наибольшее — 5. Сколько различных сообщений могут передавать мальчики?

Ответ: ______

В5. Определите, что будет напечатано в результате выполнения следующего фрагмента программы:

Бейсик	Паскаль
DIM k, S AS INTEGER S = I к = 0 WHILE S < 12 S = s + 1 к = к + s s = s + 1 WEND PRINT к	Var к, s: integer; begin S : = 1; к : = 0; While s < 12 do begin S := s + 1; К := к + 1; S := s + 1; End; Write(к); End.
Си	Алгоритмический язык
{ Int к, S; S = l; К = 0; While (s < 12) {s=s+l; К = к + s; S = s + 1; } printf(«%d», к); }	Нач Цел k, s S := 1, к := 0 Нц ПокаS < 12 S := s + 1 К := к + s S := s + 1 КЦ Вывод к KOH

Ответ:,

86. Алгоритм вычисления значения функции F(N), Где П — натуральное число, задан следующими соотно­шениями:

F(N) = F(N— 1) + F(N∕3),При П > 1 и П кратно 3, F(N) = F(N— 1) + 1, при П>1 и и не кратно 3, F(I) = 2.

Чему равно значение функции F(l2)?

В ответе запишите только натуральное число.

Ответ:.

87. Запись числа 7110в системе счисления с основа­нием N оканчивается на 2 и содержит 4 цифры. Чему равно основание этой системы счисления N?

Ответ:.

88. Ниже на 4-х языках записан алгоритм. Получив на вход число Х, этот алгоритм печатает два числа LИ М. Укажите наименьшее из таких чисел Х, при вводе кото­рых алгоритм печатает сначала 3, а потом 5.

Бейсик	Паскаль
DIM X, L, M AS INTEGER INPUT X L = 0: M = 9 WHILE X > 0 L = L + 1 IF M > (X MOD 10) THEN M=X MOD 10 ENDIF X = X ∖ 10 WEND PRINT L PRINT M	Var x, L, M: integer; begin Readln(x); L :=0; M := 9; While x > 0 do begin L := L + 1; If M > (x mod 10) then begin M := x mod 10; end; X:=x div 10; End; Writeln(L); write(M); end.

Си	Алгоритмический язык
#include Void main () { Int х, L, М; Scanf(«%d», &х); L = 0; M = 9; While (х > 0) { L = L + 1; If (М > X % 10) { M = х % 10; } X=X/ 10; ) Printf(«%d∖n%d», L, М); }	Алг нач Цел х, L, M ВводX L := 0; M := 9 Нц Пока х > 0 L := L + 1 ЕслиM > mod(х,10) то M := mod(х,10) Все Х := div(x,10) Кц выводL, нс, M KOH

Ответ:________________

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

Ответ:.

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

А. Сжать архиватором, передать по каналу связи, распаковать.

Б. Передать по каналу связи без использования ар­хиватора.

Какой способ быстрее и на сколько, если:

— средняя скорость передачи данных по каналу связи составляет 221 бит в секунду;

— объём сжатого архиватором документа равен 25% исходного;

— время, требуемое на сжатие документа, — 8 се­кунд, на распаковку — 3 секунды?

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

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

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

Ответ:.

811. В терминологии сетей TCP/IP маской сети на­зывается двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. Обычно маска записы­вается по тем же правилам, что и IP-адрес. Адрес сети получается в результате применения поразрядной ко­нъюнкции к заданному IP-адресу узла и маске.

По заданным IP-адресу узла и маске определите ад­рес сети.

IP-адрес узла: 83.242.234.187

Маска: 255.255.255.224

При записи ответа выберите из приведённых в таб­лице чисел четыре элемента IP-адреса и запишите в нужном порядке соответствующие им буквы. Точки пи­сать не нужно.

А	В	C	D	E	F	G	H
0	83	160	187	224	234	242	255

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

А	В	C	D	E	F	G	H
128	168	255	8	127	0	17	192

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

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

Запрос	Количество найденных страниц
Корвет I Линкор | Фрегат	30000
Фрегат	17000
Линкор	12000
Корвет	8000
Линкор & Фрегат	4000
Корвет & Линкор	3000
Корвет & Линкор & Фрегат	2000

Какое количество страниц будет найдено этой поис­ковой системой по запросу Корвет & Фрегат?

Ответ:.

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

1. прибавь 2,

2. умножь на 2.

Первая из них увеличивает число на экране на 2, вторая удваивает его.

Программа для Удвоителя — это последователь­ность команд.

Сколько есть программ, которые число 1 преобразу­ют в число 24?

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

Бейсик	Паскаль
DIM A, B, T, М, R AS INTEGER А = -30: B=I M=A: R = F(A) FOR T = A TO В IF F(T) < R THEN M = T R = F(T) END IF NEXT T PRINT R FUNCTION F (x) F = 3 * (x — 4) * (x — 4) END FUNCTION	Var a, b, t, M, R: integer; Function F(x:integer): Integer; begin F := 3 * (X — 4) * (x — 4); End ; BEGIN A := -30; b := 1; M := a; R := F(a); For t := a to b do Begin If (F(t) < R) then begin M : = t; R := F(t); End; End; Write (R) ; END.
Си	Алгоритмический язык
Int F(int x) { Return 3 * (x — 4) * (x — 4); } Void main () { Int a, b, t, M, R; A = -30; B = 1; M = a ; R = F(a); For (t = a; t <= b; t++) {if (F(t) < R) (M = t; R = F(t);} } Printf(«%d», R); }	Алг нач целA, b, t, M, R а := -30; b := 1 M := a; R := F(a) Нц дляT от а до b ЕслиF(t)< R То M := t; R ;= F(t) Все кц выводR KOH Алг целF(Цел х) Нач Знач: = 3 * (х-4) * (х-4) KOH

Ответ:,

В15. Сколько существует различных наборов значе­ний логических переменных x1, X2, x3, x4, x5, Yl, у2, У3>Y4, у5, которые удовлетворяют всем перечисленным ни­же условиям?

(.-Xl V Л Л (^^,∙^3 V X4) ∕∖ (-,χ4 V Х$)=1

(У1 У2) Л (у2 Уз> Л (У3 “* У4) Л (У4 -* У5) = 1

(-Y1 V *1) Л (-Y2 V χ2)Л (-Y3 V χ3) Л (-Y4 V χ4)Л (-Y5 V χ5)=1

В ответе Не нужноПеречислять все различные набо­ры значений x1, x2, x3, x4, x5, Yv Y2, у3, у4, у5, при кото­рых выполнена данная система равенств. В качестве от­вета вам нужно указать количество таких наборов.

Ответ:.

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

ЧАСТЬ 3

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

Cl. Требовалось напи­сать программу, при выпол­нении которой с клавиатуры считываются координаты точки на плоскости (х, У — Действительные числа) и оп­ределяется принадлежность этой точки заданной закра­шенной области (включая границы). Программист то­ропился и написал програм­му неправильно.

Паскаль	Бейсик
Var х, у: real; Begin Readln(x, у); Ifx*x + y*y<=l then If у >= х then If х <= 0 then Write (,принадлежит,) else Write(‘не принадлежит’) end.	INPUT x, у IFx*x+y*y<=l THEN IF у >= X THEN IF X <= 0 THEN PRINT «принадлежит» ELSE PRINT «не принадлежит» ENDIF ENDIF ENDIF END
Си	Алгоритмический язык
Void main(void) { Float x, y; Scanf («%.f %f», &x, &y) ; If (x * x + у * у <= 1) If (у >= x) If (x <= 0) Printf(«принадлежит»); else Printf(«не принадлежит»); }	Алг нач вещ х, у Ввод х, у ЕслиX*x+y*y<=l То если у >= х то Если х <= 0 то Вывод‘принадлежит* Иначе Вывод‘не принадлежит’Все все все KOH

Последовательно выпол­ните следующее.

1. Перерисуйте и запол­ните таблицу, которая пока­зывает, как работает про­грамма при аргументах, принадлежащих различным областям (А, В, С, D, Е, F, G иН).

Точки, лежащие на гра­ницах областей, отдельно не рассматривать.

Область	Условие 1 (X*X+Y*Y<=L)	Условие 2 (y>=χ)	Условие 3 (х<=0)	Программа выведет	Область обрабатыва­ется верно
А
В
C
D
E
F
G
H

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

2. Укажите, как нужно доработать программу, что­бы не было случаев её неправильной работы. (Это мож­но сделать несколькими способами, достаточно указать любой способ доработки исходной программы.)

С2. Дан целочисленный массив из 40 элементов. Элементы массива могут принимать произвольные зна­чения. Опишите на русском языке или на одном из языков программирования алгоритм, который находит и выводит номера двух элементов массива, наименее отличающихся друг от друга.

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

Паскаль	Бейсик
Const N = 40; Var a: array [1..N] of Integer; I, j, min, min2, s: integer; begin For i := 1 to N do Readln(a[i]); End.	N = 40 DIM A(N) AS INTEGER DIM I, J, MIN, MIN2 AS INTEGER FOR I = 1 TO N INPUT A(I) NEXT I END
СИ	Алгоритмический язык
#include #define N 40 void main(void) {int a[N]; Int i, j, min, min2, s; For (i = 0; i < N; i++) scanf("%d", ⅛a[i]); }	Ал г нач целN = 40 Целтаб а[1:N] ЦелI, j, MIN, MIN2, s Нц дляI от 1 до N Ввод а[i J Кц KOH
Русский (естественный) язык
Объявляем массив А из 40 элементов. Объявляем целочисленные переменные I, J, MIN, MIN2, S. В цикле от 1 до 40 вводим элементы массива А с 1-го по 40-й.

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

СЗ. Два игрока, Петя и Ваня, играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 2, а во второй — 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очере­ди, первый ход делает Петя. Ход состоит в том, что иг­рок или удваивает число камней в какой-то куче, или добавляет 3 камня в какую-то кучу. Игра завершается в тот момент, когда количество камней в одной из куч становится не менее 16. Если в момент завершения иг­ры общее число камней в двух кучах не менее 20, то вы­играл Ваня, в противном случае — Петя. Кто выигры­вает при безошибочной игре обоих игроков? Каким дол­жен быть первый ход выигрывающего игрока? Ответ обоснуйте.

С4. На вход программе подаётся последовательность символов, заканчивающаяся символом #. Другие сим­волы # во входной последовательности отсутствуют.

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

Напишите эффективную, в том числе и по использу­емой памяти, программу (укажите используемую вер­сию языка программирования, например, Borland Pascal 7.0), которая должна решать поставленную за­дачу.

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

Aced, ccedaa f#

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

FDEAC