Инструкция по выполнению работы

Единый государственный экзамен по ИНФОРМАТИКЕ и ИКТ

Экзаменационная работа состоит из двух частей, включающих в себя 27 заданий. Часть 1 содержит 23 задания с кратким ответом, часть 2 содержит 4 задания с развёрнутым ответом.

На выполнение экзаменационной работы по информатике и ИКТ отводится 3 часа 55 минут (235 минут).

Ответы к заданиям 1–23 записываются в виде числа, последовательности букв или цифр. Ответы запишите в поле ответа в тексте работы, а затем перенесите в бланк ответов № 1.

 

Задания 24–27 требуют развёрнутого ответа. В бланке ответов № 2 укажите номер задания и запишите его полное решение.

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

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

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

 

Желаем успеха!

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

 

1. Обозначения для логических связок(операций):

a) отрицание (инверсия, логическое НЕ) обозначается (например,А);

b) конъюнкция (логическое умножение, логическое И) обозначается /\ (например, А /\ В) либо & (например, А &В);

c) дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/ (например, А \/ В) либо | (например, А |В);

d) следование (импликация) обозначается → (например, А →В);

e) тождество обозначается ≡ (например, A ≡ B). Выражение A ≡ B истинно тогда и только тогда, когда значения A и B совпадают (либо они оба истинны, либо они оба ложны);

f) символ 1 используется для обозначения истины (истинного высказывания); символ 0 – для обозначения лжи (ложноговысказывания).

 

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

 

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

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

 

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

 

Часть 1

Ответами к заданиям 1–23 являются число, последовательность букв или цифр, которые следует записать в БЛАНК ОТВЕТОВ № 1 справа от номера соответствующего задания, начиная с первой клеточки, безпробелов,запятыхидругихдополнительных символов. Каждый символ пишите в отдельной клеточке в соответствии с приведёнными в бланке образцами.

1

Сколько значащих нулей в двоичной записи восьмеричного числа 1253₈?

4

Ответ:                                                    .

 

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути из пункта Вв пункт Е.

Ответ:                                                    .

 

2

ЛогическаяфункцияFзадаётсявыражением(x∧y∧z)∨(x∧y∧

ID Фамилия_И.О Пол 1072 Онищенко А.Б. Ж 1028 Онищенко Б.Ф. М 1099 Онищенко И.Б. М 1178 Онищенко П.И. М 1156 Онищенко Т.Н. Ж 1065 Корзун А.И. Ж 1131 Корзун А.П. М 1061 Корзун Л.А. Ж 1217 Корзун П.А. М 1202 Зельдович М.А Ж 1027 Витюк Д.К. Ж 1040 Лемешко В.А. Ж 1046 Месяц К.Г. М 1187 Лукина Р.Г. Ж 1093 Фокс П.А. Ж 1110 Дрк Г.Р. Ж

z) ∨ (x ∧ y ∧ z). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы

В фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите идентификатор (ID) родной сестры Лемешко В.А.

истинности функции F соответствует каждая из переменных x, y, z.

 

?	?	?	F
0	0	0	1
1	0	0	1
1	0	1	1

В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (без разделителей).

Ответ:                                                    .

 

3

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

Таблица 1

Таблица 2

 

ID_Родителя ID_Ребенка 1072 1072 1027 1099 1028 1072 1028 1099 1072 1040 1072 1202 1072 1217 1099 1156 1099 1178 1110 1156 1110 1178 1131 1040 1131 1202 1131 1217 1187 1061 1187 1093

П1 П2 П3 П4 П5 П6 П7 П1         10 15   П2       5     15 П3       10   10   П4   5 10     25   П5 10         30   П6 15   10 25 30   20 П7   15       20

Ответ:                                       .

 

 

5

Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К – кодовое слово 10. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

Ответ:                                                    .

 

6

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1. Строится двоичная запись числаN.

2. К этой записи дописываются справа ещё два разрядапо следующемуправилу:

а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа

R. Укажите такое наименьшее число R, которое превышает 43 и может являться результатом работы алгоритма. В ответе это число запишитев десятичной системесчисления.

Ответ:                                                    .

 

7

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

 

	A	B	C
1	20	???	35
2	= C1-2*B1*B1	=(B1*B1*B1-4)/A1	=C1-8*B1

Ответ:                                                    .

 

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

 

Паскаль	Python	Си
var n, s: integer; begin n:= 0; s:= 0; while s <= 365 do begin s:= s + 33; n:= n + 5 end; write(n) end.	n = 0 s = 0 while s <= 365: s = s + 33 n = n + 5 print(n)	#include <stdio.h>int main() { int n = 0, s = 0; while (s <= 365) { s = s + 33; n = n + 5; } printf("%d", n); return 0; }

 

8

Ответ:                                                    .

 

9

