АСП2/К1П 2012

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

1. задатак

Поставка

(30п) Предложити адекватну структуру података и детаљно навести услове њене употребе, а затим скицирати алгоритам за ефикасну претрагу на више целобројних кључева над неопадајуће уређеном табелом. Сматрати да у табели не постоје дуплирани кључеви нити да се више пута врши претрага над истим кључем.

Решење

Претраживање иде од почетка низа К са првим кључем из С док се не пронађе (и његова позиција запамти у П) или до прве веће вредности. Претраживање на следећи кључ из С почиње тамо где се са претраживањем на претходни кључ стало, па се зато низ К пролази само једном. Низ К је растуће уређени низ са н кључева који се претражује на појаву м кључева задатих у низу С. Излаз представља вектор П где се на позицији која одговара кључу у низу С налази позиција кључа у низу К, ако се он тамо пронађе, или вредност 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;

2. задатак

Поставка

(20п) У АВЛ стабло се редом умећу следећи целобројни кључеви: 13, 32, 14, 28, 15, 35, 44, 47, 22, 30, 24, 19, 20, а затим се бришу кључеви 15, 30, 28, 24. Нацртати изглед стабла након сваке од наведених измена. Израчунати просечан број приступа стаблу за успешну претрагу након свих уметања и у коначном стању.

Решење

Уколико желите да задатак проверите корак по корак, то можете урадити на линку.

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

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

Након свих уметања: $S_{n} = \frac{5 + 5\cdot4 + 4\cdot3 + 2\cdot2 + 1}{13} = \frac{42}{13} = 3.23$

Након свих брисања: $S_{n} = \frac{2\cdot4 + 4\cdot3 + 2\cdot2 + 1}{9} = \frac{25}{9} = 2.78$

3. задатак

Поставка

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

Решење

Уколико чвор има десног сина, онда је његов следбеник најлевљи чвор у десном подстаблу, а ако нема, онда је његов следбеник најближи предак чији је леви син такође предак задатог чвора.

BST-SUCC(k)
if(right(k) != nil)
    p = right(k);
    while(left(p) != nil) p = left(p);
    return p;
end_if
p = parent(k), s = k;
while(p != nil and right(p) = s)
    s = p;
    p = parent(p);
end_while
return s;

4. задатак

Поставка

(30п) Питања:

1. Објаснити како и зашто метод транспозије оптимизује секвенцијално претраживање.
2. Ако се стабло бинарног претраживања користи као приоритетни ред, објаснити како изгедају операције ПQ_ИНСЕРТ и ПQ_МИН_ДЕЛЕТЕ. Колика је временска сложеност ових операција?
3. Прецизно дефинисати оптимално стабло бинарног претраживања.

Решење

1. Метод транспозиције оптимизује секвенцијално претраживање тако што сваки пут када се тражени елемент нађе, он замени место са елементом лево од себе и тако се прибллижава почетку низа. Тиме се обезбеђује да су они елементи којима се чешће приступа ближе почетку, па пошто се секвенцијално приступа, и само време приступа тим елементима је скраћено.
3. Оптимално стабло бинарног претраживања је оно стабло чија је цена најмања, где цену дефинишемо као: $C = \sum_{i}^{m-n} p_{i}(h_{i} + 1) + \sum_{i}^{m-n} q_{i}h_{i}$, где су Пи вероватноће приступа кључевима Кн...Км, а Qи вероватноће приступа екстерним чворовима. Особина на којој се заснива алгоритам за налажење оптималног стабла бинарног претраживања је да су сва подстабла оптималног стабла претраживања такође оптимална.