Дорогие ученики, выбравшие экзамен по информатике и ИКТ!
Вот задания на 2 неделю апреля. Решение оформите в таблицу и отправьте на мой электронный адрес.
С уважением Татьяна Викторовна.
Часть 1.
Ответами к заданиям 1–23 являются число или последовательность цифр. Запишите ответ справа от номера задания без пробелов, запятых и других дополнительных символов.
1
1
Сколько единиц в двоичной записи шестнадцатеричного числа 10FA16?
2
2
Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых в километрах приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
A
B
C
D
E
F
A
2
5
10
B
2
1
2
C
1
3
2
D
3
1
E
5
2
2
3
F
10
1
3
Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам). В ответе укажите только число.
3
3
Каждое из логических выражений F и G содержит 5 переменных. В таблицах истинности выражений F и G есть ровно 5 одинаковых строк, причём ровно в 4 из них в столбце значений стоит 1.
Сколько строк таблицы истинности для выражения F v G содержит 1 в столбце значений?
4
4
Ниже представлены две таблицы из базы данных. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных суммарное количество дочерей и внучек Гольдони А.С.
Таблица 1
ID
Фамилия_И.О.
Пол
17
Гречко Н.А
Ж
24
Гречко И.М.
М
25
Гречко М.И.
М
26
Гречко М.М.
М
34
Лагидзе А.И.
Ж
35
Лагидзе В.С.
Ж
37
Лагидзе С.С.
М
44
Гольдони А.С.
Ж
45
Гольдони Л.А.
М
46
Гланц О.С.
М
48
Гланц М.О.
М
54
Гаранян А.М.
Ж
75
Михейко М.А.
Ж
...
...
...
Таблица 2
ID_родителя
ID_ребенка
24
25
44
25
25
26
75
26
24
34
44
34
34
35
37
35
17
37
34
46
37
46
25
54
75
54
...
5
5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
А) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 10000 преобразуется в запись 100001;
Б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите такое наименьшее число А, для которого результат работы алгоритма больше 77. В ответе это число запишите в десятичной системе счисления.
6
6
Дан фрагмент электронной таблицы
A
B
C
D
E
1
40
4
100
70
7
2
30
3
60
6
3
= B$3 * $D2
2
300
50
5
4
10
1
400
40
4
Из ячейки АЗ в ячейку С2 была скопирована формула. При копировании адреса ячеек в формуле автоматически изменились. Каким стало числовое значение формулы в ячейке С2?
Примечание: знак $ обозначает абсолютную адресацию.
7
7
Какой минимальный объём памяти (в Кбайт) нужно зарезервировать, чтобы можно было сохранить любое растровое изображение размером 512x512 пикселов при условии, что в изображении могут использоваться 256 различных цветов? В ответе запишите только целое число, единицу измерения писать не нужно.
8
8
Запишите число, которое будет напечатано в результате выполнения следующей программы. Для Вашего удобства программа представлена на пяти языках программирования.
Бейсик
DIM S, N AS INTEGER
S = 0
N = 0
WHILE S <= 65
S = S + 5
N = N + 3
WEND
PRINT N
Python
s = 0
n = 0while s <= 65:
s = s + 5
n = n + 3
print(n)
Алгоритмический язык
алг
нач
цел n, s
п : — 0
s : = 0
нц пока s <= 65
s : = s + 5
п : = п + 3
кц
вывод п
кон
Паскаль
var s, n: integer;
begin
s : = 0;
n : = 0;
while s <= 65do
begin
s : = s + 5;
n : = n + 3
end;
writeln(n)
end.
Си
#include<stdio.h>intmain(){ int s = 0, n = 0;
while (s <= 65) { s = s + 5; n = n + 3; }
printf("%d\n", n);
return0;
}
9
9
Для кодирования некоторой последовательности, состоящей из букв А, Б, В и Г, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В используются такие кодовые слова: А — 000, Б — 1, В — 011. Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
10
10
Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является цифрой от 1 до 4. Сколько различных вариантов шифра можно задать, если известно, что цифра 1 может встречаться ровно два раза, а каждая из других допустимых цифр может встречаться в шифре любое количество раз или не встречаться совсем?
11
11
Ниже на 5 языках программирования записана рекурсивная функция (процедура) F.
Бейсик
SUB F (n)
PRINT n,
IF n > 2 THEN
F(n - 3)
F(n - 2)
F(n - 1)
END IF
END SUB
Python
defF(n):print (n, end='')
if n > 2:
F(n - 3)
F(n - 2)
F(n - 1)
Алгоритмический язык
алг F(цел n)
нач
вывод n
если n > 2 то
F(n - 3)
F(n - 2)
F(n - 1)
все
кон
Паскаль
procedure F(n: integer);
begin
write(n);
if n > 2then
begin
F(n - 3);
F(n - 2);
F(n - 1)
end
end;
Что выведет программа при вызове F(4)? В ответе запишите последовательность выведенных цифр слитно (без пробелов).
12
12
В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP- адрес, — в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого разряда — нули. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске.
Например, если IP-адрес узла равен 237.33.255.123, а маска равна 255.255.240.0, то адрес сети равен 237.33.240.0.
Для узла с IP-адресом 119.167.50.77 адрес сети равен 119.167.48.0. Чему равно наименьшее возможное значение третьего слева байта маски? Ответ запишите в виде десятичного числа.
13
13
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 10 символов и содержащий только символы из 26-символьного набора латинского алфавита. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей.
Для хранения сведений о 10 пользователях потребовалось 500 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число — количество байт.
14
14
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах и и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.
Например, выполнение команды заменить (555, 63)
преобразует строку 12555550 в строку 1263550.
Если в строке нет вхождений цепочки и, то выполнение команды заменить (и, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка и в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции ЕСЛИ условие ТО команда 1 ИНАЧЕ команда2 КОНЕЦ ЕСЛИ выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 1000 идущих подряд цифр 8? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (999) ИЛИ нашлось (888)
ЕСЛИ нашлось (888)
ТО заменить (888, 9)
ИНАЧЕ заменить (999, 8)
КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ
15
15
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, 3, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Ж, но не проходящих через город К?
16
16
Значение арифметического выражения: 92016 + З2015 — 9 — записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи?
17
17
В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для обозначения логической операции «И» — символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
Запрос
Найдено страниц (в тыс.)
Сосна & Ель
270
Сосна & (Ель | Кедр)
530
Сосна & Кедр
360
Какое количество страниц (в тысячах) будет найдено по запросу: Сосна & Ель & Кедр?
Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
18
18
Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел тип. Так, например, 12&6 = 11002&01102 = 01002 = 4.
Для какого наибольшего неотрицательного целого числа А формула
х&А ≠ 0 → (х&10 = 0 → х& 3 ≠ 0)
тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)?
19
19
В программе используется одномерный целочисленный массив А с индексами от 0 до 9. Значения элементов равны 5, 6, 5, 8, 5, 4, 1, 2, 9, 6 соответственно, т.е. А[0] = 5, А[1] = 6 и т.д.
Определите значение переменной с после выполнения следующего фрагмента этой программы (записанного ниже на разных языках программирования).
Бейсик
с = 0
FOR i = 0 ТО 8
IF А(i) <= А(9) THEN
с = с + 1
t = А (i)
А (i) = А ( 9)
А (9) = t
ENDIF
NEXT i
Python
c = 0for i inrange(0,9):
if A[i] <= A[9]:
c = c + 1
t = A [ i ]
A [ i ] = A [ 9 ]
A [ 9 ] = t
Алгоритмический язык
с : = 0
нц для i от 0 до 8
если А[i] <= А[9] то
с : = с + 1
t : = А [ I ]
А[i] := А[9]
А[9] := t
все
кц
Паскаль
c : = 0;
for i := 0 to 8doif A[i] <= A[9] then
begin
c : = c + 1;
t : = A [ i ] ;
A[i] := A[9];
A[9] := t;
end;
Си
с = 0 ;
for (i = 0; i < 9;i++)
if (A[i] <= A[9])
{
c+ +;
t = A [ i ] ;
A [ i ] = A [ 9 ] ;
A[9] = t;
}
20
20
Ниже на пяти языках программирования записан алгоритм. Получив на вход число х, этот алгоритм печатает число М. Известно, что х > 40. Укажите наименьшее такое (т.е. большее 40) число х, при вводе которого алгоритм печатает 5.
Бейсик
DIM X, L, М AS INTEGER
INPUT X
L = X
M = 5IF L MOD 2=0 THEN
M = 24ENDIFWHILE L <> M
IF L > M THEN
L = L - M
ELSE
M = M - L
ENDIF
WEND
PRINT M
Python
х = int(input())
L = х
M = 5if L % 2 == 0:
M = 24while L != M:
if L > M:
L = L - M
else:
M = M - L
print(M)
Алгоритмический язык
алг
нач
цел х, L, М
ввод X
L : = х
М : = 5
если mod(L,2)=0
то
М := 24
все
нц пока L о М
если L > М
то
L := L - М
иначе
М := М - L
все
кц
вывод М
кон
Паскаль
var x, L, M: integer;
begin
readln(x);
L : = x;
M := 5;
if L mod 2=0 then
M := 24;
while L <> M doif L > M then
L := L - M
else
M := M - L;
writeln(M);
end.
Си
#iclude<stdio.h>voidmain(){
int x, L, M;
scanf ("%d", &x);
L = x;
M = 5;
if (L % 2 == 0)
M = 24;
while (L !=M) {
If (L > M)
L = L - M;
else
M = M - L;
}
printf("%d", M);
}
21
21
Напишите в ответе наибольшее значение входной переменной k, при котором программа выдаёт тот же ответ, что и при входном значении k = 49. Для Вашего удобства программа приведена на пяти языках программирования.
Бейсик
DIM К, I AS LONG
INPUT К
I = 1WHILE F(I) < G(К)
I = I + 1
WEND
PRINT I
FUNCTIONF(N)F = N * N * NENDFUNCTIONFUNCTIONG(N)G = 2*N + 1
ENDFUNCTION
Python
deff(n) :return n*n*n
defg(n) :return2*n+1
k = int (input())
i = 1while f(i) < g(k):
i+=1print (i)
Алгоритмический язык
алг
нач
цел i, k
ввод k
i : = 1
нц пока f(i) < g (k)
i : = i + 1
кц
вывод i
KOH
алг цел f(цел n)
нач
знач := n * n * n
кон
алг цел g(цел n)
нач
знач := 2*n + 1
кон
Паскаль
var
k, i : longint;
functionf(n: longint): longint;
begin
f : = n * n * n;
end;
functiong(n: longint): longint;
begin
g : = 2 * n + 1;
end;
begin
readln(k);
i := 1;
while f(i) < g(k) do
i : = i +1;
writeln(i)
end.
Си
#include <stdio.h>
long f (long n) {
return n * n * n;
}
long g (long n) {
return2*n + 1;
}
int main()
{
long k, i;
scant("%ld", &k) ;
i = 1;
while(f(i)<g(k))"
i + + ;
printf("%ld", i);
return 0;
{
22
22
Исполнитель Удвоитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
Прибавить 1
Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Удвоитель — это последовательность команд.
Сколько существует программ, для которых при исходном числе 3 результатом является число 25 и при этом траектория вычислений содержит число 11 и не содержит числа 20?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 112 при исходном числе 5 траектория будет состоять из чисел 6, 7, 14.
23
23
Сколько существует различных наборов значений логических переменных x1, х2, ... х6, y1, у2, ... у6, которые удовлетворяют всем перечисленным ниже условиям?
(x1 ∨ y1) → (x2 ∧ y2) = 0
(x2 ∨ y2) → (x2 ∧ y2) = 0
...
(x5 ∨ y5) → (x6 ∧ y6) = 0
В ответе не нужно перечислять все различные наборы значений переменных x1, х2, ... х6, у1, у2 ... у6, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.