Подготовка ребёнка к ЕГЭ по информатике. Часть семнадцатая

25.02.19

Разработка - Математика и алгоритмы

Задачи прошлых лет.

Любопытные задачи прошлых лет (2009-2018) из ЕГЭ

 

Предисловие

ЕГЭ появился в далеком 2009 году, и за то время, что прошло, претерпел значительные изменения как в структуре экзамена, так и в содержании заданий. ЕГЭ – это продукт ФИПИ, и как любой другой продукт, он эволюционирует и развивается с течением времени. В этой статье я предлагаю на примерах отследить те изменения, которые произошли в содержании заданий за десять лет. Особый приоритет будет у необычных и интересных задач.

 

Демонстрационный вариант ЕГЭ 2009 г. ИНФОРМАТИКА, 11 класс

 

A1. Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 16-битном коде Unicode, в 8-битную кодировку КОИ-8. При этом информационное сообщение уменьшилось на 480 бит. Какова длина сообщения в символах?

1) 30

2) 60

3) 120

4) 480

 

Любопытно, что раньше в демонстрационных вариантах нередко можно было встретить подобные задания, направленные на проверку знаний о различных кодировках текста. Чаще всего можно было встретить кодировки UTF-8, UTF-16, UTF-32 и КОИ-8.

Решение не представляет особой сложности. Примем количество символов в сообщении за x. Тогда изначальное сообщение имело объем 16x, а конечное – 8x. Т.к. разница между начальным и конечным – 480 бит, составим уравнение: 16x – 8x = 480 → 8x = 480 → x = 60.

 

Ответ: 60

 

А5. Определите значение переменной c после выполнения следующего фрагмента программы.

 

 Бейсик

Паскаль

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

a = 5

a = a + 6

b = – a

c = a – 2 * b

A:=5;

a:=a+6;

b:= –a;

c:=a–2*b;

a:=5

a:=a+6

b:= –a

c:=a–2*b

 

Нередко можно было встретить задания с переинициализацией пременной. Видимо, процент учеников, справлявшихся с этой нехитрой логикой был близок к 100, поэтому в экзаменах последних лет такое уже не встретить.

После второй инициализации a, переменная имеет значение 11. b соответственно равна -11. Тогда переменная c = 11 – 2*(-11) = 11 + 22 = 33.

 

Ответ: 33

 

A6. Дан фрагмент программы, обрабатывающей двумерный массив A размера n×n.

 

 Бейсик

Паскаль

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

k = 1

FOR i = 1 TO n

c = A(i,i)

A(i,i) = A(k,i)

A(k,i) = c

NEXT i

k:=1;

for i:=1 to n do

begin

c:=A[i,i];

A[i,i]:=A[k,i];

A[k,i]:=c

end

k:=1

нц для i от 1 до n

c:=A[i,i]

A[i,i]:=A[k,i] A[k,i]:=c

кц

 

 

Представим массив в виде квадратной таблицы, в которой для элемента массива A[i,j] величина i является номером строки, а величина j –номером столбца, в котором расположен элемент. Тогда данный алгоритм меняет местами

1) два столбца в таблице

2) две строки в таблице

3) элементы диагонали и k-ой строки таблицы

4) элементы диагонали и k-го столбца таблицы

 

Подобные задания на двумерные массивы в прошлом – нередкость. Кроме различного вида сортировок и перемещений элементов с одной позиции на другую, были также и присвоения значений элементам массива с дальнейшим нахождением, например, суммы элементов заданных строки или столбца.

Рассмотрим, как данный алгоритм будет исполняться для i = 1:

c := A[1,1];

A[1,1] := A[1,1];

A[1,1] := c;

 

Не произошло видимых изменений. Тогда рассмотрим его же для i = 2:

c := A[2, 2];

A[2, 2] := A[1, 2];

A[1, 2] := c;

Создадим таблицу 2*2 для демонстрации наглядности, строки – i столбцы – j:

 

До изменений:

 

i/j

1

2

1

A=[1, 1]

A=[1, 2]

2

A=[2, 1]

A=[2, 2]

 

После:

 

i/j

1

2

1

A=[1, 1]

A=[2, 1]

2

A=[2, 1]

A=[1, 2]

 

Отметим, что по исполнении алгоритма «местами поменялись» элемент массива(k-ая строка i-й столбец) и диагональ (i-ая строка, i-й столбец). Т.е. правильный ответ — 3.

 

Ответ: 3

 

А8. Укажите, какое логическое выражение равносильно выражению A /\ ¬ (¬B \/ C).

 

1) ¬A \/ ¬B \/ ¬C

2) A /\ ¬B /\ ¬C

3) A /\ B /\ ¬C

4) A /\ ¬B /\ C

 

