Вариант 1 Часть 1



Скачать 201.45 Kb.
Дата12.06.2016
Размер201.45 Kb.
Вариант 1

Часть 1

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

1 Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 01, Б – 10, В – 110, Г – 001, Д – 000. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было однозначно декодировать? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.



  1. это невозможно

  2. для буквы Б – 1

  3. для буквы В – 11

  4. для буквы Г – 00

Ответ: 

Борис заполнял таблицу истинности для выражения F. Он успел заполнить лишь небольшой фрагмент таблицы:



x1

x2

x3

x4

x5

x6

x7

x8

F







0










0




1

0







0













1




0










0







0

Каким выражением может быть F?









Ответ: 

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

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

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

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

plenty.xls

pleasure.blg

plain.pl


aeroplane.dll

stepladder.wlms

anyplace.nls

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

pleasure.blg

aeroplane.dll

anyplace.nls
1) *l*e*.*l* 2) *l*e.?l* 3) ?le*.*l 4) *l??e*.?l?

Ответ: 


Ответами к заданиям 4 – 23 являются число, последовательность букв или цифр, которые следует записать в бланк ответов №1 справа от номера соответствующего задания, начиная с первой клеточки, без пробелов, запятых и других дополнительных символов. Каждый символ пишите в отдельной клеточке в соответствии с приведёнными в бланке образцами.

4 Сколько единиц в двоичной записи десятичного числа 519?

Ответ: ______________________

5 Между населенными пунктами A, B C, D, E, F построены дороги, протяженность которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.






A

B

C

D

E

F

A




8

6

3







B

8













6

C

6







2

7




D

3




2







6

E







7







4

F




6




6

4







A

B

C

D

E

1




13

14

15

16

2

13

26

27

28

29

3

14

27

28

29

30

4

15

28

29

30

31

5

16

29

30

31

32

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

Ответ_____________________

6 Автомат получает на вход четырёхзначное число. Из этого числа строится новое число по следующим правилам.


  1. Вычисляются три числа – сумма первой и второй цифр, сумма второй и третьей и сумма третьей и четвертой цифр.

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

Пример. Исходное четырехзначное число: 7348. Сумма первой и второй цифр – 10. Сумма второй и третьей – 7. Сумма третьей и четвертой цифр – 12. Результат : 71012.

Укажите наименьшее число, в результате обработки которого автомат выдаст число 61417.

Ответ:________________________

7 Пете нужно с помощью электронных таблиц построить таблицу сложения для значений x и y от 13 до 16. Для этого сначала в в диапазонах B1:E1 и A2:A5 он записал числа от 13 до 16. Затем в ячейку E2 записал формулу сложения, после чего скопировал её во все ячейки диапазона B2:E5. В итоге на экране получился фрагмент таблицы:

Какая формула была записана в ячейке E2?


  1. = $A2 + E$1

  2. = $A2 + $E1

  3. = E$1 + A$2

  4. = A2 + E$1

8 Определите, что будет напечатано в результате выполнения программы. Для вашего удобства программа представлена на различных языках программирования.

Бейсик

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

K = 9

S = 43


WHILE S >= 0

K = K – 1

S = S – 2*K

WEND


PRINT K

алг

нач

цел k, s

k:= 9; s:= 43;



нц пока s >= 0

k:= k – 1; s:= s – 2*k;



кц

вывод k

кон

Паскаль

Си

var k, s: integer;

begin


k:= 9; s:= 43;

while s>= 0 do

begin

k:= k – 1;



s:= s – 2*k;

end;


writeln(k);

end.


#include

void main () {

int k, s;

k:= 9; s:= 43;

while (s>= 0) {

k -= 1; s -= 2*k;

}

printf("%d", k)



}

Ответ _________________.

9 Производится двухканальная (стерео) звукозапись с частотой дискретизации 48 кГц и 24-битным разрешением, результаты записываются в файл, сжатие данных не производится. В результате записи был получен файл размером 80 Мбайт. Определите приблизительно, сколько времени (в секундах) производилась запись. В качестве ответа укажите ближайшее к времени записи число, кратное 10.

Ответ ________________

10 Все четырехбуквенные слова, составленные из букв А, В, Д, Л, записаны в алфавитном порядке. Вот начало списка:



  1. АААА

  2. АААВ

  3. АААД

  4. АААЛ

  5. ААВА…

Запишите слово, которое стоит на 197-м месте списка.

11 Ниже на различных языках программирования записан рекурсивный алгоритм F



Бейсик

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

SUB F (n)

PRINT n, ’ ’

