ВАРИАНТ 16

Информатика - 20 тренировочных вариантов экзаменационных работ для подготовки к единому государственному экзамену - 2018 год

ВАРИАНТ 16

Часть 1

Ответами к заданиям 1—23 являются число, последовательность букв или цифр, которые следует записать в БЛАНК ОТВЕТОВ № 1 справа от номера соответствующего задания, начиная с первой клеточки, без пробелов, запятых и других дополнительных символов. Каждый символ пишите в отдельной клеточке в соответствии с приведёнными в бланке образцами.

1. Сколько чисел находится между С916 и D416?

Ответ: ______________­__________________ .

2. Логическая функция F задаётся выражением Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных х, у, z.

Перем. 1

Перем. 2

Перем. 3

Функция

???

???

???

F

0

0

0

0

0

0

1

0

0

1

0

1

0

1

1

0

1

0

0

0

1

0

1

0

1

1

0

1

1

1

1

1

В ответе напишите буквы х, у, z в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая 1-му столбцу; затем — буква, соответствующая 2-му столбцу; затем — буква, соответствующая 3-му столбцу). Букве в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример

Пусть задано выражение х → у, зависящее от двух переменных х и у, и таблица истинности:

Перем. 1

Перем. 2

Функция

???

???

F

0

0

1

0

0

0

0

1

1

0

1

1

Тогда 1-му столбцу соответствует переменная I/, а 2-му столбцу соответствует переменная х. В ответе нужно написать: ух.

Ответ: ______________­__________________ .

3. Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам).

Ответ: ______________­__________________ .

4. Дан фрагмент базы данных, содержащий информацию о родственных отношениях. Определите, сколько предков женского пола Жуйко А.И. упомянуто в таблице.

Таблица 1


Таблица 2


ID

Фамилия И.О.

Пол


ID_Родителя

ID_Ребёнка

1518

Гираб В.А.

М


1885

3472

1885

Жуйко А.И.

М


6109

3472

2946

Калпен Л.В.

М


9657

1885

3472

Арно В.А.

Ж


4705

1885

4705

Иваненко И.Л.

М


2946

4705

5624

Ирита Е.О.

Ж


5624

4705

6109

Кирта У.Т.

Ж


8434

2946

7296

Олинг К.Л.

Ж


1518

2946

8434

Кименко З.Т.

Ж


2946

7296

9657

Вирк Я.М.

Ж


5624

7296


...



...

...

Ответ: ______________­__________________ .

5. Для кодирования некоторой последовательности, состоящей из букв А, В, С и D, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код:

А-1101, В-100, С-000, D-111. Можно ли сократить для одной или нескольких букв длину кодового слова, удалив в нём один или несколько последних символов, чтобы код по-прежнему можно было декодировать однозначно? Если такое можно сделать несколькими способами, укажите тот, для которого общая длина кода будет минимальной.

Запишите ответ в виде: буква, кодовое слово. Если таких букв несколько, то далее через запятую перечислите буквы и их коды. Буквы перечислять в алфавитном порядке. Например, если бы ответ был “Для буквы F новый код будет 110, а для буквы G новый код будет 101”, ответ нужно записать как: F110,G101. Если невозможно ничего сократить, запишите в ответе просто цифру 0.

Ответ: ______________­_________________ .

6. У исполнителя Утроитель две команды, которым присвоены номера:

1. умножь на 3,

2. прибавь 1.

Первая из них утраивает число на экране, вторая — увеличивает его на 1.

Запишите порядок команд в программе преобразования числа 5 в число 72, содержащей не более 5 команд, указывая лишь номера команд. (Например, 21211 — это программа

прибавь 1

умножь на 3

прибавь 1

умножь на 3

умножь на 3,

которая преобразует число 1 в 63.)

(Если таких программ более одной, то запишите любую из них.)

Ответ: ______________­_________________ .

7. Дан фрагмент электронной таблицы:


А

В

С

D

1

3



5

2

=(D1-A1)*2

=А1+А2-3

=D1-1

=(В1+1)*2

Какое число должно быть записано в ячейке В1, чтобы построенная после выполнения вычислений диаграмма по значениям диапазона ячеек A2:D2 соответствовала рисунку?

Ответ: ______________­_________________ .

8. Определите, что будет напечатано в результате выполнения следующего фрагмента программы:

Бейсик

Паскаль

Си

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

Ответ: ______________­__________________ .

9. Документ объёмом 16 Мбайт можно передать с одного компьютера на другой двумя способами:

