Предварительный вариант билета государственного экзамена по направлению 09. 03. 01 Информатика и вычислительная техника
 Скачать 191.04 Kb.
|
|
Предварительный вариант билета государственного экзамена по направлению 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 #include { 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 #include #include { int res=0; for(int i=0; i { int n, **pts; std::cin >> n; pts=new int*[n]; for(int i=0; i } 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. 8. (2 балла) Построить хэш-таблицу размера m=7 методом линейных проб для данных 3, 2, 8, 9, 7, 5. Начальная хэш-таблица пустая. Для построения таблицы использовать хэш-функцию x = h mod m. Определить количество коллизий. Ответ: 2 коллизии, хэш-таблица: 9. (1 балл) Построить индексный массив, упорядочивающий данные по возрастанию (нумерация в массиве начинается с 1): 15 2 1 8 10 8 11 4 3 6. Ответ: 3 2 9 8 10 4 6 5 7 1 Хэш-номер 0 1 2 3 4 5 6 данные 7 8 2 3 9 5 |