ВАРИАНТ 5

Часть 1

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

1. Сколько единиц содержится в двоичной записи восьмеричного числа 2417₈?

Ответ: __________________________ .

2. Дан фрагмент таблицы истинности выражения F, зависящего от трех аргументов X, Y, Z:

Перечислите в порядке возрастания без запятых и пробелов номера логических выражений, которые соответствуют F:

Ответ: __________________________ .

3. На рисунке справа схема дорого Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги и пункта В в пункт Д. В ответе запишите целое число — так, как оно указано в таблице.

Ответ: __________________________ .

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

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

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

В каталоге находятся шесть файлов:

Ниже представлено восемь масок. Сколько из них таких, которым соответствует ровно три файла из данного каталога?

Ответ: __________________________ .

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

А-110, Б-10, В-01, Г-111. Каким кодовым словом должна кодироваться буква Д? Если таких вариантов несколько, укажите самый короткий.

Ответ: __________________________ .

6. Автомат получает на вход два двузначных шестнадцатеричных числа. В этих числах все цифры не превосходят цифру 7 (если в числе есть цифра больше 7, автомат отказывается работать). По этим числам строится новое шестнадцатеричное число по следующим правилам.

1. Вычисляются два шестнадцатеричных числа — сумма старших разрядов полученных чисел и сумма младших разрядов этих чисел.

2. Полученные два шестнадцатеричных числа записываются друг за другом в порядке возрастания (без разделителей).

Пример. Исходные числа: 52, 66. Поразрядные суммы: В, 8. Результат: 8В.

Какие из предложенных чисел могут быть результатом работы автомата?

Перечислите в алфавитном порядке буквы, соответствующие этим числам, без пробелов и знаков препинания.

A) 18

B) 2F

C) 214

D) 7Е

E) В7

Ответ: __________________________ .

7. В электронной таблице значение формулы =СРЗНАЧ (С2:D5) равно 3. Чему равно значение формулы =СУММ (С5:D5), если значение формулы =СРЗНАЧ (С2:D4) равно 5?

Ответ: __________________________ .

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

Бейсик	Паскаль
Си	Алгоритмический язык

Ответ: __________________________ .

9. Какой минимальный объём памяти (в Кбайт) нужно зарезервировать, чтобы можно было сохранить любое растровое изображение размером 64x256 пикселей при условии, что в изображении могут использоваться 4 различных цвета? В ответе запишите только целое число, единицу измерения писать не нужно.

Ответ: ______________­_________________ .

10. Все 4-буквенные слова, составленные из букв Б, В, Г, Д, записаны в алфавитном порядке. Вот начало списка:

1. ББББ

2. БББВ

3. БББГ

4. БББД

5. ББВБ

Запишите слово, стоящее на 244-м месте от начала списка.

Ответ: ______________­_________________ .

11. Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = F(n - 1) + n - 2, при n > 1

F(1) - 2

Чему равно значение функции F(7)?

(В ответе запишите только натуральное число.)

Ответ: ______________­_________________ .

12. На месте преступления были обнаружены четыре обрывка бумаги. Следствие установило, что на них записаны фрагменты одного IP-адреса. Криминалисты обозначили эти фрагменты буквами А, В, С и D. Восстановите IР-адрес.

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

А	В	С	D

Ответ: ______________­_________________ .

13. Для передачи секретного сообщения используется код, состоящий из десятичных цифр. При этом все цифры кодируются одним и тем же (минимально возможным) количеством бит. Определите информационный объём сообщения (в байтах) длиной в 200 символов.

Ответ: ______________­__________________ .

14. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А) заменить (v, w).

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды

заменить (222, 34)

преобразует строку 77222277 в строку 7734277.

Если в строке нет вхождений цепочки и, то выполнение команды заменить (v, w) не меняет эту строку.

Б) нашлось (v).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение “истина”, в противном случае возвращает значение “ложь”. Строка исполнителя при этом не изменяется.

