Библиотечка СтатГрад. Подготовка к ЕГЭ ДИАГНОСТИЧЕСКИЕ РАБОТЫ ЕГЭ ИНФОРМАТИКА М.А. РОЙТБЕРГ, Я.Н. ЗАЙДЕЛЬМАН ЕГЭ 2017 ФГОС

2 Государственное автономное образовательное учреждение дополнительного профессионального образования города Москвы «Центр педагогического мастерства» М. А. Ройтберг, Я. Н. Зайдельман Информатика и ИКТ Подготовка к ЕГЭ в 2017 году Диагностические работы Материалы книги соответствуют Федеральному государственному образовательному стандарту (ФГОС) Москва Издательство МЦНМО 2017

3 УДК 373:51 ББК Р65 Р65 Ройтберг М. А., Зайдельман Я. Н. Информатика и ИКТ. Подготовка к ЕГЭ в 2017 году. Диагностические работы. М.: МЦНМО, ISBN Данное пособие предназначено для отработки практических умений и навыков учащихся при подготовке к экзамену по информатике в 11 классе в формате ЕГЭ. Оно содержит варианты диагностических работ по информатике, содержание которых соответствует контрольно-измерительным материалам, разработанным Федеральным институтом педагогических измерений для проведения единого государственного экзамена. В книгу входят также ответы к заданиям и критерии проверки и оценивания выполнения заданий с развёрнутым ответом. Авторы пособия являются разработчиками тренировочных и диагностических работ для системы СтатГрад ( Материалы книги рекомендованы учителям и методистам для выявления уровня и качества подготовки учащихся по предмету, определения степени их готовности к единому государственному экзамену. Издание соответствует Федеральному государственному образовательному стандарту (ФГОС). ББК Оригинал-макет издания подготовлен в ГАОУ ДПО ЦПМ. Приказом 729 Министерства образования и науки Российской Федерации Московский центр непрерывного математического образования включён в перечень организаций, осуществляющих издание учебных пособий, допущенных к использованию в образовательном процессе. Учебно-методическое издание Михаил Абрамович Ройтберг, Яков Наумович Зайдельман ИНФОРМАТИКА И ИКТ. ПОДГОТОВКА К ЕГЭ В 2017 ГОДУ. ДИАГНОСТИЧЕСКИЕ РАБОТЫ Подписано в печать г. Формат / 16. Бумага офсетная. Печать офсетная. Тираж 3000 экз. Заказ. Издательство Московского центра непрерывного математического образования , Москва, Большой Власьевский пер., д. 11. Тел. (499) Отпечатано в ООО «Принт Сервис Групп» , Москва, ул. Борисовская, д. 14. Книги издательства МЦНМО можно приобрести в магазине «Математическая книга», Москва, Большой Власьевский пер., д. 11. Тел. (495) ISBN Ройтберг М. А., Зайдельман Я. Н., МЦНМО, 2017.

4 Предисловие СтатГрад это всероссийский интернет-проект, созданный для того, чтобы обеспечить каждое образовательное учреждение качественными дидактическими и методическими материалами. Основные направления деятельности СтатГрада система диагностики образовательных достижений учащихся, методическая поддержка систем внутришкольного контроля, учебнометодические материалы для подготовки учащихся к ЕГЭ и ОГЭ. СтатГрад предоставляет методические материалы по всем ведущим дисциплинам школьной программы по математике, физике, биологии, русскому языку, литературе, истории, обществознанию, химии, информатике, географии, иностранным языкам. Использование на уроках и при самостоятельной работе тренировочных и диагностических работ в формате ЕГЭ и ОГЭ, диагностических работ для 5 11 классов позволит учителям выявить пробелы в знаниях учащихся, а учащимся подготовиться к государственным экзаменам, заранее попробовать свои силы. Авторы и эксперты СтатГрада специалисты высокого класса, кандидаты и доктора наук, авторы учебной литературы для средней и высшей школы. В настоящее время СтатГрад сотрудничает более чем с образовательных организаций России. Настоящий сборник содержит диагностические материалы, разработанные специалистами СтатГрада для подготовки учащихся выпускных классов основной школы к ЕГЭ по информатике и ИКТ. Материалы соответствуют нормативным документам ФИПИ 2016 года. 3

5 Инструкция по выполнению работы Работа состоит из двух частей, включающих в себя 27 заданий. Часть 1 содержит 23 задания с кратким ответом. Часть 2 содержит 4 задания с развёрнутым ответом. На выполнение работы отводится 3 часа 55 минут (235 минут). Ответы к заданиям 1 23 записываются в виде числа, последовательности букв или цифр. Для выполнения заданий Вам необходимо написать развёрнутый ответ в произвольной форме. При выполнении заданий можно пользоваться черновиком. Записи в черновике не учитываются при оценивании работы. Баллы, полученные Вами за выполненные задания, суммируются. Постарайтесь выполнить как можно больше заданий и набрать наибольшее количество баллов. Желаем успеха! 4

6 В заданиях используются следующие соглашения 1. Обозначения для логических связок (операций): a) отрицание (инверсия, логическое НЕ) обозначается (например, А); b) конъюнкция (логическое умножение, логическое И) обозначается /\ (например, А /\ В) либо & (например, А & В); c) дизъюнкция (логическое сложение, логическое ИЛИ) обозначается \/ (например, А \/ В) либо (например, А В); d) следование (импликация) обозначается (например, А В); e) тождество обозначается (например, A B). Выражение A B истинно тогда и только тогда, когда значения A и B совпадают (либо они оба истинны, либо они оба ложны); f) символ 1 используется для обозначения истины (истинного высказывания); символ 0 для обозначения лжи (ложного высказывания). 2. Два логических выражения, содержащие переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А В и ( А) \/ В равносильны, а А \/ В и А /\ В неравносильны (значения выражений разные, например, при А = 1, В = 0). 3. Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), тождество. Таким образом, А /\ В \/ С /\ D означает то же, что и (( А) /\ В) \/ (С /\ D). Возможна запись А /\ В /\ С вместо (А /\ В) /\ С. То же относится и к дизъюнкции: возможна запись А \/ В \/ С вместо (А \/ В) \/ С. 4. Обозначения Мбайт и Кбайт используются в традиционном для информатики смысле как обозначения единиц измерения, чьё соотношение с единицей «байт» выражается степенью двойки. 5

