Тест №3

1 Дадена е думата МАТЕМАТИКА. Отбележете съответствията
на срещащите се букви и крайни редици от 0 и 1, които
са оптимални кодове от алгоритъма на Хофман.

+ К-0001 И-0000 М-10 А-01 Т-11 Е-001

- К-001 И-01 М-11 А-0000 Т-10 Е-0001


2 Отбележете правилно запълнена хеш-таблица чрез отворено адресиране,
ако данните с ключове
125, 224, 335, 123  се въвеждат последователно в масива.
Хеш-функциите са дадени за всеки конкретен случай.

+ h(d)=d%10, (-,-,-,123,224,125,335,-,-,-)

- h(d)=(d-25)/100, (-,123,125,224,335,-, ...)


3 Дадени са следните структури:
struct A { int x; int xx[2]; } a[2];
struct B { int y; A   yy[2]; } b[2];
Отбележете правилните имена на променливи, свързани с дадените структури.

+ a[0]

- A[1].xx[0]


4 Дадена е следната дефиниция обекти от тип клас:
class Test {
 private:
   int m, n;
 public:
   Test(int mm=0, int nn=0) { setmn(mm,nn); }
   void setmn(int mm, int nn) { m=mm; n=nn; }
   int getm()   { return m; }
   void print() { cout << n << m; }
} t1, t2;
Отбележете правилните оператори за дефиниране и работа с обекти
от този клас в главната функция main().

+ Test t(1,2);

- cout<<t1.n;


5 Отбележете верните дефиниции и твърдения относно сортиране на масиви:

+ При сортиране чрез пряка селекция броят на сравненията не зависи от
  началния ред на ключовете.

- Множеството, за което ще се прилага топологично сортиране, трябва да
  бъде линейно наредено.


6 Дадени са следните дефиниции:
int i=10, *pj, *pk=new int(1);
Отбележете формално верните оператори.

+ pj=new int;

- *pk=new i;


7 Даден е двусвързан списък, състоящ се от 3 елемента.
Полето nt сочи към следващ елемент, а полето pv --
предишен елемент от списъка.
struct Item { Item *nt, *pv; int k; };
Item *h;
като h е указател за началото на списъка.
Отбележете верните твърдения.

+ (h->nt)->nt е адресът на последния елемент от списъка.

- (h->nt).pv е адресът на първия елемент от списъка.


8 Дадени са следните рекурсивни функции:
int s(int n)
{ if (n) return (n+m(n-1));
  else return 1; }
int m(int n)
{ if (n) return (n*s(n-1));
  else return 0; }
Отбележете верните твърдения.

+ s(1) е 1

- s(2) е 2


9 Даден е аритметичния израз a*(b+c)*d-e*f и е представен като двоично дърво.
Дадени са метод за обхождане и редица от символи.
Отбележете в кои случаи (под)редицата може да се генерира от
дадения вид обхождане на двоичното дърво.

+  длк: bc

-  дкл: ef


10 Дадена е следната частична наредба:
a<b, a<c, a<d, b<d, c<e.
Отбележете редицата, която може да се генерира от алгоритъма за
топологично сортиране.

+ abcde

- aecbd

11 Дадени са два масива A и B. Отбележете случаите,
когато B е индексен масив на сортирания масив A.
(Ще считаме, че първият елемент на масива A има индекс 1 и
най-малкият елемент е първи в сортирания масив).

+ A={1,3,5,7,9},B={1,2,3,4,5};

- A={2,1,0,-1,-2},B={4,3,4,2,1};