IF n <> 1 THEN

IF (n + 1)

ELSE

F (n \ 2)



END IF

END IF


END SUB


алг F (цел n)

нач

вывод n, ’ ’

если n <> 1 то

если mod (n,2) = 0 то

F (n +1)


иначе

F (div (n,2))



все

все

кон

Паскаль

Си

procedure F (n:integer);

begin


write (n, ’ ’);

if n <> 1 then

if n mod 2 = 0 then

F (n+1);


else

F (n div 2)

end.


void F (int n) {

printf ("%d", n);

if (n!=1)

if (n % 2 ==0)

F(n+1);

else


F (n/2);

}


Чему равна сумма чисел, напечатанных на экране при выполнении вызова F (13)?

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

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

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

Маска: 255.255.254.0

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



A

B

C

D

E

F

G

H

64

120

124

148

156

248

252

0

Пример.

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

A

B

C

D

E

F

G

H

128

168

255

8

127

0

17

192

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

Ответ ________________

13 Всем сотрудникам фирмы для работы в локальной сети выдается идентификатор, состоящий из 9 символов. Первые 6 символов состоят из букв латинского алфавита (всего используется 8 прописных букв). Следующие три символа – три десятичные цифры от 0 до 9. Под хранение каждого такого идентификатора на компьютере отводится минимально возможное и одинаковое целое количество байт, при этом используется посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов. Сколько идентификаторов доступно для использования, если для их хранения достаточно 10 Кб.

Ответ________________

14 Исполнитель Чертёжник Перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду Сместиться на (a, b) (где a, b – целые числа), перемещающую Чертёжника из точки с координатами (x, y) в точку с координатами (x+a, y+b). Если числа a, b положительные, то значение соответствующей координаты увеличивается, если отрицательные – уменьшается.

Например, если Чертёжник находится в точке с координатами (4, 2), то команда Сместиться на (2, – 3) переместит Чертёжника в точку (6, – 1)

Цикл


ПОВТОРИ число РАЗ

последовательность команд

КОНЕЦ ПОВТОРИ

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

Чертёжнику был дан для исполнения следующий алгоритм (буквами n, a, b обозначены неизвестные числа, при этом n > 1).

НАЧАЛО

Сместиться на (– 14, 16)



ПОВТОРИ n РАЗ

Сместиться на (22, –15)

Сместиться на (a, b)

Сместиться на (– 9,10)

КОНЕЦ ПОВТОРИ

Сместиться на (– 7, –30)

КОНЕЦ

Укажите наименьшее возможное значение числа n, для которого найдутся такие значение чисел a и b, что после выполнения программы Чертёжник возвратиться в исходную точку, из которой начал движение.


Ответ_____________

А

И

Л

Д

Г

Б

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



В

• • •



Ж

• • • •



К

Е
• • •

Ответ________________

16 Сколько единиц содержится в двоичной записи значения выражения:

16500 + 4600 – 16?

Ответ________________

17 На языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&».

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.



Запрос

Найдено страниц

(в сотнях тысяч)

Акварель

310

Натюрморт

360

Урок

270

Урок | Акварель

470

Натюрморт & (Урок | Акварель)

180

Акварель | Натюрморт

530

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

Урок & (Акварель | Натюрморт)?
Ответ_________________

18 На числовой прямой даны два отрезка: P = [2, 28] и Q = [11, 36]. Укажите наименьшую возможную длину такого отрезка A, что логическое выражение



тождественно истинно, то есть принимает значение 1 при любом значении переменной .

Ответ:________________

19 В программе обрабатывается одномерный целочисленный массив A с индексами от 0 до 9. Значения элементов равны 8; 5; -11; 4; -6; -9; 4; -10; 7; 8 соответственно, т.е. A[0]=8; A[1]=5 и т.д. Определите значение переменной k после выполнения следующего фрагмента программы, записанного ниже на разных языках программирования:



Бейсик

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

k = 0

FOR i = 0 TO 8

IF A(i)*A(i+1) > 0 THEN

k = k+1

t = A(i+1)

A(i+1) = A(9 – k+1)

A(9 – k+1) = t

END IF


NEXT i

k:=0

нц для i от 0 до 8

если A[i]*A[i+1] > 0 то

k:=k+1


t:= A[i+1]

A[i+1] := A[9 – k+1]

A[9 – k+1]: = t

все

кц


Паскаль

Си

k:=0;

for i:=0 to 8 do

if A[i]*A[i+1] > 0 then

begin


k:=k+1; t:= A[i+1];

A[i+1] := A[9 – k+1];

