Пробный вариант ЕГЭ 2018 по информатике

ЕГЭ 2018 Вариант 1 1.  Сколько   существует   натуральных   чисел x, неравенство D716 < x < DF16?   для   которых   выполняется 2. Логическая функция F задаётся выражением ¬x \/ y \/ (¬z /\ w). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы  аргументов, при которых функция F ложна. Определите, какому столбцу таблицы  истинности функции F соответствует каждая из переменных w, x, y, z. Переменная 1 Переменная 4 Функция Переменная 2 Переменная 3 ??? 0 0 0 ??? 0 1 1 ??? 0 0 1 ??? 1 1 1 F 0 0 0 3. На рисунке справа схема дорог Н­ского района изображена в виде графа, в таблице  содержатся сведения о протяжённости каждой из этих дорог (в километрах). П1 П2 П3 П4 П5 П6 П7 15 15 9 7 15 15 9 7 12 14 10 12 20 20 10 14 П1 П2 П3 П4 П5 П6 П7 Определите, какова протяжённость дороги из пункта А в пункт В. 4. Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона.  Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей.  Информация представлена значением поля ID в соответствующей строке таблицы 1.  Определите на основании приведённых данных, у скольких детей на момент их рождения  отцам было меньше 23 полных лет. При вычислении ответа учитывайте только  информацию из приведённых фрагментов таблиц. Таблица 1   Таблица 2 ID Фамилия_И.О. Пол Год_рождения   ID_Родителя ID_Ребёнка 15 Петрова Н.А. Ж 1944 22 Иваненко И.М. 23 Иваненко М.И. М М 1940 1968       22 42 23 23 23 24 ФИПИ 2018 ЕГЭ 2018 24 Иваненко М.М. М 1993 32 33 35 Будай А.И. Будай В.С. Будай С.С. 42 Коладзе А.С. 43 Коладзе Л.А. 44 46 Родэ О.С. Родэ М.О. Ж Ж М Ж М М М 1960 1987 1965 1941 1955 1990 2010 52 Ауэрман А.М. Ж 1995 73 Антонова М.А. Ж 1967 … … … …                       73 22 42 32 35 15 32 35 23 73 … 24 32 32 33 33 35 44 44 52 52 …             Буква Л Р С Т У 00   010 011 1111 5. По каналу связи передаются шифрованные сообщения, содержащие только десять букв:  А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для  девяти букв используются кодовые слова. Буква Кодовое слово А Б Е И К Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять  условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым  значением. 6. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое  число R следующим образом. 1)    Строится двоичная запись числа N. ФИПИ 2018 Кодовое слово 1101 1010 1110 1011 100 ЕГЭ 2018 2)    К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2  дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись  111001; б) над этой записью производятся те же действия – справа дописывается остаток от  деления суммы её цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного  числа N) является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает число 51 и может являться  результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления. 7. Дан фрагмент электронной таблицы. Из ячейки E4 в ячейку D3 была скопирована  формула. При копировании адреса ячеек в формуле автоматически изменились. Каким  стало числовое значение формулы  в ячейке D3? А 40 30 20 10 1 2 3 4 8. Запишите число, которое будет напечатано в результате выполнения следующей  программы.  var s, n: integer; begin   s := 265;   n := 0;   while s > 0 do   begin     s := s ­ 10;     n := n + 2   end;   writeln(n) end. С 400 300 200 100 D 70 60 40 В 4 3 2 1 E 7 6 5 = $B2 * C$3 9. Музыкальный фрагмент был записан в формате стерео (двухканальная запись),  оцифрован и сохранён в виде файла без использования сжатия данных. Размер полученного файла – 40 Мбайт. Затем тот же музыкальный фрагмент был записан повторно в формате  моно и оцифрован с разрешением в 3 раза выше и частотой дискретизации в 5 раз меньше,  чем в первый раз. Сжатие данных не производилось. Укажите размер файла в Мбайт,  полученного при повторной записи. В ответе запишите только целое число, единицу  измерения писать не нужно. 10. Все 4­буквенные слова, составленные из букв М, А, Р, Т, записаны  в алфавитном порядке и пронумерованы, начиная с 1. Ниже приведено начало списка. 1.  АААА ФИПИ 2018 ЕГЭ 2018 2.  АААМ 3.  АААР 4.  АААТ 5.  ААМА … Под каким номером в списке идёт первое слово, которое начинается с буквы М? 11. Ниже записаны две рекурсивные функции (процедуры): F и G. procedure F(n: integer); forward; procedure G(n: integer); forward;   procedure F(n: integer); begin   if n > 0 then     G(n ­ 2); end;   procedure G(n: integer); begin   writeln('*');   if n > 1 then     F(n ­ 1); end; Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(9)? 12. Для узла с IP­адресом 119.83.208.27 адрес сети равен 119.83.192.0. Каково наименьшее  возможное количество единиц в разрядах маски? 13. При регистрации в компьютерной системе каждому пользователю выдаётся пароль,  состоящий из 10 символов. В качестве символов используют прописные буквы латинского  алфавита, т.е. 26 различных символов. В базе данных для хранения каждого пароля  отведено одинаковое и минимально возможное целое число байт. При этом используют  посимвольное кодирование паролей, все символы кодируют одинаковым  и минимально возможным количеством бит. Определите объём памяти (в байтах), необходимый для хранения данных о 50 пользователях. В ответе запишите только целое число – количество байт. 14. Чертёжнику был дан для исполнения следующий алгоритм (число повторений и  величины смещения в первой из повторяемых команд неизвестны):  НАЧАЛО   сместиться на (4, ­1)   ПОВТОРИ … РАЗ     сместиться на (…, …)     сместиться на (­4, 4)   КОНЕЦ ПОВТОРИ   сместиться на (­28, ­17) КОНЕЦ   В результате выполнения этого алгоритма Чертёжник возвращается в исходную точку.  Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ …  РАЗ»? ФИПИ 2018 ЕГЭ 2018 15.На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К,  Л, М. По каждой дороге можно двигаться только в одном направлении, указанном  стрелкой. Сколько существует различных путей из города А в город М, проходящих через  город Д?   16. Значение арифметического выражения: 4914 + 742 – 49 – записали в системе счисления с основанием 7. Сколько цифр «6» содержится в этой записи? 17. В таблице приведены запросы и количество найденных по ним страниц некоторого  сегмента сети Интернет. Запрос Найдено страниц (в сотнях тысяч) Поле Пшеница Напряжённость Напряжённость | Поле | Пшеница Напряжённость & Поле Напряжённость & Пшеница   45 24 44 74 19 0 Какое количество страниц (в сотнях тысяч) будет найдено по запросу Поле & Пшеница?  ((¬(→ x ∈ B) /\ ¬(x ∈ A)) → ¬(x ∈ D)) 18. На числовой прямой даны два отрезка: D = [135; 161] и B = [149; 174]. Укажите  наименьшую возможную длину такого отрезка A, что формула (x ∈ D)  истинна, т.е. принимает значение 1 при любом значении переменной х. 19. В программе используется одномерный целочисленный массив A  с индексами от 0 до 9. Значения элементов равны 4, 7, 3, 8, 5, 0, 1, 2, 9, 6 соответственно,  т.е. A[0] = 4, A[1] = 7 и т.д. Определите значение переменной c после выполнения следующего фрагмента этой  программы .  c := 0; for i := 1 to 9 do   if A[i­1] < A[i] then   begin ФИПИ 2018 ЕГЭ 2018     c := c + 1;     t := A[i];     A[i] := A[i­1];     A[i­1] := t;   end; 20. Ниже записан алгоритм. Получив на вход число x, этот алгоритм печатает два  числа: L и M. Укажите наибольшее число x, при вводе которого алгоритм печатает сначала 5, а потом 9. var x, L, M: integer; begin   readln(x);   L := 0;   M := 0;   while x > 0 do   begin     M := M + 1;     if x mod 2 <> 0 then       L := L + 1;     x := x div 2;   end;   writeln(L);   writeln(M); end. 21. Напишите в ответе число, которое будет напечатано в результате выполнения  следующего алгоритма.  var a, b, t, M, R :longint; function F(x: longint) : longint;   begin     F := 2*(x*x­25)*(x*x­25)+27;   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. ФИПИ 2018 ЕГЭ 2018 22. Исполнитель К17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера: 1.    Прибавить 1 2.    Прибавить 2 3.    Умножить на 2 Сколько существует таких программ, которые преобразуют исходное число 3 в число 12 и  при этом траектория вычислений программы содержит числа 9 и 11? Траектория должна  содержать оба указанных числа. 23. Сколько существует различных наборов значений логических переменных  x1, x2, ... x6,  y1, y2, ... y6, которые удовлетворяют всем перечисленным ниже условиям?   ((x1 ≡ y1) → (x2 ≡ y2)) /\ (x1 → y1) = 1 ((x2 ≡ y2) → (x3 ≡ y3)) /\ (x2 → y2) = 1 … ((x5 ≡ y5)  x6 → y6 = 1   Часть 2  (→ x6 ≡ y6)) /\ (x5 → y5) = 1 24. На обработку поступает натуральное число, не превышающее 109. Нужно написать  программу, которая выводит на экран максимальную цифру числа, кратную 5. Если цифр,  кратных 5, в числе нет, требуется на экран вывести «NO». Программист написал  программу неправильно.  Напоминание: 0 делится на любое натуральное число. var N,digit,maxDigit: longint; begin   readln(N);   maxDigit := 0;   while N > 0 do   begin     digit := N mod 10;     if digit mod 5 = 0 then       if digit > maxDigit then         maxDigit := digit;     N := N div 10;   end;   if maxDigit > 0 then     writeln(maxDigit)   else     writeln('NO') end. Последовательно выполните следующее. 1. Напишите, что выведет эта программа при вводе числа 108. 2. Приведите пример такого трёхзначного числа, при вводе которого программа выдаёт  верный ответ. 3. Найдите все ошибки в этой программе (их может быть одна или несколько). Известно,  что каждая ошибка затрагивает только одну строку  и может быть исправлена без изменения других строк.  ФИПИ 2018 ЕГЭ 2018 ФИПИ 2018 ЕГЭ 2018 25. Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые  значения от –10 000 до 10 000 включительно. Опишите  на одном из языков  программирования алгоритм, позволяющий найти и вывести  сумму элементов массива,  которые НЕ делятся на 5 (наличие хотя бы одного такого элемента гарантируется). Исходные данные объявлены так, как показано ниже на примерах для некоторых языков  программирования и естественного языка. Запрещается использовать переменные, не  описанные ниже, но разрешается  не использовать некоторые из описанных переменных. Const     N = 20; Var     a: array [1..N] of longint;     i, j, k: longint; begin     for i := 1 to N do         readln(a[i]);     ...   end. 26.Два игрока, Петя и Ваня, играют в следующую игру. Дан набор слов, составленных из  букв русского алфавита, при этом ни одно из заданных слов не является началом другого.  Слова в этой игре – это просто цепочки букв, они не обязаны быть осмысленными словами  русского языка. Игра состоит в том, что игроки составляют слово из набора, приписывая  по очереди буквы к концу составляемого слова, т.е. справа. При этом каждое  промежуточное слово должно быть началом одного из заданных слов. Выигрывает тот, кто  получит одно из заданных слов целиком. Первый ход делает Петя, т.е. Петя пишет первую  букву составляемого слова. Пример. Заданный набор слов: {АНТАРКТИДА, АНТРАЦИТ, АБАРА, АБАЖУР, БББ,  БАОБАБ, БАР}. Первым ходом Петя пишет Б (он мог написать Б или А). Ваня в ответ дописывает А и получает БА (он мог ещё получить ББ). Вторым ходом Петя получает БАР и выигрывает. В заданиях используются следующие понятия. Стратегия игрока – это правило,  указывающее игроку ход, который он должен сделать. Описать стратегию игрока – значит  описать, какой ход он должен сделать  в любой ситуации, которая ему может встретиться при различной игре противника.  Стратегия игрока называется выигрышной, если игрок выигрывает в любой партии,  разыгранной в соответствии с этой стратегией, как бы ни играл противник. Множество всех партий, которые могут получиться при данной стратегии, представляется  в виде дерева, это дерево называется деревом всех партий для заданной стратегии. В  узлах дерева – позиции игры;  на рёбрах – ходы, которые переводят одну позицию в другую; корень дерева – начальная  позиция игры. Дерево всех партий для данной стратегии можно описать с помощью  рисунка или таблицы. Задание 1. а) Укажите, у кого есть выигрышная стратегия при исходном наборе слов  {АБВГДАБВГДХ, ДГВБАДГВБА}. Опишите эту стратегию. Сколько различных партий  возможно при этой стратегии? Для каждой возможной партии укажите, какое слово будет  написано в конце партии. б) Укажите, у кого есть выигрышная стратегия при исходном наборе слов {ТРИТРИ…ТРИ, РИТАРИТА…РИТА} (в первом слове ТРИ повторено  ФИПИ 2018 ЕГЭ 2018 33 раза, т.е. его длина 99 букв; во втором слове РИТА повторено 44 раза,  т.е. его длина 176 букв). Опишите эту стратегию. Задание 2. В задании 1а поменяйте местами две буквы в более коротком слове так, чтобы  теперь выигрышная стратегия была у другого игрока. Напишите полученный набор слов;  опишите выигрышную стратегию. Сколько различных партий возможно при этой  стратегии? Для каждой возможной партии укажите, какое слово будет написано в конце  партии. Задание 3. Рассмотрим набор слов {СОЛНЦЕ, СОВА, СОВЕТ, ПРОСО, ПРОХОР,  ПРОИЗВОДНАЯ}. У кого из игроков есть выигрышная стратегия для этого набора?  Приведите в виде рисунка или таблицы дерево всех партий, возможных при этой стратегии. 27. На вход программы поступает последовательность из N целых положительных чисел,  все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом,  порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 14. Описание входных и выходных данных В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из  последующих N строк записано одно целое положительное число, не превышающее 10 000. В качестве результата программа должна напечатать одно число: количество пар, в  которых произведение элементов кратно 14. Пример входных данных: 4 2 6 7 21 Пример выходных данных для приведённого выше примера входных данных: 4 Пояснение. Из четырёх заданных чисел можно составить 6 попарных произведений: 2∙6,  2∙7, 2∙21, 6∙7, 6∙21, 7∙21 (результаты: 12, 14, 42, 42, 126, 147). Из них на 14 делятся 4  произведения (2∙7=14; 2∙21=42; 6∙7=42; 6∙21=126). ФИПИ 2018