7 Вариант 1 Часть 1 Ответами к заданиям 1 23 являются число, последовательность букв или цифр. Запишите ответы в указанном месте без пробелов, запятых и других дополнительных символов. 1 Сколько единиц в двоичной записи шестнадцатеричного числа ВЕС2 16? 2 Логическая функция F задаётся выражением: ( x /\ y /\ z) \/ ( x /\ y /\ z) \/ ( x /\ y /\ z). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z. Переменная 1 Переменная 2 Переменная 3 Функция. F В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу, затем буква, соответствующая второму столбцу, и т. д.) Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Пример. Пусть задано выражение x y, зависящее от двух переменных x и y, и таблица истинности: Переменная 1 Переменная 2 Функция. F Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx. 6

8 3 Вариант 1 На рисунке схема дорог Н-ского района изображена в виде графа, а в таблице содержатся сведения о длине этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта Г в пункт Е. В ответе запишите целое число. 4 Во фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите, сколько всего внуков и внучек Павленко А.К. упомянуты в таблице 1. Таблица 1 Таблица 2 ID Фамилия_И.О. Пол ID_Родителя ID_Ребёнка 2146 Кривич Л.П. Ж Павленко А.К. М Хитрук П.А. М Кривич А.А. М Павленко Е.А. Ж Сокол Н.А. Ж Павленко И.А. М Павленко Т.Х. Ж Хитрук А.П М Павленко П.И. М Павленко Т.И. Ж Симонян А.А. Ж Сокол В.А. Ж Биба С.А. Ж

