Тренировочный вариант ЕГЭ по информатике №1

1. Задание

Вычислите значение выражения 9E1694169E_{16} - 94_{16}. В ответе запишите вычисленное значение в десятичной системе счисления.

2. Задание

Миша заполнял таблицу истинности функции (¬x¬y)(yz)¬w,\left(\lnot x \wedge \lnot y \right) \vee \left(y \equiv z \right) \vee \lnot w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных ww, xx, yy, zz.
(¬x¬y)(yz)¬w\left(\lnot x \wedge \lnot y \right) \vee \left(y \equiv z \right) \vee \lnot w
00001100
001100
00111100
Определите, какому столбцу таблицы соответствует каждая из переменных ww, xx, yy, zz.
В ответе напишите буквы ww, xx, yy, zz в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть функция была задана выражением ¬xy\lnot x \vee y, зависящим от двух переменных, а фрагмент таблицы имел вид:
¬xy\lnot x \vee y
001100
Тогда первому столбцу соответствовала переменная yy, а второму столбцу – переменная xx. В ответе следовало бы написать yxyx.

3. Задание

На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам BB и CC на схеме.
В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

4. Задание

Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка Таблицы 22 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке Таблицы 11. На основании приведённых данных определите наибольшую разницу между годами рождения родных сестёр. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц.
Примечание. Братьев (сестёр) считать родными, если у них есть хотя бы один общий родитель.

Таблица 1

IDФамилия_И.О.ПолГод_рождения
6464Келдыш С.М.М19891989
6666Келдыш О.Н.Ж19641964
6767Келдыш М.И.М19621962
6868Дейнеко Е.В.Ж19741974
6969Дейнеко Н.А.Ж19941994
7070Сиротенко В.Н.М19661966
7272Сиротенко Д.В.Ж19951995
7575Сиротенко Н.П.М19371937
7777Мелконян А.А.М19871987
8181Мелконян И.Н.Ж19631963
8282Лурье А.В.Ж19891989
8686Хитрово Н.И.М19401940
8888Хитрово Т.Н.Ж19681968
8989Гурвич З.И.Ж19401940

Таблица 2

ID_РодителяID_Ребёнка
66666464
67676464
86866666
81816969
75757070
89897070
70707272
88887272
81817777
75758181
89898181
70708282
88888282
86868888

5. Задание

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 00, для буквы Б – кодовое слово 1010. Какова наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

6. Задание

На вход алгоритма подаётся натуральное число NN. Алгоритм строит по нему новое число RR следующим образом.
  1. Строится двоичная запись числа NN.
  2. К этой записи дописываются справа ещё два разряда по следующему правилу: если NN чётное, в конец числа (справа) дописывается сначала ноль, а затем единица. В противном случае, если NN нечётное, справа дописывается сначала единица, а затем ноль.
    Например, двоичная запись 100100 числа 44 будет преобразована в 1000110001, а двоичная запись 111111 числа 77 будет преобразована в 1111011110.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа NN) является двоичной записью числа RR – результата работы данного алгоритма.
Укажите минимальное число RR, которое больше 102102 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.

7. Задание

Дан фрагмент электронной таблицы. Из ячейки C3 в ячейку D4 была скопирована формула. При копировании адреса ячеек в формуле автоматически изменились. Каким стало числовое значение формулы в ячейке D4?
ABCDE
111122334455
2220203030404050506060
33300300400400=$B$3+D2600600700700
4440004000500050006000600080008000
Примечание. Знак $ обозначает абсолютную адресацию.

8. Задание

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

Бейсик

DIM S, N AS INTEGER
S = 0
N = 75
WHILE S + N < 150
  S = S + 15
  N = N - 5
WEND
PRINT N

Python

s = 0
n = 75
while s + n < 150:
 s = s + 15
 n = n - 5
print(n)

Алгоритмический язык

алг
нач
 цел n, s
 s := 0
 n := 75
 нц пока s + n < 150
  s := s + 15
  n := n - 5
 кц
 вывод n
кон

Паскаль

var s, n: integer;
begin
 s := 0;
 n := 75;
 while s + n < 150 do
 begin
  s := s + 15;
  n := n - 5
 end;
 writeln(n)
end.

С++

#include <iostream>
using namespace std;

int main() {
 int s = 0, n = 75;
 while (s + n < 150) {
  s = s + 15;
  n = n - 5;
 }
 cout << n << endl;
 return 0;
}

9. Задание

Автоматическая камера производит растровые изображения размером 200×256200\times256 пикселей. Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков. Объём файла с изображением не может превышать 6565 Кбайт без учёта размера заголовка файла. Какое максимальное количество цветов можно использовать в палитре?

10. Задание

Вася составляет 55-буквенные слова, в которых есть только буквы З, И, М, А, причём в каждом слове есть ровно одна гласная буква и она встречается ровно 11 раз. Каждая из допустимых согласных букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