Какой минимальный объём памяти (в Кбайт) нужно зарезервировать, чтобы можно было сохранить любое растровое изображение размером 128×128 пикселей при условии, что в изображении могут использоваться 128 различных цветов? В ответе запишите только целое число, единицу измерения писать не нужно.

Ответ:                                                    .

 

10

Сколько слов длины 5, начинающихся с гласной буквы, можно составить из букв Е, Г, Э? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Ответ:                                                    .

 

 

11

Функция F(n), где n – натуральное число, задана следующим образом:

 

Паскаль	Python	Си
function F(n: integer): integer; begin if n < 5then F:= F(3*n)+ F(n + 3) + F(n + 1) else F:= n div2; end;	def F(n): if n < 5: return F(3*n) + \ F(n + 3) + \ F(n + 1) else: return n // 2	void F(int n) { if (n < 5) return F(3*n) + F(n + 3) + F(n + 1); else return n // 2; }

 

 

Ответ:                                                    .

 

12

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

Маска: 255.255.248.0

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

 

 

A	B	C	D	E	F	G	H
0	12	16	132	135	160	168	170

 

Ответ:                                                  .

 

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора: А, В, C, D, Е, F, G, H, K, L, M, N. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 20 пользователях потребовалось 300 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе?

13

Ответ:                                                    .

 

 

14

Исполнитель Редактор получает на вход строку цифр и преобразовывает её.Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

1. заменить (v,w)

2. нашлось(v)

Первая команда заменяет в строке первое слева вхождение цепочки v на

цепочку w, вторая проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь».

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 21 цифры, причем первые девять цифр – четверки, а остальные – пятерки? В ответе запишите полученную строку.

НАЧАЛО

ПОКА нашлось (444) ИЛИ нашлось (888)

ЕСЛИ нашлось (444)

ТО заменить (444, 8) КОНЕЦ ЕСЛИ

ПОКА нашлось (555)

заменить (555, 8) КОНЕЦ ПОКА

ПОКА нашлось (888)

заменить (888, 3) КОНЕЦ ПОКА

 

 

КОНЕЦ ПОКА КОНЕЦ

Ответ:                                                    .

 

 

15

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

Ответ:                                                    .

 

16

Сколько единиц в двоичной записи числа 42016 – 22018 + 8800 – 80

Ответ:                                                    .

 

17

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

 

Запрос	Количество страниц(тыс.)
Нос&(Ключица&Хрящ\Нога)	570
Нос&Ключица&Хрящ	436
Нось&Ключица&Хрящ&Нога	68

 

Какое количество страниц будет найдено по  запросу

Нос&Нога

Ответ:                                                    .

 

Обозначим черезДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа А формула

18

ДЕЛ(x,А) → (ДЕЛ(x,21) ∨ ДЕЛ(x,35))

тождественно истинна (то есть принимает значение 1 прилюбом натуральном значении переменнойх)?

Ответ:                                                    .

 

 

19

В программе используется одномерный целочисленный массив A с индексами от 0 до 9. Значения элементов равны 4, 7, 3, 8, 5, 0, 1, 2, 9, 6 соответственно, т.е. A[0] = 4, A[1] = 7 и т.д. Определите значение переменной c после выполнения следующего фрагмента этой программы.

 

Паскаль	Python	Си
c:= 0; for i:= 1 to 9 do if A[i] < A[0] then begin c:= c + 1; t:= A[i]; A[i]:= A[0]; A[0]:= t; end;	c = 0 for i in range(1,10): if A[i] < A[0]: c = c + 1 t = A[i] A[i] = A[0] A[0] = t	c = 0; for (i = 1;i < 10;i++) if (A[i] < A[0]) { c++; t = A[i]; A[i] = A[0]; A[0] = t; }

 

Ответ:                                                    .

 

 

20

Укажите наибольшее из таких чисел x, при вводе которых алгоритм печатает сначала 3, а потом 120.

 

 

Паскаль	Python	Си
var x, L, M: integer; begin readln(x); L:=0;M:=1; while x > 0 do begin L:=L+1; M:= M*(x mod 8); x:= x div8; end; writeln(L); write(M); end.	x = int(input()) L = 0 M = 1 while x > 0: L = L+1 M = M*(x % 8) x = x // 8 print(L) print(M)	#include <stdio.h>intmain(void) { int L, M, x; scanf(″%d″,&x); L = 0; M =1; while (x > 0) { L = L + 1; M = M*(x % 8); x = x / 8; } printf(″%d\n%d″, L, M); }

 

Ответ:                                                    

Определите, количество чисел k, для которых следующая программа выведет такой же результат, что и для k = 12?

 

 