9 5 Вариант 1 По каналу связи передаются сообщения, содержащие только пять букв: A, B, С, D, E. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв A, B, C используются такие кодовые слова: A 111, B 0, C 100. Укажите кратчайшее кодовое слово для буквы D, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением. 6 Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам. 1. Перемножаются первая и вторая, а также вторая и третья цифры. 2. Полученные два числа записываются друг за другом в порядке неубывания без разделителей. Пример. Исходное число: 631. Произведения: 6 3 = 18; 3 1 = 3. Результат: 318. Укажите наибольшее число, при обработке которого автомат выдаёт результат Дан фрагмент электронной таблицы. Из ячейки D3 в ячейку E4 была скопирована формула. При копировании адреса ячеек в формуле автоматически изменились. Каким стало числовое значение формулы в ячейке E4? А В С D E = $B2 + B$ Примечание. Знак $ обозначает абсолютную адресацию. 8

10 8 Вариант 1 Запишите число, которое будет напечатано в результате выполнения следующей программы. Для Вашего удобства программа представлена на пяти языках программирования. Бейсик DIM S, N AS INTEGER S = 0 N = 0 WHILE 2*S < 111 S = S + 8 N = N + 2 WEND PRINT N Алгоритмический язык алг нач цел s, n s := 0 n := 0 нц пока 2*s < 111 s := s + 8 n := n + 2 кц вывод n кон Python s = 0 n = 0 while 2*s < 111: s = s + 8 n = n + 2 print(n) Паскаль var s, n: integer; begin s := 0; n := 0; while 2*s < 111 do begin s := s + 8; n := n + 2 end; writeln(n) end. Си #include <stdio.h> int main() < int s = 0, n = 0; while (2*s < 111) < s = s + 8; n = n + 2; printf("%d\n", n); return 0; 9

11 9 Вариант 1 Какой минимальный объём памяти (в Кбайтах) нужно зарезервировать, чтобы можно было сохранить любое растровое изображение размером пикселей при условии, что в изображении могут использоваться 256 различных цветов? В ответе запишите только целое число, единицу измерения писать не нужно. 10 Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует 5-буквенные слова, в которых есть только буквы A, B, C, X, причём буква X появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь? 11 Ниже на пяти языках программирования записаны рекурсивные функции F и G. Бейсик FUNCTION F(n) IF n > 2 THEN F = F(n - 1) + G(n - 2) ELSE F = 1 END IF END FUNCTION FUNCTION G(n) IF n > 2 THEN G = G(n - 1) + F(n - 2) ELSE G = 1 END IF END FUNCTION Паскаль function F(n: integer): integer; begin if n > 2 then F := F(n - 1) + G(n - 2) else F := 1; end; function G(n: integer): integer; begin if n > 2 then G := G(n - 1) + F(n - 2) else G := 1; end; 10

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

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

15 15 Вариант 1 На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Т? 16 Значение арифметического выражения: записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи? 17 В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ, а для обозначения логической операции «И» символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. Найдено страниц Запрос (в тысячах) Лондон & Манчестер 270 Лондон & (Ливерпуль Манчестер) 470 Лондон & Ливерпуль 355 Какое количество страниц (в тысячах) будет найдено по запросу Лондон & Ливерпуль & Манчестер? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов. 14

16 18 Вариант 1 Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Например, 14 & 5 = & = = 4. Для какого наименьшего неотрицательного целого числа А формула x & 29 0 (x & 17 = 0 x & А 0) тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной х)? 19 В программе используется одномерный целочисленный массив A с индексами от 0 до 9. Значения элементов равны 6, 7, 3, 8, 5, 1, 2, 0, 9, 4 соответственно, т. е. A[0] = 6, A[1] = 7 и т. д. Определите значение переменной c после выполнения следующего фрагмента этой программы, записанного ниже на пяти языках программирования. Бейсик c = 0 FOR i = 1 TO 9 IF A(i) < A(0) THEN c = c + 1 t = A(i) A(i) = A(0) A(0) = t END IF NEXT i Алгоритмический язык c := 0 нц для i от 1 до 9 если 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; Python 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 to 9 do if A[i] < A[0] then begin c := c + 1; t := A[i]; A[i] := A[0]; A[0] := t; end; 15