А. Сжать архиватором, передать по каналу связи, распаковать.

Б. Передать по каналу связи без использования архиватора.

Какой способ быстрее и на сколько, если:

• средняя скорость передачи данных по каналу связи составляет 221 бит в секунду;

• объём сжатого архиватором документа равен 25% исходного;

• время, требуемое на сжатие документа, — 8 секунд, на распаковку — 3 секунды?

В ответе напишите букву А, если быстрее способ А, или Б, если быстрее способ Б. Сразу после буквы напишите число, обозначающее, на сколько секунд один способ быстрее другого.

Так, например, если способ Б быстрее способа А на 23 секунды, в ответе нужно написать Б23.

Единиц измерения “секунд”, “сек.”, “с.” к ответу добавлять не нужно.

Ответ: ______________­__________________ .

10. В некотором племени для общения используется всего 64 слова. Вождь племени на общем собрании произносит 32 слова. Какое количество информации (число бит) сообщает вождь?

Ответ: ______________­__________________ .

11. Определите, сколько звёздочек будет напечатано в результате вызова F(1) приведённой подпрограммы:

Бейсик

Паскаль

Си

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

Ответ: ______________­__________________ .

12. В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес, — в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого разряда — нули.

Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске.

Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0.

Для узла с IP-адресом 117.203.214.56 адрес сети равен 117.203.192.0. Чему равно наибольшее возможное значение третьего слева байта маски? Ответ запишите в виде десятичного числа.

Ответ: ______________­__________________ .

13. На стадионе имеется 10 секторов, в каждом из которых установлено по 80 кресел в 40 рядов. При кодировании номера места автоматизированная система продажи билетов использует минимально возможное количество бит, одинаковое для каждого номера места, отдельно номер сектора, номер ряда и номер места в ряду. При этом для записи кода используется минимально возможное и одинаково целое количество байтов. Каков объём информации (в байтах), записанный устройством после продажи 200 билетов?

Ответ: ______________­__________________ .

14. Система команд исполнителя РОБОТ, “живущего” в прямоугольном лабиринте на клетчатой плоскости включает 4 команды-приказа и 4 команды проверки условия. Команды-приказы:

вверх

вниз

влево

вправо

При выполнении этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →.

Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится и программа прервётся.

Другие четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:

сверху свободно

снизу свободно

слева свободно

справа свободно

Цикл

выполняется, пока условие истинно.

В конструкции

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Сколько клеток лабиринта соответствует требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F6)?

Ответ: ______________­__________________ .

15. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, 3, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Ответ: ______________­__________________ .

16. Запись числа 42510 в системе счисления с основанием N оканчивается на 5 и содержит 4 цифры. Перечислите через запятую все такие N в порядке возрастания.

Ответ: ______________­__________________ .

17. В языке запросов к поисковому серверу для обозначения логической операции “ИЛИ” используется символ |, а для логической операции “И” — &. В таблице приведено количество страниц, которое находит поисковая система по каждому запросу.

Запрос

Количество найденных страниц (в тысячах)

Бирка & Табличка & Ценник

5

Бирка

36

Табличка

43

Ценник

48

Бирка & Табличка

18

Бирка & Ценник

20

Табличка & Ценник

28

Какое количество страниц (в тысячах) будет найдено этой поисковой системой по запросу Бирка | Табличка | Ценник?

Ответ: ______________­_________________ .

18. На числовой прямой даны отрезки Р = [5, 13] и Q = [8, 19]. Укажите наименьшую возможную длину такого отрезка А, что формула верна при любых значениях х.

Ответ: ______________­_________________ .

19. В программе используется целочисленный массив А с индексами от 0 до 9. Значения элементов массива равны 6; 5; 4; 7; 10; 6; 9; 11; 7; 8 соответственно, т.е. А[0] = 4; А[1] = 5 и т.д.

Определите значение переменной k после выполнения следующего фрагмента программы, записанной ниже на разных языках программирования.

Бейсик

Паскаль

Си

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

Ответ: ______________­_________________ .

20. Ниже на четырёх языках записан алгоритм. Получив на вход число х, этот алгоритм печатает два числа L и М. Укажите наименьшее число х, при вводе которого алгоритм печатает сначала 3, а потом 7.

Бейсик

Паскаль

Си

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

Ответ: ______________­_________________ .

21. Определите, при каком наибольшем значении b в результате выполнения следующего алгоритма будет напечатано число 10 (для Вашего удобства алгоритм представлен на четырёх языках):

Бейсик

Паскаль

Си

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

