СтатГрад: Тренировочная работа 28.11.2017 ИН10203
При выполнении заданий с кратким ответом впишите в поле для ответа цифру, которая соответствует номеру правильного ответа, или число, слово, последовательность букв (слов) или цифр. Ответ следует записывать без пробелов и каких-либо дополнительных символов. Дробную часть отделяйте от целой десятичной запятой. Единицы измерений писать не нужно.
Если вариант задан учителем, вы можете вписать или загрузить в систему ответы к заданиям с развернутым ответом. Учитель увидит результаты выполнения заданий с кратким ответом и сможет оценить загруженные ответы к заданиям с развернутым ответом. Выставленные учителем баллы отобразятся в вашей статистике.
Версия для печати и копирования в MS Word
Сколько нулей в двоичной записи десятичного числа 1021?
Ответ:
Логическая функция F задаётся выражением (x ∨ y) → (z ≡ x).
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.
Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z.
| Переменная 1 | Переменная 2 | Переменная 3 | Функция |
|---|---|---|---|
| ??? | ??? | ??? | F |
| 0 | 0 | 0 | |
| 0 | 0 |
В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
| Переменная 1 | Переменная 2 | Функция |
|---|---|---|
| ??? | ??? | F |
| 0 | 1 | 0 |
Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.
Ответ:
На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | |
| П1 | 3 | 7 | 4 | ||||
| П2 | 15 | 2 | |||||
| П3 | 3 | 6 | |||||
| П4 | 6 | 8 | 12 | ||||
| П5 | 7 | 15 | 8 | 9 | |||
| П6 | 4 | 9 | |||||
| П7 | 2 | 12 |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути из пункта А в пункт Д, если передвигаться можно только по указанным дорогам. В ответе укажите целое число – длину дороги в километрах.
ВНИМАНИЕ. Длины отрезков на схеме не отражают длины дорог.
Ответ:
Даны фрагменты двух таблиц из базы данных. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. На основании приведённых данных определите, у скольких детей в момент рождения матерям было меньше 30 полных лет. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц.
|
|
Ответ:
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, Г, Е, И, М, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
|
|
Укажите кратчайшее кодовое слово для
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Ответ:
Автомат получает на вход четырёхзначное число (число не может начинаться с нуля). По этому числу строится новое число по следующим правилам.
1. Складываются отдельно первая и вторая, вторая и третья, третья и четвёртая цифры заданного числа.
2. Наименьшая из полученных трёх сумм удаляется.
3. Оставшиеся две суммы записываются друг за другом в порядке неубывания без разделителей.
Пример. Исходное число: 1984. Суммы: 1 + 9 = 10, 9 + 8 = 17, 8 + 4 = 12.
Укажите наибольшее число, при обработке которого автомат выдаёт
Примечание. Если меньшие из трех сумм равны, то отбрасывают одну из них.
Ответ:
В ячейки электронной таблицы записаны числа, как показано на рисунке:
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| 1 | 10 | 20 | 30 | 40 | ||
| 2 | 1 | 11 | 21 | 31 | 41 | |
| 3 | 2 | 12 | 22 | 32 | 42 | |
| 4 | 3 | 13 | 23 | 33 | 43 | |
| 5 | 4 | 14 | 24 | 34 | 44 | |
| 6 | 5 | 15 | 25 | 35 | 45 |
В ячейке A5 записали формулу =$C6+E$3. После этого ячейку A5 скопировали в ячейку B1. Какое число будет показано в ячейке B1?
Примечание: знак $ обозначает абсолютную адресацию.
Ответ:
Запишите число, которое будет напечатано в результате выполнения следующей программы. Для Вашего удобства программа представлена на пяти языках программирования.
| Бейсик | Python |
|---|---|
DIM S, N AS INTEGER S = 22 N = 0 WHILE S < S*S S = S - 1 N = N + 3 WEND PRINT N
| s = 22 n = 0 while s < s*s: s = s - 1 n = n + 3 print(n)
|
| Паскаль | Алгоритмический язык |
var s, n: integer; begin s := 22; n := 0; while s < s*s do begin s := s - 1; n := n + 3 end; writeln(n) end.
| алг нач цел s, n n := 0 s := 22 нц пока s < s*s s := s - 1; n := n + 3 кц вывод n кон |
| Си++ | |
#include <iostream> using namespace std; int main() { int s = 22, n = 0; while (s < s*s) { s = s - 1; n = n + 3; } cout << n << endl; return 0; }
| |
Ответ:
Автоматическая фотокамера производит растровые изображения размером
Ответ:
Все трёхбуквенные слова, составленные из букв П, А, Р, У, С, записаны в алфавитном порядке и пронумерованы, начиная
1. ААА
2. ААП
3. ААР
4. ААС
5. ААУ
6. АПА
...
Под каким номером в списке идёт первое слово, которое начинается с
Ответ:
Ниже на пяти языках программирования записана рекурсивная функция F.
| Бейсик | Python |
|---|---|
FUNCTION F(n) IF n > 2 THEN F = F(n-2) + F(n\2) ELSE F = n END IF END FUNCTION
| def F(n): if n > 2: return F(n-2) + F(n//2) else: return n
|
| Паскаль | Алгоритмический язык |
function F(n: integer): integer; begin if n > 2 then F := F(n-2) + F(n div 2) else F := n end; | алг цел F(цел n) нач если n > 2 то знач := F(n-2) + F(div(n,2)) иначе знач := n все кон |
| Си | |
int F(int n) { if (n > 2) return F(n-2) + F(n/2); else return n; }
| |
Чему будет равно значение, вычисленное при выполнении вызова F(9)?
Ответ:
В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого места — нули.
Обычно маска записывается по тем же правилам, что и IP-адрес, — в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске.
Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0.
Для узла с IP-адресом 93.138.161.94 адрес сети равен 93.138.160.0. Какое наибольшее количество нулей может быть в двоичной записи маски?
Ответ:
При регистрации в компьютерной системе для каждого пользователя формируется индивидуальный идентификатор, состоящий из
Сколько байт нужно для хранения сведений о
Ответ:
Исполнитель Редактор получает на вход строку цифр и преобразует её.
Редактор может выполнять две команды, в обеих
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение
Если в строке нет вхождений
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно). Часть ИНАЧЕ может отсутствовать, в этом случае, если условие ложно, никакие действия не выполняются.
Какая строка получится в результате применения приведённой ниже программы к строке вида 1…12…2
НАЧАЛО
ПОКА нашлось (111) ИЛИ нашлось (222)
ЕСЛИ нашлось (111)
ТО заменить (111, 2)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (222)
ТО заменить (222, 1)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Ответ:
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П, Р, С, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Т, проходящих через город Л?
Ответ:
В какой системе счисления выполняется равенство 12 · 13 = 222?
В ответе укажите число – основание системы счисления.
Ответ:
В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&».
В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
| Запрос | Найдено страниц (в тыс.) |
|---|---|
| Жираф | 75 |
| Слон | 109 |
| Моська | 14 |
| Слон & Жираф | 33 |
| Жираф & Моська | 0 |
| Жираф | Слон | Моська | 153 |
Какое количество страниц (в тыс.) будет найдено по запросу Слон & Моська?
Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Ответ:
Сколько существует целых значений
тождественно истинна при любых целых
Ответ:
Представленный ниже фрагмент программы обрабатывает элементы фрагмента одномерного целочисленного массива A с индексами от 1 до 10. Перед началом выполнения данного фрагмента эти элементы фрагмента массива имели значения 2, 3, 5, 8, 10, 7, 4, 6, 12, 15 (т. е. A[1] = 2, A[2] = 3, …, A[10] = 15).
Определите значение переменной s после выполнения фрагмента этой программы (записанного ниже на разных языках программирования).
| Бейсик | Python |
|---|---|
n = 10 s = 0 FOR i = 2 TO n IF A(i-1) < A(i) THEN A(i) = A(i) + A(i-1) s = s + A(i) END IF NEXT i
| n = 10 s = 0 for i in range(2,n+1): if A[i-1] < A[i]: A[i] = A[i] + A[i-1] s = s + A[i]
|
| Паскаль | Алгоритмический язык |
n := 10; s := 0; for i:=2 to n do begin if A[i-1] < A[i] then begin A[i] := A[i] + A[i-1]; s := s + A[i] end end;
| n := 10 s := 0 нц для i от 2 до n если A[i-1] < A[i] то A[i] := A[i] + A[i-1] s := s + A[i] все кц |
| Си++ | |
n = 10; s = 0; for (i = 2; i <= n; ++i) { if (A[i-1] < A[i]) { A[i] = A[i] + A[i-1]; s = s + A[i]; } }
| |
Ответ:
Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: a и b. Укажите наибольшее из таких чисел x, при вводе которого алгоритм печатает сначала 2, а потом 4.
| Бейсик | Python |
|---|---|
DIM X, A, B AS INTEGER INPUT X A = 0: B = 0 WHILE X > 0 IF X MOD 2 = 0 THEN A = A + 1 ELSE B = B + X MOD 10 END IF X = X \ 10 WEND PRINT A PRINT B
| x = int(input()) a=0; b=0 while x > 0: if x%2 == 0: a += 1 else: b += x%10 x = x//10 print(a, b)
|
| Паскаль | Алгоритмический язык |
var x, a, b: longint; begin readln(x); a := 0; b := 0; while x > 0 do begin if x mod 2= 0 then a := a + 1 else b := b + x mod 10; x := x div 10; end; writeln(a); write(b); end.
| алг нач цел x, a, b ввод x a := 0; b := 0 нц пока x > 0 если mod(x,2)=0 то a := a+1 иначе b := b + mod(x,10) все x := div(x,10) кц вывод a, нс, b кон |
| Си++ | |
#include <iostream> using namespace std; int main() { int x, a, b; cin >> x; a = 0; b = 0; while (x > 0) { if (x%2 == 0) a += 1; else b += x%10; x = x / 10; } cout << a << endl << b << endl; return 0; }
| |
Ответ:
Напишите в ответе наибольшее значение входной переменной k, при котором программа выдаёт ответ 7. Для Вашего удобства программа приведена на пяти языках программирования.
| Бейсик | Python |
|---|---|
DIM K, I AS LONG INPUT K I = 20 WHILE F(I) > K I = I - 1 WEND PRINT I FUNCTION F(N) F = N * N * N END FUNCTION
| def f(n): return n * n * n k = int(input()) i = 20 while f(i) > k: i -= 1 print(i)
|
| Паскаль | Алгоритмический язык |
var k, i : longint; function f(n: longint): longint; begin f := n * n * n end; begin readln(k); i := 20; while f(i) > k do i := i-1; writeln(i) end.
| алг нач цел k, i ввод k i := 20 нц пока f(i) > k i := i - 1 кц вывод i кон алг цел f(цел n) нач знач := n * n * n кон |
| Си++ | |
#include <iostream> using namespace std; long f(long n) { return n * n * n; } int main() { long k, i; cin >> k; i = 20; while (f(i) > k) --i; cout << i; return 0; }
| |
Ответ:
Исполнитель Тренер преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера.
1. Прибавить 1.
2. Умножить на 2.
Первая команда увеличивает число на экране
Сколько существует программ, которые преобразуют исходное
Траектория должна содержать оба указанных числа. Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 212 при исходном
Ответ:
Сколько существует различных наборов значений логических переменных x1, x2, ... x8, y1, y2, ... y8, которые удовлетворяют всем перечисленным ниже условиям?
(x1→x2) ∧ (x1→y1) = 1
(x2→x3) ∧ (x2→y2) = 1
…
(x7→x8) ∧ (x7→y7) = 1
(x8→y8) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, ... x8, y1, y2, ... y8 при которых выполнена данная система равенств.
В качестве ответа Вам нужно указать количество таких наборов.
Ответ:
Факториалом натурального числа n (обозначается n!) называется произведение всех натуральных чисел от 1 до n. Например, 4! = 1 · 2 · 3 · 4 = 24.
Дано целое положительное число A. Необходимо найти минимальное натуральное K, для которого K! ≥ A.
Для решения этой задачи ученик написал программу, но, к сожалению, его программа неправильная.
Ниже эта программа для Вашего удобства приведена на пяти языках программирования.
| Бейсик | Python |
|---|---|
DIM A, K, F AS INTEGER INPUT A K = 0 F = 1 WHILE F <= A K = K + 1 F = F * K WEND PRINT K END
| a = int(input()) k = 0 f = 1 while f <= a: k += 1 f *= k print(k) |
| Паскаль | Алгоритмический язык |
var a, k, f: integer; begin read(a); k := 0; f := 1; while f <= a do begin k := k + 1; f := f * k end; writeln(k) end.
| алг нач цел a, k, f ввод a k := 0 f := 1 нц пока f <= a k := k + 1 f := f * k кц вывод k кон |
| Си++ | |
#include using namespace std; int main(){ int a, k, f; cin >> a; k = 0; f = 1; while (f <= a) { ++k; f *= k; } cout << k; return 0; } | |
Последовательно выполните следующее.
1. Напишите, что выведет эта программа при вводе A = 6.
2. Назовите минимальное A, большее 10, при котором программа выведет неверный ответ.
3. Найдите в программе все ошибки (их может быть одна или несколько).
Для каждой ошибки выпишите строку, в которой она допущена, и приведите эту же строку в исправленном виде.
Достаточно указать ошибки и способ их исправления для одного языка программирования.
Обратите внимание: Вам нужно исправить приведённую программу, а не написать свою. Вы можете только заменять ошибочные строки, но не можете удалять строки или добавлять новые. Заменять следует только ошибочные строки: за исправления, внесённые в строки, не содержащие ошибок, баллы будут снижаться.
На следующей странице вам будет предложено проверить их самостоятельно.
Дан массив, содержащий 2018 положительных целых чисел, не превышающих 30 000. Необходимо определить, сколько в этом массиве элементов, десятичная и восьмеричная запись которых содержит одинаковое количество цифр.
Напишите на одном из языков программирования программу для решения этой задачи. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из описанных.
| Бейсик | Python |
|---|---|
CONST N=2018 DIM A(N) AS INTEGER DIM B, I, K, L, M AS INTEGER FOR I = 1 TO N INPUT A(I) NEXT I … END
| # кроме уже указанных # допускается использование # целочисленных переменных # k, b, l, m a = [] N = 2018 for i in range(0, N): a.append(int(input())) …
|
| Паскаль | Алгоритмический язык |
const N=2018; var a: array [1..N] of integer; b, i, k, l, m: integer; begin for i:=1 to N do readln(a[i]); … end.
| алг нач цел N=2018 целтаб a[1:N] цел b, i, k, l, m нц для i от 1 до N ввод a[i] кц … кон |
| Си++ | |
#include <iostream> using namespace std; const int N=2018; int main(){ int a[N]; int b, i, k, l, m; for (i=0; i … return 0; } | |
В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например, Free Pascal 2.6). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии.
На следующей странице вам будет предложено проверить их самостоятельно.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
увеличить количество камней в куче в два раза или увеличить количество камней в куче в три раза.
Например, имея кучу из 10 камней, за один ход можно получить кучу из 20 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче превышает 61. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 62 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 61.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы следующего стратегии игрока, которые не являются для него безусловно выигрышными.
Выполните следующие задания.
Задание 1. Назовите все значения S, при которых Петя может выиграть первым ходом, причём у Пети есть ровно один выигрывающий ход.
Задание 2. Назовите все значения S, при которых Ваня может выиграть первым ходом, независимо от того, каким будет первый ход Пети. Опишите выигрышную стратегию Вани для этих значений S.
Задание 3. Назовите все значения S, при которых Петя не может выиграть первым ходом, но может выиграть вторым ходом независимо от того, как будет играть Ваня, причём в начальной позиции у Пети есть ровно один выигрывающий ход. Опишите выигрышную стратегию Пети для всех этих значений. Постройте (в виде рисунка или таблицы) дерево всех партий, возможных при этой стратегии для одного произвольного значения S. На рёбрах дерева указывайте, кто делает ход, в узлах – количество камней в позиции. Дерево должно содержать только те партии, которые возможны при реализации выигрышной стратегии Пети.
На следующей странице вам будет предложено проверить их самостоятельно.
Дан набор из N целых положительных чисел. Из этих чисел формируются все возможные пары (парой считаются два элемента, которые находятся на разных местах в наборе, порядок чисел в паре не учитывается), в каждой паре вычисляется сумма элементов. Необходимо определить количество пар, для которых полученная сумма делится на 7.
Напишите эффективную по времени и по памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксическихошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, – 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла.
Вы можете сдать одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000).
В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример входных данных:
5
1
3
6
11
1
Пример выходных данных для приведённого выше примера входных данных:
3
Из 5 чисел можно составить 10 пар. В данном случае у трёх пар сумма делится на 7: 1 + 6, 1 + 6 (в наборе две единицы, поэтому пару 1 + 6 можно составить двумя способами), 3 + 11.
На следующей странице вам будет предложено проверить их самостоятельно.