17 20 Вариант 1 Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает число M. Известно, что x > 100. Укажите наименьшее такое (т. е. большее 100) число x, при вводе которого алгоритм печатает 15. Бейсик DIM X, L, M AS INTEGER INPUT X L = X 30 M = X + 30 WHILE L <> M IF L > M THEN L = L M ELSE M = M L END IF WEND PRINT M Алгоритмический язык алг нач цел x, L, M ввод x L := x 30 M := x+30 нц пока L <> M если L > M то L := L M иначе M := M L все кц вывод M кон Python x = int(input()) L = x 30 M = x+30 while L!= M: if L > M: L = L M else: M = M L print(m) Паскаль var x, L, M: integer; begin readln(x); L := x 30; M := x+30; while L <> M do begin if L > M then L := L M else M := M L; end; writeln(m); end. 16

20 22 Вариант 1 Исполнитель Май16 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Май16 это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 31 и при этом траектория вычислений содержит число 15 и не содержит числа 22? Траектория вычислений программы это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, Сколько существует различных наборов значений логических переменных x 1, x 2, x 3, x 4, x 5, x 6, y 1, y 2, y 3, y 4, y 5, y 6, которые удовлетворяют всем перечисленным ниже условиям? (x 1 x 2 ) /\ (x 2 x 3 ) /\ (x 3 x 4 ) /\ (x 4 x 5 ) /\ (x 5 x 6 ) = 1 (y 1 y 2 ) /\ (y 2 y 3 ) /\ (y 3 y 4 ) /\ (y 4 y 5 ) /\ (y 5 y 6 ) = 1 x 1 y 1 = 1 В ответе не нужно перечислять все различные наборы значений переменных x 1, x 2, x 3, x 4, x 5, x 6, y 1, y 2, y 3, y 4, y 5, y 6, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов. 19

21 Вариант 1 Часть 2 Для записи ответов на задания этой части (24 27) используйте отдельный лист. Запишите сначала номер задания (24, 25 и т. д.), а затем полное решение. Ответы записывайте чётко и разборчиво. 24 Дано целое положительное число N. Необходимо определить наименьшее целое число K, для которого выполняется неравенство: K N. Для решения этой задачи ученик написал программу, но, к сожалению, его программа неправильная. Ниже эта программа для Вашего удобства приведена на пяти языках программирования. Бейсик DIM N, K AS INTEGER INPUT N K = 1 WHILE N >= 0 K = K + 1 N = N - K WEND PRINT K END Алгоритмический язык алг нач цел n, k ввод n k := 1 нц пока n>=0 k := k + 1 n := n - k кц вывод k кон Python n = int(input()) k = 1 while n>=0: k = k + 1 n = n - k print(k) Паскаль var n, k: integer; begin read(n); k := 1; while n>=0 do begin k := k + 1; n := n - k; end; writeln(k) end. 20

