Решение задач с разбором к госэкзамену: Информатика и вычислительная техника

Задачи подобраны из разных вариантов! Смотрите внимательно! Также есть скриншоты, которые я не вставил текстом. - смотрите в приложении. К задачам также даны отсылки к методичкам и учебникам, где можно почитать подробно.

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

1. (2 балла) Вариант 1 Дан бернуллиевский источник с алфавитом 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.(2 балла). Дан бернулиевский источник с алфавитом K = {a, b, c, d, e, f}. Вероятности символов источника:
p(a)=0.1 p(b)=0.1 p(c)=0.1 p(d)=0.1 p(e)=0.1 p(f)=0.5.
Построить код Хаффмана для данного источника и определить его избыточность R (как разницу между средней длиной кодового слова SD и энтропией H).

2. (3 балла)Вариант1 Проанализировать работу программы и написать последовательность символов, выводимых на консоль.
Методичка по нитям
#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;
}
Ответ: eadcfg

2. Вариант2 (3 балла). Проанализировать работу программы и написать последовательность символов, выводимых на консоль.

#include <windows.h>
#include <stdio.h>

unsigned long idA, idB;
void A (char c)
(
HANDLE chan;
char str [2];
unsigned long n;
chan = CreateNamedPipe (“\\\\.\\pipe\\ppp”, PIPE ACCESS_DUPLEX,
 PIPE_TYPE_MESSAGE | PIPE_READMODE_MESSAGE, 1, 4, 4, 0, 0);
Sleep (100);
TransactNamedPipe (chan, &c, 1, str, 2, &n, 0);
putchar (str[0]), putchar (str[1]);
)

void B (char c)
(
HANDLE chan;
char str [2] = (‘a’, ‘b’);
unsigned long n;
chan = CreateFile (“\\\\.\\pipe\\ppp”, GENERIC_READ | GENERIC_ERITE,
0, 0, OPEN_EXISTING, 0, 0);
ReadFile (chan, str, 1, &n, 0);
putchar (str[0]), putchar (str[1]);
str[1] = c;
WriteFile (chan, str, 2, &n, 0);
)

int main ()
(
CreateThread (0, 0, (LPTHREAD_START_ROUTINE) A, (LPVOID) ‘c’, 0, &idA);
CreateThread (0, 0, (LPTHREAD_START_ROUTINE) B, (LPVOID) ‘d’, 0, &idB);
Sleep (1000);
return 0;
)

3. (2 балла) Вариант1Для предиката p на Прологе описаны правила:
p([_,_],L,L):-!.
p([X|L1],L2,L):–p(L1,[X,X|L2],L).
Какое значение получит L после следующего обращения к этому предикату
p([2,5,6,3,4],[],L)?

3. (2 балла).Вариант2 Для предиката p на Прологе описаны правила:
p(_,[],[]):-!.
p(X,[X|L],L):-!.
p(X, [_|L],Z):-p(X,L,Z).
Какое значение получит Z после следующего обращения к этому предикату p(2, [3,6,2,7,9,1],Z)?

Вариант 3
.р (_,[ ],[ ] ): - !
p([X,[X|L1],[X,X|L2]): - p(X,L1,L2),!
P (X,[Z|L1],[Z|L2]); - p(X,L1,L2)

L=? p(2,[1,2,3,2,3],L)

Вариант4.
P([_],L2,L2); - !
P([X|L1],L2,[X|L]); - p(L1,L2,L),!

L=? p([1,2,3],[1,2],L)


Вариант 5.
p([_,_],L,L); - !
p([X|L1],L2,L); - p(L1,[X|L2],L)

L=7 p([2,5,6,3,4},[],L)

Вариант6.
p(_,_[X],[X]); - !
p(X,Y,[X|L1],[Y|L2]); - p(X,Y,L1,L2),!
P(X,Y,[Z|L1],[Z|L2]); - p(X,Y,L1,L2)

L =? ,p(1,0,[1,5,1,0,1],L)

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

4. Вариант2(2 балла). Определить высоту случайного дерева поиска (СДП), построенного для последовательности данных:
17 18 2 6 10 15 1 2 10 16

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 балла)Вариант1 Для шифра Шамира с параметрами P= 17, Ca= 5, Cb = 7, найти недостающие параметры и описать передачу сообщения m=6.

6. (2 балла). Вариант2 Для шифра Эль-Гамаля с параметрами p=31, g=3, cB=10, k=5 найти недостающие параметры и описать процесс передачи сообщения m=15 пользователю B.