Ответ: ______________­_________________ .

22. У исполнителя Прибавлятель две команды, которым присвоены номера:

1. прибавь 1,

2. прибавь 9.

Первая из них увеличивает число на экране на 1, вторая увеличивает его на 9. Программа для Прибавлятеля — это последовательность команд.

Сколько есть программ, которые число 2 преобразуют в число 25?

Ответ: ______________­_________________ .

23. Сколько существует различных наборов значений логических переменных x1, х2, ... х7, х8, которые удовлетворяют всем перечисленным ниже условиям?

В ответе не нужно перечислять все различные наборы значений x1, х2, ... х7, х8, при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

Ответ: ______________­_________________ .

Не забудьте перенести все ответы в бланк ответов № 1 в соответствии с инструкцией по выполнению работы.

Часть 2

Для записи ответов на задания этой части (24—27) используйте БЛАНК ОТВЕТОВ № 2. Запишите сначала номер задания (24, 25 и т. д.), а затем полное решение. Ответы записывайте чётко и разборчиво.

24. Требовалось написать программу, которая вводит с клавиатуры последовательность из n целых чисел (n — 4), и выводит на экран количество нечётных чисел среди этой последовательности. Известно, что вводимые числа не превышают по модулю 1000. Программист торопился и написал программу неправильно.

Паскаль

Бейсик

Си

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

Выполните следующие действия:

1. Напишите, что выведет программа при вводе чисел -1 1 -3 5.

2. Приведите пример такой входной последовательности, при которой программа работает верно.

3. Укажите все ошибки в программе и исправьте их. Для этого для каждой ошибки: выпишите строку, которая написана неправильно и приведите правильный вариант строки.

25. Дан целочисленный массив из 40 элементов. Элементы массива могут принимать значения от -10000 до 10000. Опишите на русском языке или на одном из языков программирования алгоритм, который находит и выводит количество элементов массива, равных максимальному элементу массива.

Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них.

Паскаль

Бейсик

СИ

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

Русский (естественный) язык

Объявляем массив А из 40 элементов.

Объявляем целочисленные переменные I, J, К, МАХ.

В цикле от 1 до 40 вводим элементы массива А с 1-го по 40-й.

...

В качестве ответа вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например Borland Pascal 7.0) или в виде блок-схемы. В этом случае вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на естественном языке).

26. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. Назовем позицией игры указание количества камней в обеих кучах. Например, позиция (15,20) означает, что в первой куче 15 камней, а во второй — 20. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной из куч в два раза. Например, имея количество камней в кучах (15,20), за один ход можно получить положение (16,20), (30,20), (15,21) и (15,30). У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в обеих кучах (сумма) становится не менее 58. Победителем считается игрок, сделавший последний ход, то есть первым получивший положение, в котором сумма камней в кучах будет 58 или больше камней.

Говорят, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (8,25), (7,26), (10,24) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

1. Для исходных позиций (7,25) и (9,24) укажите, кто из игроков выигрывает. Сколько ходов необходимо для выигрыша? Опишите выигрышную стратегию. Обоснуйте ответ.

2. Для исходных позиций (6,25), (8,24) и (9,23) укажите, кто из игроков выигрывает. Сколько ходов необходимо для выигрыша? Опишите выигрышную стратегию. Обоснуйте ответ.

3. Для исходной позиции (8,23) укажите, кто из игроков выигрывает. Сколько ходов необходимо для выигрыша? Опишите выигрышную стратегию. Приведите дерево игры. Обоснуйте ответ. На рёбрах дерева указывайте, кто делает ход, в узлах - позицию игры.

27. Из населённого пункта R в населенный пункт Q ведут две дороги. Назовём их А и В.

Дороги идут невдалеке друг от друга, не пересекаются. Периодически между ними встречаются соединительные дороги (связки), по которым можно переехать с дороги А на дорогу В и обратно.

Необходимо найти кратчайшее расстояние между населёнными пунктами R и Q при условии, что можно ехать по любой дороге — А или В, и любое количество раз переезжать (если это нужно/короче) по дорогам-связкам с одной дороги на другую.

На вход программе подаётся: в первой строке — число дорог-связок N.

В каждой из последующих N строк — три целых неотрицательных числа: расстояние от предыдущей “развилки” по дороге А, расстояние от предыдущей развилки по дороге В, длина дороги-связки (в последней строке длина дороги-связки равна нулю).

Пример входных данных:

4

3 7 3

12 2 4

3 10 5

7 6 0

Пример выходных данных:

22