24 26 Вариант 1 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 20 камней, а в другой 7 камней; такую позицию в игре будем обозначать (20, 7). Тогда за один ход можно получить любую из четырёх позиций: (21, 7), (40, 7), (20, 8), (20, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 97. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, что в кучах всего будет 97 камней или больше. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, в начальных позициях (10, 44) и (11, 43) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче. Задание 1. Для каждой из начальных позиций (10, 43), (12, 42) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Задание 2. Для каждой из начальных позиций (10, 42), (11, 42), (12, 41) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Задание 3. Для начальной позиции (11, 41) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной Вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы. 23

25 27 Вариант 1 На плоскости задано множество точек с целочисленными координатами. Необходимо найти максимально возможную площадь невырожденного (т. е., имеющего ненулевую площадь) треугольника, одна вершина которого расположена в начале координат, а две другие лежат на осях координат и при этом принадлежат заданному множеству. Если такого треугольника не существует, необходимо вывести соответствующее сообщение. Напишите эффективную по времени и по используемой памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз. Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает 1 килобайт. Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию. Входные данные В первой строке задаётся N количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа координаты очередной точки. Пример входных данных: Выходные данные Если искомый треугольник существует, программа должна напечатать одно число: максимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать сообщение: «Треугольник не существует». Пример выходных данных для приведённого выше примера входных данных: 24 24

26 Вариант 2 Часть 1 Ответами к заданиям 1 23 являются число, последовательность букв или цифр. Запишите ответы в указанном месте без пробелов, запятых и других дополнительных символов. 1 Сколько единиц в двоичной записи шестнадцатеричного числа ВЕС3 16? 2 Логическая функция F задаётся выражением: ( x /\ y /\ z) \/ ( x /\ y /\ z) \/ ( x /\ y /\ z). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z. Переменная 1 Переменная 2 Переменная 3 Функция. F В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу, затем буква, соответствующая второму столбцу, и т. д.) Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Пример. Пусть задано выражение x y, зависящее от двух переменных x и y, и таблица истинности: Переменная 1 Переменная 2 Функция. F Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx. 25