7. (2 балла) Вариант1 Построить электронную подпись RSA c параметрами P = 5, Q = 11 , D = 13 для сообщения m, значение хеш-функции которого равно 6.

7. (2 балла). Вариант2 Построить подпись RSA для сообщения m с хэш-функцией h(m)=55 при следующих параметрах пользователя: P=11, Q=13, С=11.

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

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

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

10. (2 балла) Вариант1 Оптимальным образом расставить скобки при перемножении матриц
М1[2x5], M2[5x7], M3[7x3], М4[3x8], M5[8x4].
Какова трудоемкость умножения при оптимальной расстановке скобок?

10.(2 балла).Вариант2 Оптимальным образом расставить скобки при перемножении матриц M1[2x6], M2[6x7], M3[7x4], M4[4x3], M5[3x5].
Какова трудоемкость умножения при оптимальной расстановке скобок?

10.Вариант3 M1[7x3], M2[3x8], M3[8x3], M4[3x5], M5[5x2].

10.Вариант4 M1[5x4], M2[4x2], M3[2x6], M4[6x9], M5[9x3].

11Указать, что выдаст на экран следующая программа:

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <conio.h>
using namespace std;
const int MAXL=40, N=5;
struct node{
 char *name;
 bool vo;
 node *next;
 node(char *_name, bool _vo):vo(_vo){
  name=new char[MAXL];
  strcpy(name,_name);
  next=NULL;
 }
 ~node(){
  delete [] name;
 }
};
node *head=NULL, *tail=NULL;
void add(char *name, bool vo){
 node *tmp=new node(name,vo);
 if(tail!=NULL){
  tail=tail->next=tmp;
 }else head=tail=tmp;
}
void get(char *&name, bool &vo){
 node *prev=NULL, *cur=head;
 while(cur->next!=NULL){
  prev=cur;
  cur=cur->next;
 }
 strcpy(name,cur->name);
 vo=cur->vo;
 if(prev!=NULL){
  delete cur;
  prev->next=NULL;
 }else{
  delete cur;
  head=tail=NULL;
 }
}
void handling(char **_names, bool *voarr, int pos){
 char **names=new char*[N];
 for(int j=0; j<N; ++j){
  names[j]=_names[j];
  if(j==pos) continue;
  if(voarr[j]){
   char *tmp=new char[MAXL];
 
 strcpy(tmp,names[j]);
   strcat(tmp,"s");
   names[j]=tmp;
   voarr[j]=true && (voarr[j] || !voarr[j]);
  }else if(strlen(names[j])<=9){
   names[j]="------";
voarr[j]=(voarr[j]^true)^true;
  }
 }
}
char *boolToStr(bool b){
 if(b)
  return "TRUE";
 return "FALSE";
}
int main(){
 char **names=new char*[N];
 for(int i=0; i<N; ++i)
  names[i]=new char[MAXL];
 bool voarr[N];
 char *name=new char[MAXL];
 bool vo;
 system("cls");
 strcpy(name,"Lebedev"), vo=true;
 add(name,vo);
 strcat(name,"skaya"), vo=0;
 add(name,vo);
 strcpy(name,"Vasilyev"), vo=vo||false;
 add(name,!vo);
 strcpy(name,"Vainstein"), vo=true^true; add(name,vo);
 strcpy(name,"Kirjanova"), vo=!(1-0);
 add(name,vo);
 strcpy(name,"Sanoylov"), vo=true;
 add(name,!vo);
 strcpy(name,"Dozenko"), vo=true;
 add(name,vo);
 get(name,vo);
 get(name,vo);
 for(node *cur=head; cur!=NULL; cur=cur->next)
  printf("%s - %s\n",cur->name,boolToStr(cur->vo)); printf("\n");
 for(int i=0; i<N; ++i)
{
  get(name,vo);
  strcpy(names[i],name);
  voarr[i]=vo;
 }
 for(int i=0; i<N; ++i)
  printf("%s - %s\n",names[i],boolToStr(voarr[i])); handling(names,voarr,3);
 printf("\nAfter handling:\n\n");
 for(int i=0; i<N; ++i)
  printf("%s - %s\n",names[i],boolToStr(voarr[i]));
}

2019 г.
Всего 21 страница
Задачи реальные!
Это стоит того, чтобы не завалить ГОС экзамен!