Сейчас на экзамене чаще всего предлагается логическая функция с двумя, тремя, четырьмя переменными, а также частично заполненная таблица истинности для оных, и необходимо определить, какая переменная соответствует определенному столбцу.

Рассмотрим данное выражение. ¬(¬B \/ C) по законам де Моргана равносильно (B /\ ¬C). Т.е. в итоге получаем A /\ B /\ ¬C. А это третий ответ.

 

Ответ: 3

 

A10. Между четырьмя крупными аэропортами, обозначенными кодами DLU, IGT, OPK и QLO, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между этими аэропортами:

 

Аэропорт вылета

Аэропорт прилета

Время вылета

Время прилета

QLO

IGT

06:20

08:35

IGT

DLU

10:25

12:35

DLU

IGT

11:45

13:30

OPK

QLO

12:15

14:25

QLO

DLU

12:45

16:35

IGT

QLO

13:15

15:40

DLU

QLO

13:40

17:25

DLU

OPK

15:30

17:15

QLO

OPK

17:35

19:30

OPK

DLU

19:40

21:55

 

Путешественник находится в аэропорту DLU в полночь (0:00). Определите самое раннее время, когда он может оказаться в аэропорту QLO.

 

1) 15:40

2) 16:35

3) 17:15

4) 17:25

 

В экзаменах последних лет есть задание на анализ табличной информации, как правило, надо найти родственника данного человека по его ID. Иногда встречается вариация с двумя таблицам.

Выделим в таблице строки, где в столбце «аэропорт прилета» значится QLO. Заметим, что если путешественник полетит прямым рейсом, то окажется в QLO в 17.25. Но есть еще 2 рейса, с пересадкой. Если путешественник полетит сначала в аэропорт IGT, то не успеет на рейс в QLO на 13.15 (т. к. прилетит туда только в 13.30). А садиться на рейс до OPK ему нет смысла, потому что дальше по расписанию нет рейсов из OPK до QLO. Потому самое раннее время, когда он может оказаться в QLO – 17.25.

 

Ответ: 4

 

A12. Цепочка из трех бусин, помеченных латинскими буквами, формируется по следующему правилу. В конце цепочки стоит одна из бусин A, B, C. На первом месте – одна из бусин B, D, C, которой нет на третьем месте. В середине – одна из бусин А, C, E, B, не стоящая на первом месте.

 

Какая из перечисленных цепочек создана по этому правилу?

1) CBB

2) EAC

3) BCD

4) BCB

 

Методом исключения: не третья, потому что у этой цепочки в конце D (что противоречит первому условию), не четвертая (потому что противоречит второму условию – первая и последние буквы не могут быть одинаковыми), не вторая (потому что на первом месте не может быть E). Следовательно, остается только первый ответ.

 

Ответ: 1

 

A13. Для групповых операций с файлами используются маски имен файлов. Маска представляет собой последовательность букв, цифр и прочих допустимых в именах файлов символов, в которых также могут встречаться следующие символы:

Символ «?» (вопросительный знак) означает ровно один произвольный символ.

Символ «*» (звездочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность.

Определите, какое из указанных имен файлов удовлетворяет маске:

?hel*lo.c?*

 

1) hello.c

2) hello.cpp

3) hhelolo.cpp

4) hhelolo.c

 

В ЕГЭ последних лет нет заданий на знание масок файлов.

В искомом ответе перед буквой h обязан стоять символ (таких) вариантов всего два (третий и четвертый). Кроме того, в расширении файла должно быть по меньшей мере два символа. Таким образом, подходит лишь 3 ответ.

 

Ответ: 3

 

А15. Для кодирования цвета фона страницы Интернет используется атрибут bgcolor="ХХХХХХ", где в кавычках задаются шестнадцатеричные значения интенсивности цветовых компонент в 24-битной RGB-модели. Какой цвет будет у страницы, заданной тэгом <body bgcolor="FFFFFF">?

 

1) белый

2) зеленый

3) красный

4) синий

 

Первые два символа RGB-модели отвечают за красный (наибольшая интенсивность), вторые – за зеленый (наибольшая интенсивность), третьи – за синий (наибольшая интенсивность). Три этих цвета при наибольшей интенсивности дают белый.

 

Ответ: 1

 

B3. Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 25, запись которых в системе счисления с основанием четыре оканчивается на 11.

 

Рассмотрим, как выглядит число 25 в системе счисления с основанием четыре: 121. Т.е. искомые числа должны быть меньше 121. Тогда возможны два варианта. Либо 11, либо 111. Переведем их в десятичную систему счисления. Это числа 5 и 21.

 

Ответ: 5, 21

 

