Образец_билета_очное_2022-23 (обновленный). Образец билета государственного квалификационного экзамена
 Скачать 245.01 Kb.
|
|
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 } 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, k0}, минимальная цепочка «ab». |