Файл: Образец билета государственного квалификационного экзамена.pdf

1
Образец билета
государственного квалификационного экзамена
по направлению 09.03.01 «Информатика и вычислительная техника»,
профиль «Программное обеспечение средств вычислительной техники
и автоматизированных систем» (очная форма обучения)
1. (3 балла) Указать, что выведет на экран программа для заданных входных данных:
#include
#include
#include
int fx(int **pts, int n)
{
int res=0;
for(int i=0; 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
{
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/
Пояснение:
Данная
программа
вычисляет
площадь
введенного
в
неё
многоугольника по известной формуле:
2. (1 балл) Построить индексный массив, упорядочивающий данные по возрастанию (нумерация в массиве начинается с 1):
15 2 1 8 10 8 11 4 3 6.
Ответ: 3 2 9 8 10 4 6 5 7 1.

2
3. (3 балла) Для приведенной ниже программы определить последовательность символов, выводимых на стандартный вывод.
#include
#include
#include
#include
#include void* T (char * cptr) { wait (0), write (1, cptr, 1), *cptr = 'N';
} int main () { char c = 'B'; int p = fork (); if (p > 0) { int pp = p; c--; p = fork (); if (p > 0) { write (1, &c, 1); int tid; pthread_create (&tid, 0, T, &c); c = 'E'; pthread_join (tid, 0); write (1, &c, 1);
}
else { delay (1000), write (1, &c, 1); int con = ConnectAttach (0, pp, 1, 0, 0);
MsgSend (con, "C", 1, &c, 1); write (1, &c, 1);
}
} else { int chan = ChannelCreate (0); // chan = 1 int rcvid = MsgReceive (chan, &c, 1, 0); write (1, &c, 1);
MsgReply (rcvid, 0, "H", 1);
} return 0;
}
Ответ: AACHEN
4. (2 балла) Определить высоту случайного дерева поиска (СДП), построенного для последовательности данных:
15 2 1 8 10 8 11 4 3 6.
Ответ: 4.
5. (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
6. (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]
7. (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

3
8. (2 балла) Для шифра Шамира с параметрами P= 29, Ca= 13, Cb = 17, найти недостающие параметры и описать передачу сообщения m=10.
Ответ: Da =13, Db = 5; x1 = 26, x2 = 27, x3 = 15, x4 = 10.
9. (2 балла) Построить электронную подпись RSA c параметрами P = 17, Q = 5 , D = 47 для сообщения
m, значение хеш-функции которого равно 13.
Ответ: C = 15, N = 85; s = 72.
10. (3 балла) Задан детерминированный автомат с магазинной памятью (ДМПА) Р, работающий с опустошением стека. Определить и записать язык L(P), распознаваемый этим автоматом; записать минимальную допустимую цепочку этого языка.
Р({q
0
,q
1
,q
2
,q
3
},{a,b,c},{Z,c},q
0
,Z,,{q
3
}), функция переходов  имеет вид:
1) (q
0
,c,Z) = {(q
0
,cZ)}
2) (q
0
,c,c) = {(q
0
,cc)}
3) (q
0
,a,c) = {(q
1
,c)}
4) (q
1
,a,c) = {(q
2
,c)}
5) (q
2
,a,c) = {(q
1
,)}
6) (q
1
,b,Z) = {(q
3
,Z)}
7) (q
3
,b,Z) = {(q
3
,Z)}
8) (q
0
,a,Z) = {(q
1
,Z)}
9) (q
3
,,Z) = {(q
3
,)}
Ответ: L(P)={
=с n
а
2n+1
b k+1
, n
0, k0}, минимальная цепочка «ab».