11. Задание

Ниже на пяти языках программирования записан рекурсивный алгоритм FF.

Бейсик

SUB F(n)
 IF n > 0 THEN
  F(n - 1)
  PRINT n
  F(n - 2)
 END IF
END SUB

Python

def F(n):
 if n > 0:
  F(n - 1)
  print(n)
  F(n - 2)

Алгоритмический язык

алг F(цел n)
нач
 если n > 0 то
  F(n - 1)
  вывод n
  F(n - 2)
 все
кон

Паскаль

procedure F(n: integer);
begin
 if n > 0 then
 begin
  F(n - 1);
  write(n);
  F(n - 2)
 end
end;

С++

void F(int n){
 if (n > 0){
  F(n - 1);
  std::cout << n;
  F(n - 2);
 }
}
Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(4). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

12. Задание

В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес, – в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого разряда – нули. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске.
Пример. Если IP-адрес узла равен 231.32.255.131231.32.255.131, а маска равна 255.255.240.0255.255.240.0, то адрес сети равен 231.32.240.0231.32.240.0.
Для узла с IP-адресом 117.191.37.84117.191.37.84 адрес сети равен 117.191.37.80117.191.37.80. Чему равно наименьшее возможное значение последнего (самого правого) байта маски?
Ответ запишите в виде десятичного числа.

13. Задание

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 77 символов и содержащий только символы из 2626-символьного набора прописных латинских букв. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт, это число одно и то же для всех пользователей.
Для хранения сведений о 3030 пользователях потребовалось 600600 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.

14. Задание

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в которых vv и ww обозначают последовательности цифр:
А) заменить (v,w)(v, w).
Эта команда заменяет в строке первое слева вхождение последовательности vv на последовательность ww. Например, выполнение команды заменить (111,27)(111, 27) преобразует строку 0511115005111150 в строку 05271500527150.
Если в строке нет вхождений последовательности vv, то выполнение команды заменить (v,w)(v, w) не меняет эту строку.
Б) нашлось (v)(v).
Эта команда проверяет, встречается ли последовательность vv в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
 ПОКА условие
 последовательность команд
 КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции
 ЕСЛИ условие
  ТО команда1
 КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно).
В конструкции
 ЕСЛИ условие
  ТО команда1
  ИНАЧЕ команда2
 КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 8282 идущих подряд цифр 11?
НАЧАЛО
ПОКА нашлось (11111) ИЛИ нашлось (888)
 ЕСЛИ нашлось (11111)
  ТО заменить (11111, 88)
 ИНАЧЕ
  ЕСЛИ нашлось (888)
   ТО заменить (888, 8)
  КОНЕЦ ЕСЛИ
 КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
В ответе запишите полученную строку.

15. Задание

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

16. Задание

Значение арифметического выражения 97+32199^{7} + 3^{21} - 9 записали в системе счисления с основанием 33. Сколько цифр «22» содержится в этой записи?

17. Задание

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для обозначения логической операции «И» – символ «&».
В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
ЗапросНайдено страниц (в сотнях тысяч)
Горло3535
Корабль3535
Нос4040
Корабль & Нос2020
Горло & Нос1313
Горло & Корабль00
Какое количество страниц (в сотнях тысяч) будет найдено по запросу Горло | Корабль | Нос?
Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

18. Задание

Для какого наибольшего целого неотрицательного числа AA выражение (48y+2x)(A<x)(A<y)\left(48≠y+2x \right)\vee \left(A < x \right) \vee \left(A < y \right) тождественно истинно, т.е. принимает значение 11 при любых целых неотрицательных xx и yy?

19. Задание

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

Бейсик

c = 0
FOR i = 1 TO 9
 IF A(i-1) < A(i) THEN
  c = c + 1
  t = A(i)
  A(i) = A(i-1)
  A(i-1) = t
 END IF
NEXT i

Python

c = 0
for i in range(1, 10):
 if A[i-1] < A[i]:
  c = c + 1
  A[i-1], A[i] = A[i], A[i-1]

Алгоритмический язык

c := 0
нц для i от 1 до 9
 если A[i-1] < A[i] то
  c := c + 1
  t := A[i]
  A[i] := A[i-1]
  A[i-1] := t
 все
кц

Паскаль

c := 0;
for i := 1 to 9 do
 if A[i-1] < A[i] then
 begin
  c := c + 1;
  t := A[i];
  A[i] := A[i-1];
  A[i-1] := t;
 end;

С++

c = 0;
for (int i = 1; i < 10; i++)
 if (A[i-1] < A[i]){
  c++;
  t = A[i];
  A[i] = A[i-1];
  A[i-1] = t;
 }

20. Задание

Ниже на пяти языках программирования записан алгоритм. Получив на вход натуральное десятичное число xx, этот алгоритм печатает два числа: LL и MM.
Укажите наибольшее число x,x, при вводе которого алгоритм печатает сначала 2121, а потом 33.

