В данном разделе представлены типовые задания, которые могут быть на экзамене (ЕГЭ). |
Основой послужили демонстрационные версии ЕГЭ по информатике, открытый банк заданий, представленные на сайте "Федерального института педагогических измерений" (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 балла. |
Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). |
Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок. |
Перед текстом программы обязательно кратко опишите алгоритм решения. |
Укажите использованный язык программирования и его версию. |
Ответы
|
 |