A[9 – k+1]: = t

end;


k:=0;

for (i=0; i < 9; i ++)

if (A[i]*A[i+1] > 0) {

k++;


t = A[i+1];

A[i+1] = A[9 – k+1];

A[9 – k+1] = t

}


Ответ:_____________
20 Ниже на четырех языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа K и R. Укажите наибольшее из таких чисел x, при вводе которых алгоритм печатает сначала 4, а потом 5.

Бейсик

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

INPUT X

K = 0 : R = 9

Y = X MOD 10

WHILE X > 0

K = K + 1

IF R > X MOD 10 THEN

R = X MOD 10

END IF


X = X\10

WEND


R = Y – R

PRINT K


PRINT R

алг

нач

цел x, K, R, y

ввод x

K := 0


R :=9

y := mod(x, 10)



нц пока x > 0

K := K+1


если R > mod (x, 10) то

R := mod (x, 10)



все

x := div (x, 10)



кц

R := y – R



вывод K, нс, R

кон

Паскаль

Си

var x, K, R, y: integer;

begin


readln (x);

K := 0; R := 9;

y := x mod 10;

while x > 0 do begin

K := K +1;

if R > x mod 10 then

R := x mod 10;

x := x div 10

end;

R := y – R;



writeln(K); writeln (R)

end.


#include

void main ()

{

int x, K, R, y;



scanf (″%d″, &x);

K = 0;


R = 9;

y = x % 10;

while (x > 0) {

K = K + 1

if (R > x %10)

R = x % 10;

x = x /10;

}

R = y – R;



printf (″%d\n%d″, K, R);

}


Ответ:___________

21 Получив на вход целое число k , этот алгоритм печатает число i. Укажите число различных значений входной переменной k, при которых программа выдает тот же ответ, что и при входном значении k=100. Значение k=100 также включается в подсчет различных значений k.



Бейсик

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

INPUT K

I = 5


Y = X MOD 10

WHILE I < 100 AND F(K) >=I

I = I + 1

WEND


PRINT I

FUNCTION F(X)

F = SQRT (X)

END FUNCTION



алг

нач

цел i, k

ввод k

i := 5


нц пока i < 100 и f(k) >=i

i := i+1


кц

вывод i

кон

алг вещ F (цел x)

нач

знач := sqrt(x)

кон

Паскаль

Си

var k, i: integer;

function F(x: integer) : real;

begin

f:=sqrt(x)



end;

begin


readln (k);

i := 5;


y := x mod 10;

while (i <100) and (f(k) >= 1)

do i := i +1;

writeln (i)

end.


#include

#include

float F(int x) {

return sqrt (x);

}

void main () {



int k, I;

scanf (″%d″, &k);

i = 5;

while (i < 100 && F(k) >=i)



i ++;

printf (″%d″, i);

}


Ответ: ______________

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



  1. прибавь 1

  2. умножь на 4

  3. умножь на 8

первая из них увеличивает число на экране на 1, вторая – увеличивает в 4 раза, а третья – в 8 раз. Программа для исполнителя Р148 – это последовательность команд.

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

Ответ: ______________
23 сколько существует различных наборов значений логических переменных x1, x2, …, x8, y1, y2, …, y8, которые удовлетворяют всем перечисленным ниже условиям?







В ответе не нужно перечислять все различные наборы значений x1, x2, …, x8, y1, y2, …, y8, при которых выполнена данная система неравенств. В качестве ответа нужно указать количество таких наборов.

Ответ:_______________

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

Часть 2

Для записи ответов на задания этой части (24 – 27) используйте БЛАНК ОТВЕТОВ №2. Запишите сначала номер задания (24, 25 и т.д.), а затем полное решение. Ответы записывайте четко и разборчиво.
24 На обработку поступает последовательность из пяти целых чисел (некоторые числа могут быть одинаковыми). Требовалось написать программу, которая должна найти среднее арифметическое чётных чисел и максимальное чётное число и вывести найденные числа на экран. Если чётных чисел в последовательности нет, требуется вывести на экране «NO». Известно, что вводимые числа не превышают 1000. Программист написал программу неправильно. Ниже эта программа для Вашего удобства приведена на четырёх языках программирования.

Бейсик

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

CONST N = 5

K = 0 : Sum = 0

MaxX = 0

FOR I = 1 TO N

INPUT X

IF X MOD 2 = 0 THEN



K = K + 1 : Sum = Sum + X

IF X < MaxX THEN MaxX = X

END IF

NEXT I


IF Sum <> 0 THEN

PRINT Sum /N