Бейсик

DIM X, L, M AS INTEGER
INPUT X
L = 1
M = 0
WHILE X > 0
 M = M + 1
 IF X MOD 2 <> 0 THEN
  L = L * (X MOD 8)
 END IF
 X = X \ 8
WEND
PRINT L
PRINT M

Python

x = int(input())
L = 1
M = 0
while x > 0:
 M = M + 1
 if x % 2 != 0:
  L = L * (x % 8)
 x = x // 8
print(L)
print(M)

Алгоритмический язык

алг
нач
 цел x, L, M
 ввод x
 L := 1
 M := 0
 нц пока x > 0
  M := M + 1
  если mod(x,2) <> 0 то
   L := L * mod(x,8)
  все
  x := div(x,8)
 кц
 вывод L, нс, M
кон

Паскаль

var x, L, M: integer;
begin
 readln(x);
 L := 1;
 M := 0;
 while x > 0 do
 begin
  M := M + 1;
  if x mod 2 <> 0 then
   L := L * (x mod 8);
  x := x div 8
 end;
 writeln(L);
 writeln(M)
end.

С++

#include <iostream>
using namespace std;

int main(){
 int x, L, M;
 cin >> x;
 L = 1;
 M = 0;
 while (x > 0) {
  M = M + 1;
  if(x % 2 != 0) {
   L = L * (x % 8);
  }
  x = x / 8;
 }
 cout << L << endl << M << endl;
 return 0;
}

21. Задание

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

Бейсик

DIM A, B, T, M, R AS LONG
A = -20: B = 20
M = A: R = F(A)
FOR T = A TO B
 IF F(T) <= R THEN
  M = T
  R = F(T)
 END IF
NEXT T
PRINT M + R

FUNCTION F(x)
 F = abs(abs(x - 6) + abs(x + 6) - 16) + 2
END FUNCTION

Python

def F(x):
 return abs(abs(x - 6) + abs(x + 6) - 16) + 2

a = -20
b = 20
M = a
R = F(a)
for t in range(a, b + 1):
 if (F(t) <= R):
  M = t
  R = F(t)
print (M + R)

Алгоритмический язык

алг
нач
цел a, b, t, M, R
 a := -20; b := 20
 M := a; R := F(a)
 нц для t от a до b
  если F(t) <= R то
   M := t; R := F(t)
  все
 кц
 вывод M + R
кон
алг цел F(цел x)
нач
 знач := iabs(iabs(x - 6) + iabs(x + 6) - 16) + 2
кон

Паскаль

var a, b, t, M, R : longint;
function F(x: longint) : longint;
begin
 F := abs(abs(x - 6) + abs(x + 6) - 16) + 2;
end;

begin
 a := -20; b := 20;
 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(M + R)
end.

С++

#include <iostream>
using namespace std;

long F(long x) {
 return abs(abs(x - 6) + abs(x + 6) - 16) + 2;
}

int main() {
 long a = -20, b = 20, M = a, R = F(a);
 for (int t = a; t <= b; ++t) {
  if (F(t) <= R) {
   M = t; R = F(t);
  }
 }
 cout << M + R;
 return 0;
}

22. Задание

Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
  1. Прибавить 22
  2. Умножить на 22
  3. Прибавить 33
Первая из них увеличивает число на экране на 22, вторая умножает его на 22, третья увеличивает его на 33.
Программа для Вычислителя – это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 22 в число 2222 и при этом траектория вычислений программы содержит число 1111?
Примечание. Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Пример. Для программы 123123 при исходном числе 77 траектория будет состоять из чисел 9,18,219, 18, 21.

23. Задание

Сколько существует различных наборов значений логических переменных x1,x2,x7,y1,y2,y7x_{1}, x_{2}, … x_{7}, y_{1}, y_{2}, … y_{7}, которые удовлетворяют всем перечисленным ниже условиям?
(y1(y2x1))(x1x2)=1\left(y_{1} \rightarrow \left(y_{2} \wedge x_{1} \right) \right) \wedge \left(x_{1} \rightarrow x_{2} \right) = 1
(y2(y3x2))(x2x3)=1\left(y_{2} \rightarrow \left(y_{3} \wedge x_{2} \right) \right) \wedge \left(x_{2} \rightarrow x_{3} \right) = 1

(y6(y7x6))(x6x7)=1\left(y_{6} \rightarrow \left(y_{7} \wedge x_{6} \right) \right) \wedge \left(x_{6} \rightarrow x_{7} \right) = 1
y7x7=1y_{7} \rightarrow x_{7} = 1
В ответе не нужно перечислять все различные наборы значений переменных x1,x2,x7,y1,y2,y7x_{1}, x_{2}, … x_{7}, y_{1}, y_{2}, … y_{7}, при которых выполнена данная система равенств. Укажите в качестве ответа количество таких наборов.