Онлайн-помощь «“Программное обеспечение средств вычислительной техники и автоматизированных систем”»,
«Информатика и вычислительная техника» в Санкт-Петербурге

Предварительный вариант билета государственного экзамена по направлению 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 знаками после запятой. Ответ: 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; } Ответ: 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)? Ответ: 4. (2 балла) Определить высоту случайного дерева поиска (СДП), построенного для последовательности данных: 15 2 1 8 10 8 11 4 3 6. Высота дерева определяется по количеству ребер. Ответ: 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 Ответ: 6. (2 балла) Для шифра Шамира с параметрами P= 29, Ca= 13, Cb = 17, найти недостающие параметры и описать передачу сообщения m=10. Ответ: 7. (2 балла) Построить электронную подпись RSA c параметрами P = 17, Q = 5 , D = 47 для сообщения m, значение хеш-функции которого равно 13. Ответ: 8. (2 балла) Построить хэш-таблицу размера m=7 методом линейных проб для данных 3, 2, 8, 9, 7, 5. Начальная хэш-таблица пустая. Для построения таблицы использовать хэш-функцию x = h mod m. Определить количество коллизий. Ответ: 9. (1 балл) Построить индексный массив, упорядочивающий данные по возрастанию (нумерация в массиве начинается с 1): 15 2 1 8 10 8 11 4 3 6. Ответ: