АСП2/К1 2020

Задаци на страници предмета.

Први колоквијум 2020. године одржан је 3. новембра 2020.

1. задатак

Поставка

(10п) Посматра се табела целобројних кључева дата на слици. Приказати изглед табеле у сваком кораку приликом претраге на скуп кључева {25, 40, 25, 40} методом транспозиције као и методом пребацивања на почетак и у оба случаја израчунати просечан број поређења приликом претраживања.

Стање низа из поставке задатка

12	7	3	27	25	78	98	21	22	40	51

Решење

Транспозиција:

Стање низа након претраге на кључ 25

12	7	3	25	27	78	98	21	22	40	51

Број поређења у овом кораку - 5

Стање низа након претраге на кључ 40

12	7	3	25	27	78	98	21	40	22	51

Број поређења у овом кораку - 10

Стање низа након претраге на кључ 25

12	7	25	3	27	78	98	21	40	22	51

Број поређења у овом кораку - 4

Стање низа након претраге на кључ 40

12	7	25	3	27	78	98	40	21	22	51

Број поређења у овом кораку - 9

Просечан број поређења: $\frac{5+10+4+9}{4} = \frac{28}{4} = 7$

Пребацивање на почетак:

Стање низа након претраге на кључ 25

25	12	7	3	27	78	98	21	22	40	51

Број поређења у овом кораку - 5

Стање низа након претраге на кључ 40

40	25	12	7	3	27	78	98	21	22	51

Број поређења у овом кораку - 10

Стање низа након претраге на кључ 25

25	40	12	7	3	27	78	98	21	22	51

Број поређења у овом кораку - 2

Стање низа након претраге на кључ 40

40	25	12	7	3	27	78	98	21	22	51

Број поређења у овом кораку - 2

Просечан број поређења: $\frac{5+10+2+2}{4} = \frac{19}{4} = 4.75$

2. задатак

Поставка

(10п) Укратко објаснити и илустровати примерима случајеве проналажења чвора претходника по инордер поретку за задати чвор у стаблу бинарног претраживања.

Решење

Уколико чвор има лево подстабло, његов претходник је најдешњи потомак његовог левог сина, а уколико нема лево подстабло, његов претходник је његов најнижи предак чији је десни син такође његов предак. У примеру испод, претходник од 3 је 1, а претходник од 6 је 5.

Пример

3. задатак

Поставка

(15п) У АВЛ стабло са слике се редом умећу кључеви 44, 72, 19, 22, 21, 5 и 1, након чега се уклањају кључеви 23 и 39. Приказати стања стабла након сваке промене.

Почетно стање

Решење

После свих уметања

После свих брисања

4. задатак

Поставка

(15п) Нека је дата велика, уређена једноструко уланчана листа лист коју треба претражити на задати кључ кеy. Као помоћна структура, расположив је индекс индеx величине сизе.

1. (5п) Објаснити и нацртати структуру индекса и начин повезивања са листом која се претражује.
2. (10п) Написати у псеудокоду имплементацију функције за секвенцијалну претрагу листе лист уз коришћење индекса индеx на кључ кеy.

Решење

1. Структура индеx представља низ чворова који садрже информационо поље са вредношћу пронађених кључева и поље-показивач на тај пронађен кључ. Структура индеx се чува уређеном.

Структура индекса

1. ФИНД КЕY ЛИСТ(лист, индеx, сизе, кеy)

int i=0;
for(i<size)
    if(key<index[i].info) Node poc = index[i];
    if(key>=index[i].info) break;
    while(poc!=nil)
        if(key==poc.info) return poc;
        if(key>poc.info) return nil;
        poc=poc.next
    end_while
end_for

5. задатак

Поставка

(10п) Нека се у дато самоподешавајуће стабло убацује кључ 30, након чега се бришу кључеви 29 и 61, и на крају се убацује кључ 33. Приказати изглед стабла након сваког извршеног корака при уметању и брисању.

Почетно стање

Решење

У стаблу се већ налази кључ 33, тако да он не треба да се убацује.

• 

  Након уметања кључа 30.

• 

  Након брисања кључа 29.

• 

  Након брисања кључа 61.

6. задатак

Поставка

(15п) Написати у псеудокоду имплементацију функције која у датом бинарном стаблу на чији корен указује показивач роот проналази и исписује адресе коренова свих подстабала која задовољавају особине стабла бинарног претраживања. Дозвољено је уводити додатна поља у чвор стабла која могу олакшати имплементацију функције.

Решење

У овом решењу су коришћене функције иницијализације, брисања и додавања у ред, као и функција провере да ли је ред празан, које су подразумевано знање са АСП1 и као такве могу да се користе без посебног псеудокода за те операције.

PRINT ALL BST(root)
Q.insert(root)
while(!Q.empty())
    tr = Q.delete
    CHECK(tr)
    if(tr.bst) print(tr)
    if(tr.left) Q.insert(tr.left)
    if(tr.right) Q.insert(tr.right)
end_while

CHECK(root)
Q.insert(root, -∞,+∞)
while(!Q.empty())
    {tr,min.max} = Q.delete
    if(tr.left)
        if(tr.left.info < min || tr.left.info > tr.info)
            root.bst = 0
            return
        end_if
        Q.insert(tr.left,min,tr.info)
    end_if
    if(tr.right)
        if(tr.right.info < key || tr.right.info > tr.info)
            root.bst = 0
            return
        end_if
    end_if
end_while
root.bst=1
return

7. задатак

Поставка

(15п) Нека се посматра једна строго монотоно растућа функција ф(x). На пример,$x^3 - 3x^2 +6x - 1$ или $3^x$. Коришћењем стратегије бинарног претраживања, написати у псеудокоду итеративну имплементацију функције која проналази вредност н за коју функција ф(x) постаје позитивна први пут, уколико важи да је x ≥ 0. Кратко објаснити поступак.

Решење

У решењу се користи бинарно претраживање у табели непознате величине.

FIND FIRST POSITIVE(f)
int high=1;
while(f(high)<0)
    high *= 2;
end_while
int low = high/2;
while(low<=high)
    mid = (high+low)/2;
    if(f(mid)>=0 && f(mid-1)<0) return mid;
    if(f(mid)>0) high = mid-1;
    else low=mid+1;
end_while

8. задатак

Поставка

(10п) Анализа перформанси стабла бинарног претраживања.

1. (5п) Формално дефинисати и објаснити просечан број поређења Сн приликом успешног претраживања и просечан број поређења Ун приликом неуспешног претраживања у стаблу бинарног претраживања које је настало уметањем н чворова у произвољном поретку.
2. (5п) Извести и кратко објаснити везу између Сн и Ун који су дефинисани под а). Одговор илустровати сликом.

Решење

1. Сн можемо представити као $Sn = (PI + n)/n$, јер има за 1 више поређења него чворова, а Ун можемо представити као $Un = PE/n_{e} = PE/(n+1)$.
2. $PE = PI + 2n$

$Un(n+1) - 2n = PI$

$Sn = (Un \frac{n+1}{n}) - 1$