| В данном разделе представлены типовые задания, которые могут быть на экзамене (ЕГЭ). |
| Основой послужили демонстрационные версии ЕГЭ по информатике, открытый банк заданий, представленные на сайте "Федерального института педагогических измерений" (www.fipi.ru). |
| На занятиях у репетитора каждый тип задания будет представлен множеством различных конкретных задач и способами их решения. |
| На решение 27 заданий дается 3часа 55 мин. Это немного. В среднем, на каждое задание ученик должен потратить 8-9 мин. |
| Конечно, есть задания, которые можно и быстрее решить, но есть и сложные задания, на которые уйдет 20-30 мин. А на решение 27ой задачи по варианту Б может потребоваться даже минут 40. |
| Поэтому, от ученика требуется не просто решить задачу, но решить ее быстро, в спортивном темпе и без ошибок. |
| От репетитора по информатике требуется не просто показать как решаются подобные задачи, а предложить методы быстрого решения задач. |
Задание 1
|
| Сколько существует целых чисел x, для которых выполняется неравенство |
 |
| В ответе укажите только количество чисел, сами числа писать не нужно. |
Задание 2
|
| Логическая функция F задаётся выражением ¬x \/ y \/ (¬z /\ w). |
| На рисунке приведён фрагмент таблицы истинности функции F, |
| содержащий все наборы аргументов, при которых функция F ложна. |
| Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z. |
 |
| В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая первому столбцу; затем – буква, соответствующая второму столбцу, и т.д.). |
| Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. |
| Пример. Если бы функция была задана выражением ¬x\/y, зависящим от двух переменных: x и y, и был приведён фрагмент её таблицы истинности, содержащий все наборы аргументов, при которых функция истинна. |
Задание 3
|
| На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). |
 |
| Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта А в пункт Г. В ответе запишите целое число – так, как оно указано в таблице. |
Задание 4
|
| Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. |
| Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных, у скольких детей на момент их рождения матерям было больше 22 полных лет. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц. |
 |
Задание 5
|
| По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. |
| Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова. |
 |
| Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением. |
| Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений. |
Задание 6
|
| На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. |
| 1) Строится двоичная запись числа N. |
| 2) К этой записи дописываются справа ещё два разряда по следующему правилу: |
| а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; |
| б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2. |
| Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. |
| Укажите минимальное число R, которое превышает число 83 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления. |
Задание 7
|
| Дан фрагмент электронной таблицы. Из ячейки B3 в ячейку A4 была скопирована формула. |
| При копировании адреса ячеек в формуле автоматически изменились. Каким стало числовое значение формулы в ячейке A4? |
 |
Задание 8
|
| Запишите число, которое будет напечатано в результате выполнения следующей программы. |
| Для Вашего удобства программа представлена на пяти языках программирования. |
 |
Задание 9
|
| Автоматическая фотокамера производит растровые изображения размером 640×480 пикселей. |
| При этом объём файла с изображением не может превышать 320 Кбайт, упаковка данных не производится. |
| Какое максимальное количество цветов можно использовать в палитре? |
Задание 10
|
| Все 4-буквенные слова, составленные из букв Д, Е, К, О, Р, записаны в алфавитном порядке и пронумерованы, начиная с 1. |
| Ниже приведено начало списка. |
| 1. ДДДД |
| 2. ДДДЕ |
| 3. ДДДК |
| 4. ДДДО |
| 5. ДДДР |
| 6. ДДЕД |
| … |
| Под каким номером в списке идёт первое слово, которое начинается с буквы K? |
Задание 11
|
| Ниже на пяти языках программирования записан рекурсивный алгоритм F. |
 |
| Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(9). Числа должны быть записаны в том же порядке, в котором они выводятся на экран. |
Задание 12
|
| В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в этой сети. |
| Обычно маска записывается по тем же правилам, что и IP-адрес, – в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. При этом в маске сначала(в старших разрядах) стоят единицы, а затем с некоторого разряда – нули. |
| Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске. |
| Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0. |
| Для узла с IP-адресом 57.179.208.27 адрес сети равен 57.179.192.0. |
| Каково наибольшее возможное количество единиц в разрядах маски? |
Задание 13
|
| При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 10 символов. |
| В качестве символов используют прописные буквы латинского алфавита, т.е. 26 различных символов. |
| В базе данных для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. |
| При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. |
| Определите объём памяти (в байтах), необходимый для хранения данных о 50 пользователях. В ответе запишите только целое число – количество байт. |
Задание 14
|
| Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. |
| Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. |
| Эта команда перемещает Чертёжника из точки с координатами (x,y) в точку с координатами (x + a, y + b). |
| Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, −3) переместит Чертёжника в точку (6, −1). |
| Цикл |
| ПОВТОРИ число РАЗ |
| последовательность команд |
| КОНЕЦ ПОВТОРИ |
| означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным). |
| Чертёжнику был дан для исполнения следующий алгоритм (число повторений и величины смещения в первой из повторяемых команд неизвестны): |
| НАЧАЛО |
| сместиться на (4, 6) |
| ПОВТОРИ …РАЗ |
| сместиться на (…, …) |
| сместиться на (4, -6) |
| КОНЕЦ ПОВТОРИ |
| сместиться на (-28, -22) |
| КОНЕЦ |
| В результате выполнения этого алгоритма Чертёжник возвращается в исходную точку. |
| Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ … РАЗ»? |
Задание 15
|
| На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. |
| По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. |
| Сколько существует различных путей из города А в город М, проходящих через город Ж? |
 |
