АСП2/К3 2018

1. задатак

Поставка

Приказати изглед бинарног хипа након уклањања минималног кључа и након уметања кључева 9 и 30.

         5
       /   \
     10      7
    /  \    / \
   47  32  12 31
  /
54

Решење

Након уклањања минималног кључа:

      7
    /   \
  10      12
 /  \    /  \
47  32  54  31

Након уметања кључева 9 и 30:

       7
     /   \
    9     12
   / \   /  \
  10 32 54  31
 /  \
47  30

2. задатак

Поставка

Написати итеративну имплементацију следећег алгоритма хеширања. За хеширање се користе две хеш функције, х₁(К) и х₂(К), док се за разрешавање колизија користи секундарна хеш функција г(к). Над кључем К који се убацује у табелу се примењују и функција х₁(К) и х₂(К), а као улаз се користи резултат функције за коју се добије мање колизија. У случају једнаког броја колизија, користи се функција х₁(К). Потребно је реализовати операције уметања и претраге.

Решење

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

INSERT(table, K)
adr1 = adr1_init = h1(K)
adr2 = adr2_init = h2(K)
repeat
    if table[adr1] = empty then
        table[adr1] = K
        return
    else
        adr1 = adr1 + g(K)
    end_if
    if table[adr2] = empty then
        table[adr2] = K
        return
    else
        adr2 = adr2 + g(K)
    end_if
until (adr1 = adr1_init) or (adr2 = adr2_init)
ERROR(Tabela je puna)

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

SEARCH(table, K)
adr1 = adr1_init = h1(K)
adr2 = adr2_init = h2(K)
repeat
    if table[adr1] = K then
        return true
    else if table[adr1] ≠ empty then
        adr1 = adr1 + g(K)
    end_if
    if table[adr2] = K then
        return true
    else if table[adr2] ≠ empty then
        adr2 = adr2 + g(K)
    end_if
until (adr1 = adr1_init) or (adr2 = adr2_init) or ((table[adr1] = empty) and (table[adr2] = empty))
return false

3. задатак

Поставка

Дата је секвенца кључева: 169, 84, 99, 6, 61, 84, 9, 96, 158, 42, 495, 46, 223. Приказати рад схелл сорт алгоритма по корацима. Навести коришћену секвенцу инкремената и образложити избор.

Решење

Инкременти су изабрани као у решењу шестог задатка са трећег колоквијума 2020. године.

Инкремент	0	1	2	3	4	5	6	7	8	9	10	11	12
Почетак	169	84	99	6	61	84	9	96	158	42	495	46	223
7	96	84	42	6	46	84	9	169	158	99	495	61	223
5	84	9	42	6	46	96	84	169	158	99	495	84	223
3	6	9	42	61	46	96	84	169	84	99	495	158	223
2	6	9	42	61	46	96	84	99	84	158	223	169	495
1	6	9	42	46	61	84	96	84	99	158	169	223	495
1	6	9	42	46	61	84	84	96	99	158	169	223	495

4. задатак

Поставка

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

for i:=1 to n-1 do
    for j:=n-1 downto 1 do
        if arr[j]>arr[j+1] then
            b:=arr[j]; arr[j]:=arr[j+1]; arr[j+1]:=b;
        end_if
     end_for
end_for

Решење

Код овог алгоритма јесте највећи проблем то што n-1 пута ради итерацију кроз низ, када је то потребно радити само док се не деси да није било ниједне замене у унутрашњој петљи. Други проблем јесте непотребан пролазак од краја до почетка низа, када је пролазак од почетка до краја потенцијално ефикаснији због кеш меморије. Такође, није потребно пролазити кроз сортирани део приликом замене елемената.

BUBBLE SORT REVISITED(arr, n)
i = 1
repeat
    broj_zamena = 0
    for i = 1 to n-i do
        if arr[i] > arr[i+1] then
            arr[i] ↔ arr[i+1]
            broj_zamena = broj_zamena + 1
        end_if
    end_for
    i = i + 1
until broj_zamena = 0

5. задатак

Поставка

Подаци се смештају у хеш табелу са 7 улаза применом хеш функције х_п(К) = К мод 7. За разрешавање колизија се користи метода двоструког хеширања са секундарном хеш функцијом х_с(К) = 4 + К мод 3. Одредити просечан број приступа приликом неуспешног тражења и вероватноћу попуњавања празних улаза, под претпоставком да су сви кључеви једнако вероватни.

Табела из поставке задатка
0	14
1
2	11
3	24
4	18
5
6	13

Решење

Испитни низови
0	1	2
0	0	0
4	5	6
1	3	5
5	1	4
2	6	3
6	4	2
3	2	1

Просечан број неуспешних приступа: $P_nu = 1 + \frac{5}{7} + \frac{5 \cdot 4}{7 \cdot 6} + \frac{5 \cdot 4 \cdot 3}{7 \cdot 6 \cdot 5} + \frac{5 \cdot 4 \cdot 3 \cdot 2}{7 \cdot 6 \cdot 5 \cdot 4} + \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3} =$
$= 1 + \frac{5}{7} + \frac{10}{21} + \frac{2}{7} + \frac{1}{7} + \frac{1}{21} = \frac{8}{3} \approx 2.67$
Вероватноћа попуњавања:
- 1: $\frac{1}{3} \left(\frac{6}{7} + \frac{2}{7} + \frac{4}{7}\right) = \frac{4}{7}$
- 5: $\frac{1}{3} \left(\frac{1}{7} + \frac{5}{7} + \frac{3}{7}\right) = \frac{3}{7}$

