Предварительный вариант билета ГОС экзамена 09.03.01 - «Информатика и вычислительная техника»

В представленном файле подробно разобраны задания предварительного варианта билета государственного экзамена по направлению 09.03.01 -
«Информатика и вычислительная техника», профиль “Программное обеспечение средств вычислительной техники
и автоматизированных систем” (заочная форма обучения с применением дистанционных технологий)
Пример билета за 2022 год

1. (2 балла) Дан бернуллиевский источник с алфавитом K = {a, b, c, d, e, f}. Вероятности символов источника: p(a)=0.1, p(b)=0.05, p(c)=0.05, p(d)=0.05, p(e)= 0.05, p(f)=0.7. Построить код Хаффмана для данного источника и определить его избыточность R (как разницу между средней длиной кодового слова SD и энтропией H). Вычисления выполнять с 3 знаками после запятой.

Ответ: {0.7, 0.1, 0.05, 0.05, 0.05, 0.05}; SD=1.700 H= 1.557 R=0.143


2. (3 балла) Проанализировать работу программы и написать последовательность символов, выводимых на консоль.
#include <windows.h>
#include <stdio.h>
unsigned long idA, idB;
void A ()
{
MSG msg;
PeekMessage (&msg, 0, 0, 0, PM_NOREMOVE), Sleep (1);
putchar ('a');
PostThreadMessage (idB, WM_USER, 'b', 0);
putchar ('d');
PostThreadMessage (idB, WM_USER+1, 'c', 0);
GetMessage (&msg, 0, 0, 0);
putchar (msg.lParam);
}
void B (char c)
{
MSG msg;
PeekMessage (&msg, 0, 0, 0, PM_NOREMOVE), Sleep (1);
GetMessage (&msg, 0, WM_USER + 1, WM_USER + 1);
putchar (msg.wParam);
PostThreadMessage (idA, WM_USER, c, c);
}
int main ()
{
putchar ('e');
CreateThread (0, 0, (LPTHREAD_START_ROUTINE) A, 0, 0, &idA);
CreateThread (0, 0, (LPTHREAD_START_ROUTINE) B, (LPVOID) 'f', 0, &idB);
Sleep (1000);
putchar ('g');
return 0;
}

Ответ: eadcfg


3. (2 балла) Для предиката p на Прологе описаны правила:
p([_,_],L,L):-!.
p([X|L1],L2,L):–p(L1,[X,X|L2],L).
Какое значение получит L после следующего обращения к этому предикату p([2,5,6,3,4],[],L)?

Ответ: [6,6,5,5,2,2]


4. (2 балла) Определить высоту случайного дерева поиска (СДП), построенного для последовательности данных: 15 2 1 8 10 8 11 4 3 6.
Высота дерева определяется по количеству ребер.

Ответ: 4.


5. (3 балла) Указать, что выведет на экран программа для заданных входных данных.
#include <iostream>
#include <cmath>
#include <cstdlib>
int fx(int **pts, int n)
{
int res=0;
for(int i=0; i<n; ++i)
res+=(pts[(i+1)%n][0]-pts[i][0])*(pts[(i+1)%n][1]+pts[i][1]);
return res;
}
int main()
{
int n, **pts;
std::cin >> n;
pts=new int*[n];
for(int i=0; i<n; ++i)
{
pts[i]=new int[2];
std::cin >> pts[i][0] >> pts[i][1];
}
std::cout << abs(fx(pts,n))/2.0;
}
Входные данные:
5
1 1
3 1
3 3
2 4
1 3

Ответ: 5
Полезная ссылка:
http://www.cplusplus.com/reference/clibrary/cstdio/printf/
Пояснение: Данная программа вычисляет площадь введенного в неё многоугольника по известной формуле:


6. (2 балла) Для шифра Шамира с параметрами P= 29, Ca= 13, Cb = 17, найти недостающие параметры и описать передачу сообщения m=10.

Ответ: Da = 13, Db = 5; x1 = 26, x2 = 27, x3 = 15, x4 = 10.


7. (2 балла) Построить электронную подпись RSA c параметрами P = 17, Q = 5 , D = 47 для сообщения m, значение хеш-функции которого равно 13.

Ответ: C = 15, N = 85; s = 72.


8. (2 балла) Построить хэш-таблицу размера m=7 методом линейных проб для данных 3, 2, 8, 9, 7, 5.
Начальная хэш-таблица пустая. Для построения таблицы использовать хэш-функцию x = h mod m. Определить количество коллизий.

Ответ: 2 коллизии, хэш-таблица:
Хэш-номер 0 1 2 3 4 5 6
данные 7 8 2 3 9 5


9. (1 балл) Построить индексный массив, упорядочивающий данные по возрастанию (нумерация в массиве начинается с 1): 15 2 1 8 10 8 11 4 3 6.

Ответ: 3 2 9 8 10 4 6 5 7 1

Пример выполнения заданий из билета государственного экзамена образца 2022 года. Направление - ИВТ (информатика и вычислительная техника)