ВАРИАНТ 11

Часть 1

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

1. Даны 4 целых числа, записанных различных системах счисления: 9F₁₆, 10110101₂> 274₈, СЕ₁₆. Сколько среди них чисел, значение которых лежит между А5_1б и CD₁₆?

Ответ: ______________­__________________ .

2. Дан фрагмент таблицы истинности выражения F. Значения в пустых клетках таблицы неизвестны и могут быть любыми из возможных.

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

Ответ: ______________­__________________ .

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

	А	В	С	D	Е	F
А		7	2
В	7		4	2	2	4
С	2	4		5	1
D		2	5		4	3
Е		2	1	4		8
F		4		3	8

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

Ответ: ______________­__________________ .

4. В папке D:\Pictures\School находятся следующие файлы и только они:

kino.gif

vano.jpg

ono.jpg

domino.gif

no.jpg

К этим файлам применили следующую операцию: файлы, имена которых удовлетворяют маске *?no.*g* переместили в папку ".." относительно текущей. Сколько файлов останется в исходной папке?

Ответ: ______________­__________________ .

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

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

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

Ответ: ______________­__________________ .

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

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

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

Пример: Исходные числа: 52, 44. Поразрядные произведения: 20 = 14_1б, 8. Результат: 814.

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

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

A) 4В

B) АВ

C) СА

D) 9С

E) 616

Ответ: ____________________________

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

	А	В	С	D
1	4	5	3
2	2	1	=А1+В2
3	6	7	=А$2+В3

Чему станет равным значение ячейки D2, если в неё скопировать формулу из ячейки С3?

Примечание: знак $ обозначает абсолютную адресацию.

Ответ:___________________________

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

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

Ответ: ______________­_________________ .

9. Производится двухканальная (стерео) звукозапись с частотой дискретизации 16 кГц и количеством уровней квантования 65536. Запись длится 4 минуты, её результаты записываются в файл, сжатие данных не производится. Укажите размер полученного файла (в Мбайт) с точностью 5 Мбайт. В ответе запишите только целое число, единицу измерения писать не нужно.

Ответ: ______________­_________________ .

10. Вася и Петя передают друг другу сообщения, используя флажки 6-ти цветов. Эти они делают, поднимая последовательно один из флажков, потом опускают его и поднимают ещё какой-то. Чтобы не путаться, ребята договорились, что флажки в одном сообщении не могут повторяться. Сколько различных сообщений могут передавать мальчики?

Ответ: ______________­_________________ .

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

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

Ответ: ______________­_________________ .

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

По заданным IP-адресу узла и маске определите адрес сети.

IP-адрес узла: 251.137.219.94

Маска: 255.255.248.0

При записи ответа выберите из приведённых в таблице чисел четыре элемента IP-адреса и запишите в нужном порядке соответствующие им буквы. Точки писать не нужно.

A	В	С	D	Е	F	G	H
0	94	137	216	219	248	251	255

Пример

Пусть искомый IP-адрес 192.168.128.0, и дана таблица

A	В	С	D	Е	F	G	H
128	168	255	8	127	0	17	192

В этом случае правильный ответ будет записан в виде: HBAF

Ответ: ______________­_________________ .

13. При регистрации в компьютерной системе каждому пользователю выдается пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора: А, В, С, D, Е, F, G, Н, К, L, М, N. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего отведено 12 байт на одного пользователя.

Определите объём памяти (в байтах), необходимый для хранения сведений о 30 пользователях. В ответе запишите только целое число — количество байт.

Ответ: ______________­__________________ .

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

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

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

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

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

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

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

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

Цикл

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

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

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

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

Ответ: ______________­_________________ .

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

Ответ: ______________­_________________ .

16. Запись десятичного числа в системах счисления с основаниями 4 и 7 в обоих случаях имеет последней цифрой 0. Какое минимальное натуральное десятичное число удовлетворяет этому требованию?

Ответ: ______________­_________________ .

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

Запрос	Количество найденных страниц (в тысячах)
Колбаса | Сыр | Паштет	26
Паштет	13
Сыр	8
Колбаса & Паштет	3
Сыр & Паштет	2
Колбаса & Сыр	2
Колбаса & Сыр & Паштет	1

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

Ответ: ______________­_________________ .

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

Ответ: ______________­__________________ .

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

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

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

Ответ: ______________­__________________ .

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

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

Ответ: ______________­__________________ .

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

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

Ответ: ______________­__________________ .

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

1. прибавь 1,

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

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

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

Ответ: ______________­__________________ .

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

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

Ответ: ______________­__________________ .

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

Часть 2

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

24. Требовалось написать программу, которая вводит с клавиатуры натуральное число N (N < 10⁹) и выводит на экран наибольшую цифру числа. Программист торопился и написал программу неправильно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Укажите такое значение S, при котором:

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

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

27. В секретной службе некоторой страны работает N сотрудников (N < 40 000). Каждый сотрудник имеет свой собственный уникальный номер, совпадающий с порядковым номером в ведомости на зарплату. Специальная пропускная система на входе фиксирует номер каждого сотрудника, пришедшего на работу. В середине дня начальник заподозрил, что, возможно, один из сотрудников на работу не пришёл. Он запросил у пропускной системы список пришедших сотрудников.

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

На вход программе подаётся:

— в первой строке: количество сотрудников в службе N,

— во второй строке: последовательность номеров сотрудников, заканчивающийся нулем (этот ноль служит признаком окончания последовательности).

Программа должна вывести требуемую последовательность, если один из сотрудников не пришёл на работу, или сообщение “Все пришли”, если прогульщика нет.

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

5

3 2 5 1 4 0

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

Все пришли

Другой пример входной строки:

5

3 5 1 4 0

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

1 3 4 5