Решенный Билет ГОС экзамена (09.03.01 Информатика и вычислительная техника, профиль: Программное обеспечение средств вычислительной техники и автоматизированных систем») + читай описание

В архиве 3 файла
1)билет с госэкзамена 2020 года с решением,
2)старые задачи с госэкзамена с решением
3)теория по многим темам
--------------------------------------------------------------------
БИЛЕТ
государственного экзамена по направлению
09.03.01 «Информатика и вычислительная техника»,
профиль «Программное обеспечение средств вычислительной техники и автоматизированных систем»
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= 17, Ca= 5, Cb = 7, найти недостающие параметры и описать передачу сообщения m=6.
Ответ: Da = 13, Db = 7; x1 = 7, x2 = 12, x3 = 14, x4 = 6.
7. (2 балла) Построить электронную подпись RSA c параметрами P = 5, Q = 11 , D = 13 для сообщения m, значение хеш-функции которого равно 6.
Ответ: C = 37, N = 55; s = 41.
4. (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 4 5 



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

Год сдачи 2020
Одной задачи нет.
Оценка 5