АСП2/К1 2009

Први колоквијум 2009. године одржан је 29. октобра 2009. Поставка задатака је доступна са странице предмета.

1. задатак

Поставка

(20п)

1. Објаснити стратегију бинарног претраживања. Који су предуслови примене бинарне претраге? Које услове мора да задовољи структура података над којом се примењује бинарно претраживање да би примена била ефикасна?
2. Над табелом у коју су уметнути кључеви 2, 18, 33, 14, 25, 5, 7, 12, 11, 16, 20, 22, 26 се врши претрага на кључеве 14, 7 и 18 применом стратегије бинарног претраживања. Одредити просечан број поређења вредности кључева.
3. Написати на језику C (или C++) функцију која у задатом низу целих бројева задате дужине тражи задати целобројни кључ. Функција враћа индекс под којим је кључ нађен у низу или -1 у случају неуспешне претраге.

Решење

1. Стратегија бинарног претраживања се заснива на налажењу медијане, а затим половљењу интервала претраживања. Поступак се понавла све док се не нађе тражени кључ или се закључи да се он не налази у низу. Предуслови су да је низ уређен и да је могућ линеаран приступ. Структура мора бити линеарна.
2. При претрази на кључ 14 врше се 4 поређења, као и при претрази на кључ 18. При претрази на кључ 7 врше се 2 поређења, што нам у просеку даје $\frac{10}{3} = 3.33$ поређења.

3. BIN(arr, key, n)
   high = n;
   low = 1;
   while(high>=low)
       mid = (low+high)/2;
       if(arr[mid]=key) return mid;
       if(arr[mid]<key) low = mid+1;
       else high = mid-1;
   end_while
   return -1;

2. задатак

Поставка

(30п) У АВЛ стабло приказано на слици се редом умећу следећи кључеви: 20, 21, 19, 7, 10, 12, 14. Након уметања се редом бришу кључеви: 22, 15, 18. Приказати изглед стабла након сваке од наведених измена. Израчунати просечан број приступа стаблу приликом успешне претраге након свих уметања и у коначном стању. Напомена: приликом брисања кључева, користити следбенике.

Стабло из поставке задатка

Решење

Стабло након свих уметања

Стабло након свих брисања

Након свих уметања: $PI = \sum R_{i} \cdot n_{i} = 3\cdot5 + 4\cdot4 + 4\cdot3 + 5 = 15+16+12+5=48$, па је $S_{n} = \frac{48}{14} = 3.43$

Након свих брисања: $PI = \sum R_{i} \cdot n_{i} = 33$, па је $S_{n} = \frac{33}{11} = 3$.

3. задатак

Поставка

(20п) Дати псеудокод и објаснити алгоритам за истовремено секвенцијално претраживање уређеног низа на више кључева. Колика је сложеност алгоритма?

Решење

Претраживање иде од почетка низа К са првим кључем из С док се не пронађе (и његова позиција запамти у П) или до прве веће вредности. Претраживање на следећи кључ из С почиње тамо где се са претраживањем на претходни кључ стало, па се зато низ К пролази само једном. Низ К је растуће уређени низ са н кључева који се претражује на појаву м кључева задатих у низу С. Излаз представља вектор П где се на позицији која одговара кључу у низу С налази позиција кључа у низу К, ако се он тамо пронађе, или вредност 0 ако се не пронађе. Сложеност овог алгоритма је О(н) за случај када је м << н.

SEQ-SEARCH-MUL(K,S)
for(int i=0;i<m;i++) P[i] = 0;
i=j=1;
while(i<=n) and (j<=m)
    while(i<n) and (S[j] > K[i]) i++;
    if(S[j] = K[i]) P[j] = i;
    j++;
end_while
return P;

4. задатак

Поставка

(30п) Питања:

1. Колике су перформансе претраживања у стаблу бинарног претраживања у најбољем, средњем и најгорем случају и дискутовати импликације.
2. Дефинисати Фибонацци-јева стабла и навести њихове главне особине.
3. Зашто се уводе 2-3 стабла? Објаснити њихову организацију и главне особине.

Решење

1. Сложеност је у функцији висине - О(х). У најбољем случају х = лог(н), а у најгорем х = н.
2. Фибоначијево стабло је најгори случај АВЛ стабла, тј. стабло највеће висине за одређен број чворова. Број чворова у Фибоначијевом стаблу висине х је $n_{h} = n_{h-1} + n_{h-2} + 1$. Сви чворови имају баланс 1. Брисање било ког чвора смањује висину стабла. Сваки корен ће бити Фибоначијев број.
3. 2-3 стабла се уводе да би се осигурала балансираност, па су све операције О(лог(н)). Главно својство је постојање 3-чворова, који имају лево, десно и средње подстабло, и тиме се омогућава да сви листови буду на истом нивоу. 3-чворови имају два кључа, К1 и К2 и у зависности од интервала припадања одређујемо подстабло.