27 3 Вариант 2 На рисунке схема дорог Н-ского района изображена в виде графа, а в таблице содержатся сведения о длине этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта В в пункт Г. В ответе запишите целое число. 4 Для групповых операций с файлами используются маски имён файлов. Маска представляет собой последовательность букв, цифр и прочих допустимых в именах файлов символов, среди которых также могут встречаться следующие символы: Символ «?» (вопросительный знак) означает ровно один произвольный символ. Символ «*» (звёздочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность. В каталоге находятся 6 файлов: mustard.map mustard.mp3 catarsis.mp4 vitarcon.mp4 taras.mp3 star.mp3 Ниже представлено восемь масок. Сколько среди них таких, которым соответствуют ровно четыре файла из данного каталога? *tar*.mp* *?tar?*.mp??*tar*.mp?* *t*r*?.m?p*. *. mp*. *. m* *a*.*a* *s*.mp* 26

28 5 Вариант 2 По каналу связи передаются сообщения, содержащие только пять букв: A, B, С, D, E. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв A, B, C используются такие кодовые слова: A 1, B 010, C 000. Укажите кратчайшее кодовое слово для буквы E, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением. 6 Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам. 1. Перемножаются первая и вторая, а также вторая и третья цифры. 2. Полученные два числа записываются друг за другом в порядке неубывания без разделителей. Пример. Исходное число: 631. Произведения: 6 3 = 18; 3 1 = 3. Результат: 318. Укажите наименьшее число, при обработке которого автомат выдаёт результат Дан фрагмент электронной таблицы. Из ячейки D3 в ячейку E4 была скопирована формула. При копировании адреса ячеек в формуле автоматически изменились. Каким стало числовое значение формулы в ячейке E4? А В С D E = $B1 + B$ Примечание. Знак $ обозначает абсолютную адресацию. 27

30 10 Вариант 2 Алексей составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Алексей использует 5-буквенные слова, в которых есть только буквы A, B, C, X, причём буква X может появиться на первом месте или не появиться вовсе. Сколько различных кодовых слов может использовать Алексей? 11 Ниже на пяти языках программирования записаны рекурсивные функции F и G. Бейсик FUNCTION F(n) IF n > 2 THEN F = F(n - 1) + G(n - 2) ELSE F = 1 END IF END FUNCTION FUNCTION G(n) IF n > 2 THEN G = G(n - 1) + F(n - 2) ELSE G = 1 END IF END FUNCTION Си int F(int n) < if (n > 2) return F(n-1) + G(n-2); else return 1; int G(int n) < if (n > 2) return G(n-1) + F(n-2); else return 1; Паскаль function F(n: integer): integer; begin if n > 2 then F := F(n - 1) + G(n - 2) else F := 1; end; function G(n: integer): integer; begin if n > 2 then G := G(n - 1) + F(n - 2) else G := 1; end; Алгоритмический язык алг цел F(цел n) нач если n > 2 то знач := F(n - 1)+G(n - 2) иначе знач := 1 все кон алг цел G(цел n) нач если n > 2 то знач := G(n - 1) + F(n - 2) иначе знач := 1 все кон 29

31 Вариант 2 Python def F(n): if n > 2: return F(n-1)+ G(n-2) else: return 1 def G(n): if n > 2: return G(n-1) + F(n-2) else: return 1 Чему будет равно значение, вычисленное при выполнении вызова F(8)? В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая к адресу самого узла в этой сети. При этом в двоичном представлении маски сначала (в старших разрядах) стоят единицы, а затем с некоторого разряда нули. Обычно маска записывается по тем же правилам, что и IPадрес, в виде четырёх байт, причём каждый байт записывается в виде десятичного числа. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске. Например, если IP-адрес узла равен , а маска равна , то адрес сети равен Для узла с IP-адресом адрес сети равен Чему равно наибольшее возможное значение третьего слева байта маски? Ответ запишите в виде десятичного числа. При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 8-символьного набора: А, В, C, D, Е, F, G, H. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байтов. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством битов. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байтов; это число одно и то же для всех пользователей. Для хранения сведений о 20 пользователях потребовалось 300 байт. Сколько байтов выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число количество байтов. 30

32 14 Вариант 2 Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. А) заменить (v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку в строку Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку. Б) нашлось (v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется. Цикл ПОКА условие последовательность команд КОНЕЦ ПОКА выполняется, пока условие истинно. В конструкции ЕСЛИ условие ТО команда1 ИНАЧЕ команда2 КОНЕЦ ЕСЛИ выполняется команда1 (если условие истинно) или команда2 (если условие ложно). Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 127 идущих подряд цифр «9»? В ответе запишите полученную строку. НАЧАЛО ПОКА нашлось (333) ИЛИ нашлось (999) ЕСЛИ нашлось (333) ТО заменить (333, 9) ИНАЧЕ заменить (999, 3) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ 31

33 15 Вариант 2 На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Т? 16 Значение арифметического выражения: записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи? 17 В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ, а для обозначения логической операции «И» символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. Запрос Найдено страниц (в тысячах) Лондон & Манчестер 270 Лондон & (Ливерпуль Манчестер) 470 Лондон & Ливерпуль 367 Какое количество страниц (в тысячах) будет найдено по запросу Лондон & Ливерпуль & Манчестер? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов. 32

34 18 Вариант 2 Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Например, 14 & 5 = & = = 4. Для какого наименьшего неотрицательного целого числа А формула x & 29 0 (x & 12 = 0 x & А 0) тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной х)? 19 В программе используется одномерный целочисленный массив A с индексами от 0 до 9. Значения элементов равны 6, 7, 5, 8, 3, 2, 0, 1, 9, 4 соответственно, т. е. A[0] = 6, A[1] = 7 и т. д. Определите значение переменной c после выполнения следующего фрагмента этой программы, записанного ниже на пяти языках программирования. Бейсик c = 0 FOR i = 1 TO 9 IF A(i) < A(0) THEN c = c + 1 t = A(i) A(i) = A(0) A(0) = t END IF NEXT i Алгоритмический язык c := 0 нц для i от 1 до 9 если A[i] < A[0] то c := c + 1 t := A[i] A[i] := A[0] A[0] := t все кц Python 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 to 9 do if A[i] < A[0] then begin c := c + 1; t := A[i]; A[i] := A[0]; A[0] := t; end; 33

38 22 Вариант 2 Исполнитель Май16 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Май16 это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 33 и при этом траектория вычислений содержит число 16 и не содержит числа 30? Траектория вычислений программы это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, Сколько существует различных наборов значений логических переменных x 1, x 2, x 3, x 4, x 5, x 6, y 1, y 2, y 3, y 4, y 5, y 6, которые удовлетворяют всем перечисленным ниже условиям? (x 1 x 2 ) /\ (x 2 x 3 ) /\ (x 3 x 4 ) /\ (x 4 x 5 ) /\ (x 5 x 6 ) = 1 (y 1 y 2 ) /\ (y 2 y 3 ) /\ (y 3 y 4 ) /\ (y 4 y 5 ) /\ (y 5 y 6 ) = 1 y 1 x 1 = 1 В ответе не нужно перечислять все различные наборы значений переменных x 1, x 2, x 3, x 4, x 5, x 6, y 1, y 2, y 3, y 4, y 5, y 6, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов. 37

39 Вариант 2 Часть 2 Для записи ответов на задания этой части (24 27) используйте отдельный лист. Запишите сначала номер задания (24, 25 и т. д.), а затем полное решение. Ответы записывайте чётко и разборчиво. 24 Дано целое положительное число N. Необходимо определить наименьшее целое число K, для которого выполняется неравенство: K > N. Для решения этой задачи ученик написал программу, но, к сожалению, его программа неправильная. Ниже эта программа для Вашего удобства приведена на пяти языках программирования. Бейсик DIM N, K AS INTEGER INPUT N K = 1 WHILE N > 0 N = N - K K = K + 1 WEND PRINT K END Алгоритмический язык алг нач цел n, k ввод n k := 1 нц пока n>0 n := n - k k := k + 1 кц вывод k кон Python n = int(input()) k = 1 while n>0: n = n - k k = k + 1 print(k) Паскаль var n, k: integer; begin read(n); k := 1; while n>0 do begin n := n - k; k := k + 1; end; writeln(k) end. 38

42 26 Вариант 2 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 20 камней, а в другой 7 камней; такую позицию в игре будем обозначать (20, 7). Тогда за один ход можно получить любую из четырёх позиций: (21, 7), (40, 7), (20, 8), (20, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, что в кучах всего будет 77 камней или больше. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (10, 34), (11, 33) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче. Задание 1. Для каждой из начальных позиций (10, 33), (12, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Задание 2. Для каждой из начальных позиций (10, 32), (11, 32), (12, 31) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Задание 3. Для начальной позиции (11, 31) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной Вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы. 41

43 27 Вариант 2 На плоскости задано множество точек с целочисленными координатами. Необходимо найти минимально возможную площадь невырожденного (т. е. имеющего ненулевую площадь) треугольника, одна вершина которого расположена в начале координат, а две другие лежат на осях координат и при этом принадлежат заданному множеству. Если такого треугольника не существует, необходимо вывести соответствующее сообщение. Напишите эффективную по времени и по используемой памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз. Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает 1 килобайт. Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию. Входные данные В первой строке задаётся N количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа координаты очередной точки. Пример входных данных: Выходные данные Если искомый треугольник существует, программа должна напечатать одно число: минимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать сообщение: «Треугольник не существует». Пример выходных данных для приведённого выше примера входных данных: 24 42

44 Вариант 3 Часть 1 Ответами к заданиям 1 23 являются число, последовательность букв или цифр. Запишите ответы в указанном месте без пробелов, запятых и других дополнительных символов. 1 Вычислите: Ответ запишите в десятичной системе счисления. В ответе запишите только число, основание системы счисления писать не нужно. 2 Логическая функция F задаётся выражением ( x /\ y /\ z) \/ ( x /\ z). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z. Переменная 1 Переменная 2 Переменная 3 Функция. F В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу, затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Пример. Пусть задано выражение x y, зависящее от двух переменных x и y, и таблица истинности: Переменная 1 Переменная 2 Функция. F Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать yx. 43