B6. Классный руководитель пожаловался директору, что у него в классе появилась компания из 3-х учеников, один из которых всегда говорит правду, другой всегда лжет, а третий говорит через раз то ложь, то правду. Директор знает, что их зовут Коля, Саша и Миша, но не знает, кто из них прав-див, а кто – нет. Однажды все трое прогуляли урок астрономии. Директор знает, что никогда раньше никто из них не прогуливал астрономию. Он вызвал всех троих в кабинет и поговорил с мальчиками. Коля сказал: "Я всегда прогуливаю астрономию. Не верьте тому, что скажет Саша". Саша сказал: "Это был мой первый прогул этого предмета". Миша сказал: "Все, что говорит Коля, – правда". Директор понял, кто из них кто. Расположите первые буквы имен мальчиков в порядке: "говорит всегда правду", "всегда лжет", "говорит правду через раз". (Пример: если бы имена мальчиков были Рома, Толя и Вася, ответ мог бы быть: РТВ).

 

Мне эта логическая задача напомнила «Самую сложную логическую головоломку» (предложена Джорджем Булосом в итальянской газете «la Repubblica» в 1992 году). Довольно жаль, что в ЕГЭ последних лет таких задач нет.

Из высказывания Коли мы замечаем, что он солгал. Таким образом, он либо всегда врет, либо по воле случая. Саша же сказал правду, т.е. он либо всегда говорит правду, либо по воле случая. Миша солгал. Т.е. он либо всегда врет, либо по воле случая. Допустим, что Коля врет по воле случая. Тогда Саша сказал правду, а ответ Миши также зависит от воли случая, что невозможно. Допустим, что Коля всегда лжет, а Саша – говорит правду по воле случая. Тогда Миша тоже солгал. Т.е. среди них троих два лжеца, что также невозможно. Таким образом, Коля всегда врет, Саша говорит правду, а Миша – говорит правду через раз.

 

Ответ: СКМ

 

B8. Строки (цепочки символов латинских букв) создаются по следующему правилу.

Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка.

Вот первые 4 строки, созданные по этому правилу:

(1) A

(2) BAA

(3) CBAABAA

(4) DCBAABAACBAABAA

 

Латинский алфавит (для справки):

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Запишите семь символов подряд, стоящие в восьмой строке со 126-го по 132-е место (считая слева направо).

 

Конечно, данное задание можно решить методом грубой силой – просто прописать 8 строку, в ней будет всего-то 255 символов (что, вероятнее всего, и делали первые ученики, сдающие ЕГЭ). Далее встречаются вариации данного задания с цифрами, но из ЕГЭ последних лет его исключили. Можно предположить, что на него у учеников уходило много времени, и они в итоге справлялись с ним только посредством «brute force».

Заметим, что в i-й строке i^2 - 1 символов. Т.е. в седьмой строке будет 127 символов, а в 8 – 255. В восьмой строке на 1 месте будет H, а потом дважды будет дублироваться 7 строка с последней буквой G. В 7 строке 127 символов. Из-за сдвига на 1, окончание 7 строки придется на 128 символ. Т.е. симоволы 126 = B, а  127 и 128 = A. Начиная со 129 символа, будет второй дубль 7 строки, которая начинается следующим образом: GFEDCBA...

 

126

127

128

129

130

131

132

B

A

A

G

F

E

D

 

Конечный ответ: BAAGFED.

 

Ответ:  BAAGFED

 

B10. В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу.

Для обозначения логической операции “ИЛИ” в запросе используется символ |, а для логической операции “И” – &.

 

1

принтеры & сканеры & продажа

2

принтеры & продажа

3

принтеры | продажа

4

принтеры | сканеры | продажа

 

В ЕГЭ последних лет дано количество запросов по каждому из значений, и необходимо использовать круги Эйлера и формулу включений-выключений для решения подобных примеров.

Для решения данного задания необходимо лишь помнить, что чем больше в логическом выказывании логических операций «ИЛИ», то тем больше запросов будет выдано поисковой строкой, а чем больше логических операций «И» – тем меньше запросов будет выдано поисковой строкой. Таким образом, в порядке возрастания запросы будут располагаться следующим образом: «принтеры & сканеры & продажа», затем «принтеры & продажа», потом «принтеры | продажа», и наконец «принтеры | сканеры | продажа». Правильный ответ будет 1234.

 

Ответ: 1234

 

Вывод

«Что-то модно, что-то вышло из моды, а что-то вечно». Будем надеяться, что эволюция экзамена идет правильным путем, и в содержании остается только лучшее. Время покажет.

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1754    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4416    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7460    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7855    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8837    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7803    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. tacu 04.03.19 05:58 Сейчас в теме
А6 :
----------
Т.е. правильный ответ — 3.
----------

Интересно, каков был правильный вопрос? ))
2. vasilev2015 2686 04.03.19 20:05 Сейчас в теме
Здравствуйте !

выбран вариант ответа из задания
3) элементы диагонали и k-ой строки таблицы
Оставьте свое сообщение