PRINT MaxX

ELSE


PRINT ″No″

END IF


END

алг

нач

цел N=5, I, X, K, Sum, MaxX

K :=0; Sum :=0

MaxX :=0

нц для I от 1 до N

ввод X

если mod (X, 2) = 0 то

K:=K+1


Sum:=Sum + X

если X > MaxX то

MaxX:=X


все

все

кц

если Sum <>0 то

вывод Sum/N, нс

вывод MaxX

все

кон



Паскаль

Си

const N=5;

var i, X, K, Sum, MaxX: integer;

begin

K:=0; Sum:=0; MaxX:=0;



for i:=1 to N do

begin


readln (X);

if X mod 2 = 0 then

begin

K := K + 1; Sum := Sum + X;



If X > MaxX then MaxX:= X

end


end;

if Sum <>0 then begin

writeln(Sum/N:2:1);

writeln (MaxX)

end

else writeln (‘No’)



end.

#include

void main () {

const int N=5

int i, X, K, Sum, MaxX;

K = 0; Sum = 0;

MaxX=0;


for (i = 1; i <= N; i++) {

scanf (″%d″, &X);

if (X % 2 ==0) {

K = K + 1

Sum = Sum+X;

if (X > MaxX)

MaxX = X;

}

}



if (Sum <> 0) {

printf (″%f\n″, (float) Sum/N);

printf (″%d\n″, MaxX);

}

else printf (No″)″



}

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



  1. Напишите, что выведет эта программа при вводе последовательности чисел – 6 5 – 8 4 2.

  2. Приведите пример такой последовательности, содержащей хотя бы одно чётное число, что, несмотря на ошибки, программа печатает правильный ответ.

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

  1. выпишите строку, в которой сделана ошибка;

  2. укажите, как исправить ошибку, - приведите правильный вариант строки.

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

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

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

Бейсик

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

CONST N=30

DIM A(1 TO N) AS INTEGER

DIM I AS INTEGER

DIM K AS INTEGER

DIM L AS INTEGER

DIM MAX AS INTEGER

FOR I=1 TO N

INPUT A(I)

NEXT I



END



алг

нач

цел N=30

целтаб a[1:n]

цел i, k, l max

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

ввод a[i]

кц



кон



Паскаль

Си

const N=30;

var a:array[1..N] of integer;

i, k, l, max: integer;

begin


for i:=1 to N do

readln(a[i]);

end.


#define N 30

void main(void) {

int a[N];

int i, k, l, max;

for (i=0; I < N; i++)

scanf ("%d", &a[i]);

}



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

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

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

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

Задание 1


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

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

Задание 2

Укажите два таких значения S, при которых у Коли есть выигрышная стратегия, причём



  • Коля не может выиграть за один ход, и

  • Коля может выиграть своим вторым ходом независимо от того, как будет ходить Саша. Для каждого указанного значения S опишите выигрышную стратегию Коли.

Задание 3

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



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

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

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

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

На некоторой остановке в течение одного часа для каждого пассажирского автобуса фиксируется время прибытия в минутах (целое число от 0 до 60), номер маршрута (целое число), название предприятия (текстовая строка 20 символов). Все автобусы одного маршрута принадлежат одному предприятию; одно предприятие может обслуживать несколько маршрутов. Для каждого маршрута задан плановый интервал движения в минутах (целое число от 5 до 15) – промежуток времени между моментами прихода автобусов данного маршрута. Если автобусы некоторого маршрута допускают интервал движения, превышающий плановый более чем на 2 минуты, то на предприятие начисляется по одному штрафному баллу за каждую минуту.

Напечатать список маршрутов и предприятий, чьи автобусы допустили нарушения, и число штрафных баллов в виде <Номер маршрута> <Предприятие> <Число штрафных баллов>.

Исходные данные вводятся в компьютер в следующем порядке:

Сначала вводится число M – число маршрутов, проходящих через данную остановку, а затем вводится M строк вида <Номер маршрута> <Интервал движения> <Название предприятия>.

Здесь <Номер маршрута> - разные целые числа в количестве M, <Интервал движения> - целые числа от 5 до 15, <Название предприятия> - строка символов не более 20.

Далее вводится число N – число прошедших через остановку автобусов, затем вводится N строк вида <Время прибытия> <Номер маршрута>. <Время прибытия> - целые числа от 0 до 60, вводятся в порядке неубывания, <Номер маршрута> - целые числа, каждое число обязательно совпадает с одним из <Номеров маршрута> введённых выше.







Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©uverenniy.ru 2019
обратиться к администрации

    Главная страница