Паскаль	Python	Си
var k, i: longint; function f(n: longint): longint; begin f:= 3*n*n - 2*n; end; begin readln(k); i:= 1; while f(i) < k do i:= i + 1; if f(i)-k <= f(i-1) then writeln(i) else writeln(i-1); end.	def f(n): return 3*n*n - 2*n k = int(input()) i = 1 while f(i) < k: i += 1 if f(i)-k <= f(i- 1): print(i) else: print(i-1)	#include <stdio.h> long f(long n) { return 3*n*n - 2*n; } int main() { long k, i; scanf("%ld", &k); i = 1; while (f(i) < k ) i++; if (f(i)-k <= f(i- 1)) printf("%ld", i); else printf("%ld", i-1); return 0; }

 

21

Ответ:                                                    .

 

22

Исполнитель Калькулятор преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить1

2. Умножить на2

Программа для исполнителя Калькулятор – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 21 и при этом траектория вычислений содержит число 10?

Ответ:                                                    .

 

23

Сколько существует различных наборов значений логическихпеременных x₁, x₂,... x₇, y₁, y₂,... y₇, которые удовлетворяют всем перечисленным ниже условиям?

Часть 2

(x₁∨ y₁) ≡ (x₂∧ y₂) (x₂∨ y₂) ≡ (x₃∧ y₃)

...

(x₆∨y₆) ≡ (x₇∧y₇)Ответ:                                                       .

 

 

Для записи ответов на задания этой части (24–27) используйте БЛАНК ОТВЕТОВ № 2. Запишите сначала номер задания (24, 25 и т. д.), а затем полное решение. Ответы записывайте чётко и разборчиво.

Для заданного положительного вещественного числа A необходимо найти минимальное целое число K, при котором выполняется неравенство.

24

1 + (1/2) + (1/3) +... + (1/K) ≥ A

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

Программист написал программу неправильно.

Паскаль	Python	Си
var a, s: real; k: integer; begin read(a); k:=0; s:=1; while s >= a do begin k:= k + 1; s:= s + 1.0/k; end; write(k); end.	a = float(input()) k =0 s = 1 while s >= a: k = k + 1 s = s + 1.0/k print(k)	#include <stdio.h>int main() { float a, s; int k; scanf("%f", &a); k = 0; s = 1; while (s >= a) { k = k + 1; s = s + 1./k; } printf("%d", k); return 0; }

 

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

1. Напишите, что выведет эта программа при вводе числа 1.4.

2. Сколько существует натуральных чисел А, при вводекоторых программа выведет ответ 1?

3. Найдите все ошибки в этой программе (их может быть однаили несколько). Известно, что каждая ошибка затрагивает толькоодну строку и может быть исправлена без изменения других строк. Для каждойошибки:

1) выпишите     строку,     в      которой     сделана    ошибка;

2) укажите, как исправить ошибку, т.е. приведите правильный вариантстроки.

 

 

25

27 Последовательность натуральных чисел характеризуется числом Х – наиболь-шим числом, кратным 14 и являющимся произведением двух элементов после- довательности с различными номерами. Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, BorlandPascal 7.0), находящую число X для по-следовательности натуральных чисел, значение каждого элемента которой не превосходит 1000. Программа должна напечатать найденное число, если оно существует для заданной последовательности, или ноль в противном случае. На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. Пример входных данных: 5 40 1000 7 28 55 Пример выходных данныхдля приведённого выше примера входных данных: 28000

Дан массив, содержащий 40 положительных целых чисел. Напишите на одном из языков программирования программу, которая находит в этом массиве количество локальных минимумов. Локальным минимумом называется элемент массива, который меньше всех своих соседей. Например, в массиве из 6 элементов, содержащем числа 4, 6, 12, 7, 3, 8, есть два локальных минимума: это элементы, равные 4 и 3. Программа должна вывести общее количество подходящих элементов, значения элементов выводить не нужно.

 

 

Паскаль	Python	Си
const n = 40; var a: array [0..n-1] ofinteger; i, j, k: integer; begin for i:= 0 to n-1 do readln(a[i]); ... end.	# допускаетсятакже # использовать две #целочисленные # переменные j, k a = [] n = 40 for i in range(n):   a.append(int(input())) ...	#include <stdio.h> #define n 40 int main() { int a[n]; inti, j, k; for (i = 0; i< n; i++) scanf("%d", &a[i]); ... return 0; }

26

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) два камня или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 55. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 55 камней или больше. Задание 1. Для каждой из начальных позиций (8, 23), (9, 22) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю              для выигрыша              при            этой              стратегии. Задание 2. Для каждой из начальных позиций (8, 21), (8,22), (9,21) укажите, кто              из       игроков                        имеет              выигрышную стратегию. Задание 3. Для начальной позиции (9,19) укажите, кто из игроков имеет выигрышную стратегию. Постройте дерево всех партий, возможных при указанной вами выигрышной стратегии. Представьте дерево в виде рисунка илитаблицы.