Цикл

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

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

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

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 80 идущих подряд цифр 7? В ответе запишите полученную строку.

Ответ: ______________­__________________ .

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

Ответ: __________________________ .

16. Укажите наименьшее основание системы счисления, в которой запись десятичного числа 70 имеет ровно 3 значащих разряда.

Ответ: ______________­_________________ .

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

Запрос	Количество найденных страниц
Колеса	8700
Шины	4300
Колеса & Шины	1400

Какое количество страниц будет найдено по запросу: Колеса | Шины?

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

Ответ: ______________­_________________ .

18. Какое количество натуральных чисел удовлетворяет логическому условию:

Ответ: ______________­_________________ .

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

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

Бейсик	Паскаль
Си	Алгоритмический язык

Ответ: ______________­_________________ .

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

Бейсик	Паскаль
Си	Алгоритмический язык

Ответ: ______________­_________________ .

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

Бейсик	Паскаль
Си	Алгоритмический язык

Ответ: ______________­_________________ .

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

1. прибавь 3,

2. умножь на 2.

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

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

Ответ: ______________­_________________ .

23. Сколько существует различных наборов значений логических переменных x₁, х₂, ... x₉, х₁₀, которые удовлетворяют всем перечисленным ниже условиям?

В ответе не нужно перечислять все различные наборы значений x₁, х₂, ... x₉, х₁₀, при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

Ответ: ______________­__________________ .

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

Часть 2

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

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

Паскаль	Бейсик
Си	Алгоритмический язык

Последовательно выполните следующее.

1. Перерисуйте и заполните таблицу, которая показывает, как работает программа при аргументах, принадлежащих различным областям (А, В, С, D, Е, F, G, Н и I).

Точки, лежащие на границах областей, отдельно не рассматривать.

Область	Условие 1 (y<= х)	Условие 2 (у<=-х)	Условие 3 (у>= х*x-2)	Программа выведет	Область обрабатывается верно
А
В
С
D
Е
F
G
Н
I

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

2. Укажите, как нужно доработать программу, чтобы не было случаев её неправильной работы. (Это можно сделать несколькими способами, достаточно указать любой способ доработки исходной программы.)

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

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

Паскаль	Бейсик
СИ	Алгоритмический язык
Русский (естественный) язык
Объявляем массив А из 40 элементов. Объявляем целочисленные переменные I, К, MAX, МАХ2. В цикле от 1 до 40 вводим элементы массива А с 1-го по 40-й. ...

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

26. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два камня или увеличить количество камней в куче в два раза. Например, имея кучу из 18 камней, за один ход можно получить кучу из 19, 20 или 36 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

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

В начальный момент в куче было S камней, 1 ≤ S ≤ 30.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

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

1. а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.

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

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

3. Укажите значение S, при котором выполняется два условия:

- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и

- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах — количество камней в куче.

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

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

Районный методист решила выяснить такие номера школ.

Программа должна вывести на номера этих школ, в любом порядке.

Если такая школа окажется одна, нужно вывести наибольший балл в этой школе, с указанием того, что это наибольший балл.

Если таких школ не окажется, нужно вывести об этом сообщение.

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

На вход программе сначала подаётся число учеников, сдававших экзамен. В каждой из следующих N строк находится информация об учениках в формате:

<Фамилия> <Имя> <Номер школы> <Количество баллов>,

где <Фамилия> — строка, состоящая не более, чем из 30 символов без пробелов, <Имя> — строка, состоящая не более, чем из 20 символов без пробелов, <Номер школы> — целое число в диапазоне от 1 до 99, <Количество баллов> — целое число диапазоне от 0 до 100. Эти данные записаны через пробел, причем ровно один между каждой парой (то есть, всего по три пробела в каждой строке).

Пример входной строки:

Иванов Иван 50 87

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

5 50 74 87

Другой вариант выходных данных:

7

Наибольший балл = 74

Третий вариант выходных данных:

Нет таких школ