Задание 16
|
 |
Задание 17
|
| В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для обозначения логической операции «И» – символ «&». |
| В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. |
 |
| Какое количество страниц (в сотнях тысяч) будет найдено по запросу |
| Бабочка & Гусеница? |
| Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов. |
Задание 18
|
| Для какого наибольшего целого числа А формула |
| ((x ≤ 9) →(x⋅x ≤ A)) ⋀ ((y⋅y ≤ A) → (y ≤ 9)) |
| тождественно истинна, то есть принимает значение 1 при любых целых неотрицательных x и y? |
Задание 19
|
| В программе используется одномерный целочисленный массив A с индексами от 0 до 9. |
| Значения элементов равны 3, 0, 4, 6, 5, 1, 8, 2, 9, 7 соответственно, т.е. A[0] = 3, A[1] = 0 и т.д. |
| Определите значение переменной c после выполнения следующего фрагмента этой программы (записанного ниже на разных языках программирования). |
 |
Задание 20
|
| Ниже на пяти языках программирования записан алгоритм. |
| Получив на вход число x, этот алгоритм печатает два числа: L и M. |
| Укажите наименьшее число x, при вводе которого алгоритм печатает сначала 5, а потом 7. |
 |
Задание 21
|
| Напишите в ответе число, которое будет напечатано в результате выполнения следующего алгоритма. |
| Для Вашего удобства алгоритм представлен на пяти языках программирования. |
 |
Задание 22
|
| Исполнитель М17 преобразует число, записанное на экране. |
| У исполнителя есть три команды, которым присвоены номера: |
| 1. Прибавить 1 |
| 2. Прибавить 2 |
| 3. Умножить на 3 |
| Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 3. |
| Программа для исполнителя М17 – это последовательность команд. |
| Сколько существует таких программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений программы содержит числа и 10? |
| Траектория должна содержать оба указанных числа. |
| Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. |
| Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 24, 26. |
Задание 23
|
| Сколько существует различных наборов значений логических переменных x1, x2, ...x7, y1, y2, ...y7, которые удовлетворяют всем перечисленным ниже условиям? |
| (¬x1 \/ y1) → (¬x2 /\ y2) = 1 |
| (¬x2 \/ y2) → (¬x3 /\ y3) = 1 |
| … |
| (¬x6 \/ y6) → (¬x7 /\ y7) = 1 |
| В ответе не нужно перечислять все различные наборы значений переменных x1, x2, ...x7, y1, y2, ...y7, при которых выполнена данная система равенств. |
| В качестве ответа Вам нужно указать количество таких наборов. |
Задание 24
|
| На обработку поступает натуральное число, не превышающее 109. |
| Нужно написать программу, которая выводит на экран максимальную цифру числа, кратную 5. |
| Если в числе нет цифр, кратных 5, требуется на экран вывести «NO». |
| Программист написал программу неправильно. Ниже эта программа для Вашего удобства приведена на пяти языках программирования. |
 |
| Последовательно выполните следующее. |
| 1. Напишите, что выведет эта программа при вводе числа 132. |
| 2. Приведите пример такого трёхзначного числа, при вводе которого программа выдаёт верный ответ. |
| 3. Найдите все ошибки в этой программе (их может быть одна или несколько). Известно, что каждая ошибка затрагивает только одну строку и может быть исправлена без изменения других строк. Для каждой ошибки: |
| 1) выпишите строку, в которой сделана ошибка; |
| 2) укажите, как исправить ошибку, т.е. приведите правильный вариант строки. |
| Достаточно указать ошибки и способ их исправления для одного языка программирования. |
| Обратите внимание, что требуется найти ошибки в имеющейся программе, а не написать свою, возможно, использующую другой алгоритм решения. |
| Исправление ошибки должно затрагивать только строку, в которой находится ошибка. |
Задание 25
|
| Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от 0 до 10 000 включительно. |
| Опишите на одном из языков программирования алгоритм, который находит количество элементов массива, больших 100 и при этом кратных 5, а затем заменяет каждый такой элемент на число, равное найденному количеству. |
| Гарантируется, что хотя бы один такой элемент в массиве есть. |
| В качестве результата необходимо вывести измененный массив, каждый элемент массива выводится с новой строчки. |
| Например, для массива из шести элементов: 4 115 7 195 25 106 |
| программа должна вывести числа 4 2 7 2 25 106 |
| Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования. |
| Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных. |
 |
