Билет государственного экзамена по направлению 09.01.03 «Информатика и вычислительная техника» профиль «Программное обеспечение средств вычислительной техники и автоматизированных систем»

Вариант ЗД192002

Билет
государственного экзамена по направлению 09.01.03 «Информатика и вычислительная техника» профиль «Программное обеспечение средств вычислительной техники и автоматизированных систем»

1. (3 балла). Проанализировать работу программы и написать последовательность символов выводимых на консоль.
#include <windows.h>
#include <stdio.h>
unsigned long idA, idB;
void A (char c)
 {
 MSG msg;
 PeekMessage (&msg, 0, 0, 0, PM_NOOREMOVE), Sleep (1);
 putchar (`a`);
 PostThreadMessage (idB, WM_USER, `b`, c);
 putchar (`d`);
 GetMessage (&msg, 0, 0, 0);
 putchar (msg.wParam);
 }

void B (char c)
 {
 MSG msg:
 PeekMessage (&msg, 0, 0, 0, PM_NOREMOVE), Sleep (1);
 GetMessage (&msg 0, 0, 0);
 putchar (msg.wParam);
 PostThreadMessage (idA, WM_USER, c, 0);
 putchar (msg.1Param);
 }

int main ()
 {
 CreateThread (0, 0, (LPTHREAD_START_ROUTINE) A, (LPVOID) `x`, 0, &idA);
 CreateThread (0, 0, (LPTHREAD_START_ROUTINE) B, (LPVOID) `f`, 0, &idB);
 Sleep (1000);
 putchar (`g`);
 return 0;
 }
2. (2 балла) Дан бернуллиевский источник с алфавитом К = {a,b,c,d,e,f}.
Вероятности символов источника: p(a)=0.05 p(b)=0.25 p(c)=0.25 p(d)=0.2 p(e)=0.15 p(f)=0.1
 Построить код Хаффмана для данного источника и определить его избыточность R (как разницу между средней длинной кодового слова SD и энтропией H). Вычисления выполнять с 3 знаками после запятой.
3. (2 балла) Для предиката p на Прологе описаны правила:
p(X, [Y], [Y,X,X,Y] ) : - !.
p(X, [X|L], [X|L] ) : - !.
p(X, [_|L],Z) :-p (X,L,Z).
 Какое значение получит Z после обращения к этому предикату
p(0, [-1, 4, 2, 3, 5], Z) ?

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

5. (2 балла) Вычислить открытые ключи YA, YB, и общий секретный ключ ZAB, для системы Диффи-Хеллмана с параметрами p = 31, g = 3, XA = 6, XB = 10.

6. (2 балла) Для пользователя ГОСТ Р34.10-94 с открытым параметрами q = 11, p = 67, a = 9 и секретным ключом x = 4 построить подпись для сообщения m с хеш-функцией h(m) = 4 при k = 6.

7. (3 балла) Указать, что выведет на экран программа для заданных входных данных.

#include <iostream>
#include <cstdlib>

int fx (int arg1, int arg2)
{
 retutn arg2?fx (arg2,arg1%arg2) :arg1;
}
int main ()
{
 int n, *mass;
std: : cin >> n;
mass=new int[n];
for (int i=0; i<n; ++i)
 std: : cin >> mass[i];
in tans=0;
for (int i=0; i<n; ++i)
 for (int j=i+1; j<n; ++j)
  if (fx(mass[i],mass[j])>1)
   ++ans;
std: : cout << ans;
 }
 Входные данные:
 8
 2 5 17 34 7 3 6 22

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

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

Решенный билет ГОС экзамена. Дата сдачи - декабрь 2019.
Оценка "отлично".