6. задатак

Поставка

Написати у псеудокоду функцију за уклањање минималног кључа у биномном хипу и његову накнадну реорганизацију. Није потребно спровести потенцијално спајање стабала након уклањања чвора са минималним кључем. Биномни хип представљен помоћу објекта класе БинХеап која садржи уланчану листу објеката БинТрее који представљају појединачна биномна стабла. Листа је уређена растуће по степену стабла. Биномно стабло се састоји од чворова представљених објектима класе БинНоде. Функција као аргумент прима објекат класе БинХеап. У наставку је дат списак метода које су на располагању, њихове повратне вредности и класе објеката за које их треба позвати.

Метода	Повратна вредност	Објекат класе
гетФирст	показивач на почетак листе шуме биномних стабала	БинХеап
финдМин	показивач на биномно стабло у чијем корену је минимални кључ	БинХеап
гетОрдер	ред стабла	БинТрее
сетОрдер	нема	БинТрее
гетРоот	показивач на корен биномног стабла	БинТрее
гетНумОфЦхилдрен	број потомака чвора биномног стабла	БинНоде
гетЦхилдАтПос(индеx)	показивач на чвор који је потомак објекта БинНоде на позицији индеx	БинНоде

Решење

Следеће претпоставке су усвојене при имплементацији:

getFirst враћа променљиву референцу на лвредност до почетка уланчане листе, како бисмо могли да ажурирамо тај почетак
getChildAtPos исто враћа променљиву референцу на лвредност. Ово је како бисмо децу тренутног чвора могли да поставимо на нил, како не би била уништена приликом деалокације стабла (претпостављамо да постоји функција ФРЕЕТРЕЕ која то ради, слично ФРЕЕНОДЕ)
Постоји функција ГЕТТРЕЕ која само алоцира стабло и као корен поставља свој први аргумент
Уланчана листа је једноструко уланчана, па накнадно морамо дохватати елементе листе које садрже стабло са минималним кореном након позивања findMin
Уланчана листа у хипу садржи поље неxт које показује до следећег чвора уланчане листе и поље валуе које показује на БинТрее објекат, и све операције као што су се користиле на АСП1 су подржане

REMOVE MIN KEY(binheap)
first_node = binheap.getFirst()
if first_node = nil then
    return
end_if
min_tree = binheap.getMin()
prev_node = nil
curr_node = first_node
while value(curr_node) ≠ min_tree do
    prev_node = curr_node
    curr_node = next(curr_node)
end_while
next(prev_node) = next(curr_node)
root = min_tree.getRoot()
for i = 1 to root.getNumOfChildren() do
    child = root.getChildAtPos(i)
    tree = GETTREE(child)
    tree.setOrder(child.getNumOfChildren())
    INSERT_TREE(binheap, tree)
    root.getChildAtPos(i) = nil
end_for
FREETREE(min_tree)
FREENODE(curr_node)

INSERT TREE(binheap, bintree)
curr = binheap.getFirst()
prev = nil
while curr ≠ nil do
    if value(curr).getOrder() ≥ bintree.getOrder() then
        if prev = nil then
            binheap.getFirst() = GETNODE
            value(binheap.getFirst()) = bintree
            next(binheap.getFirst()) = curr
        else
            next(prev) = GETNODE
            value(next(prev)) = bintree
            next(next(prev)) = curr
        end_if
        return
    end_if
    prev = curr
    curr = next(curr)
end_while
next(prev) = GETNODE
value(next(prev)) = bintree
next(next(prev)) = nil

7. задатак

Поставка

Подаци се смештају у хеш табелу са 8 улаза применом хеш функције по методу дељења. За разрешавање колизија се користи метода случајног претраживања (ц = 3). Приказати процес разрешавања колизије и генерисати испитне низове за кључеве 21 и 18. Објаснити да ли код овог метода у општем случају долази до примарног и секундарног груписања и зашто.

Решење

Пошто се користи метода случајног претраживања, морамо генерисати случајни низ за генерисање испитног низа:

    011 = 3
*2  110 = 6
*2 1100
-8  100
⊕3  111 = 7
*2 1110
-8  110
⊕3  101 = 5
*2 1010
-8  010
⊕3  001 = 1
*2  010 = 2
*2  100 = 4
*2 1000
-8  000
⊕3  011 ...

Испитни низови за 21 и 18
21	18
5	2
0	5
3	0
4	1
2	7
6	3
7	4
1	6

Процес разрешавања колизије:

21 % 8 = 5
Ако је улаз 5 заузет: (5 + 3) % 8 = 0
Ако је улаз 0 заузет: (5 + 6) % 8 = 3
итд.

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

8. задатак

Поставка

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

Решење

АСП2/К3 2018

Садржај

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

5. задатак

Поставка

Решење

6. задатак

Поставка

Решење

7. задатак

Поставка

Решење

8. задатак

Поставка

Решење

Мени за навигацију