| В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия. |
| Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например Free Pascal 2.6). |
| В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на Алгоритмическом языке). |
Задание 26
|
| Два игрока, Петя и Ваня играют в следующую игру. |
| На столе в кучке лежат фишки. На лицевой стороне каждой фишки написано двузначное натуральное число, обе цифры которого находятся в диапазоне от 1 до 4. |
| Никакие две фишки не повторяются. Игра состоит в том, что игроки поочередно берут из кучки по одной фишке и выкладывают в цепочку на стол лицевой стороной вверх таким образом, что каждая новая фишка ставится правее предыдущей и ближайшие цифры соседних фишек совпадают. |
| Верхняя часть всех выложенных фишек направлена в одну сторону, то есть переворачивать фишки нельзя. Например, из фишки, на которой написано 23, нельзя сделать фишку, на которой написано 32. |
| Первый ход делает Петя, выкладывая на стол любую фишку из кучки. |
| Игра заканчивается, когда в кучке нет ни одной фишки, которую можно добавить в цепочку. |
| Тот, кто добавил в цепочку последнюю фишку, выигрывает, а его противник проигрывает. |
| Будем называть партией любую допустимую правилами последовательность ходов игроков, приводящую к завершению игры. |
| Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. |
| Описать стратегию игрока – значит указать, какую фишку он должен выставить в любой ситуации, которая ему может встретиться при различной игре противника. |
| Пример партии. |
| Пусть на столе в кучке лежат фишки: 11, 12, 13, 21, 22, 23 |
| Пусть первый ход Пети 12. |
| Ваня может поставить 21, 22 или 23. Предположим, он ставит 21. Получим цепочку 12-21. |
| Петя может поставить 11 или 13. Предположим, он ставит 11. Получим цепочку 12-21-11. |
| Ваня может поставить только фишку со значением 13. Получим цепочку 12-21-11-13. |
| Перед Петей в кучке остались только фишки 22 и 23, то есть нет фишек, которые он мог бы добавить в цепочку. Таким образом, партия закончена, Ваня выиграл. |
| Выполните следующие три задания при исходном наборе фишек в кучке |
| {12, 14, 21, 22, 24, 41, 42, 44}. |
| Задание 1. |
| а) Приведите пример самой короткой партии, возможной при данном наборе фишек. Если таких партий несколько, достаточно привести одну. |
| б) Пусть Петя первым ходом пошел 42. У кого из игроков есть выигрышная стратегия в этой ситуации? Укажите первый ход, который должен сделать выигрывающий игрок, играющий по этой стратегии. Приведите пример одной из партий, возможных при реализации выигрывающим игроком этой стратегии. |
| Задание 2. |
| Пусть Петя первым ходом пошел 44. У кого из игроков есть выигрышная стратегия, позволяющая в этой ситуации выиграть своим четвертым ходом? |
| Постройте в виде рисунка или таблицы дерево всех партий, возможных при реализации выигрывающим игроком этой стратегии. |
| На рёбрах дерева указывайте ход, в узлах – цепочку фишек, получившуюся после этого хода. |
| Задание 3. |
| Укажите хотя бы один способ убрать 2 фишки из исходного набора так, чтобы всегда выигрывал не тот игрок, который имеет выигрышную стратегию в задании 2. Приведите пример партии для набора из 6 оставшихся фишек |
Задание 27
|
| На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. |
| Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). |
| Необходимо определить количество пар, для которых произведение элементов делится на 26. |
| Описание входных и выходных данных |
| В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. |
| В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 26. |
| Пример входных данных: |
|
|
| Пример выходных данных для приведённого выше примера входных данных: |
|
|
| Пояснение. Из четырёх заданных чисел можно составить 6 попарных произведений: 2·6, 2·13, 2·39, 6·13, 6·39, 13·39 (результаты: 12, 26, 78, 78, 234, 507). Из них на 26 делятся 4 произведения (2·13=26; 2·39=78; 6·13=78; 6·39=234). |
| Требуется написать эффективную по времени и по памяти программу для решения описанной задачи. |
| Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. |
| Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N. |
| Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, – 4 балла. |
| Максимальная оценка за правильную программу, эффективную только по времени – 3 балла. |
| Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла. |
| Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). |
| Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок. |
| Перед текстом программы обязательно кратко опишите алгоритм решения. |
| Укажите использованный язык программирования и его версию. |
Ответы
|
 |
