АСП2/К1 2009

Prvi kolokvijum 2009. godine održan je 29. oktobra 2009. Postavka zadataka je dostupna sa stranice predmeta.

1. zadatak

Postavka

(20p)

1. Objasniti strategiju binarnog pretraživanja. Koji su preduslovi primene binarne pretrage? Koje uslove mora da zadovolji struktura podataka nad kojom se primenjuje binarno pretraživanje da bi primena bila efikasna?
2. Nad tabelom u koju su umetnuti ključevi 2, 18, 33, 14, 25, 5, 7, 12, 11, 16, 20, 22, 26 se vrši pretraga na ključeve 14, 7 i 18 primenom strategije binarnog pretraživanja. Odrediti prosečan broj poređenja vrednosti ključeva.
3. Napisati na jeziku C (ili C++) funkciju koja u zadatom nizu celih brojeva zadate dužine traži zadati celobrojni ključ. Funkcija vraća indeks pod kojim je ključ nađen u nizu ili -1 u slučaju neuspešne pretrage.

Rešenje

1. Strategija binarnog pretraživanja se zasniva na nalaženju medijane, a zatim polovljenju intervala pretraživanja. Postupak se ponavla sve dok se ne nađe traženi ključ ili se zaključi da se on ne nalazi u nizu. Preduslovi su da je niz uređen i da je moguć linearan pristup. Struktura mora biti linearna.
2. Pri pretrazi na ključ 14 vrše se 4 poređenja, kao i pri pretrazi na ključ 18. Pri pretrazi na ključ 7 vrše se 2 poređenja, što nam u proseku daje $\frac{10}{3} = 3.33$ poređenja.
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. zadatak

Postavka

(30p) U AVL stablo prikazano na slici se redom umeću sledeći ključevi: 20, 21, 19, 7, 10, 12, 14. Nakon umetanja se redom brišu ključevi: 22, 15, 18. Prikazati izgled stabla nakon svake od navedenih izmena. Izračunati prosečan broj pristupa stablu prilikom uspešne pretrage nakon svih umetanja i u konačnom stanju. Napomena: prilikom brisanja ključeva, koristiti sledbenike.

Stablo iz postavke zadatka

Rešenje

Stablo nakon svih umetanja

Stablo nakon svih brisanja

Nakon svih umetanja: $PI = \sum R_{i} \cdot n_{i} = 3\cdot5 + 4\cdot4 + 4\cdot3 + 5 = 15+16+12+5=48$, pa je $S_{n} = \frac{48}{14} = 3.43$

Nakon svih brisanja: $PI = \sum R_{i} \cdot n_{i} = 33$, pa je $S_{n} = \frac{33}{11} = 3$.

3. zadatak

Postavka

(20p) Dati pseudokod i objasniti algoritam za istovremeno sekvencijalno pretraživanje uređenog niza na više ključeva. Kolika je složenost algoritma?

Rešenje

Pretraživanje ide od početka niza K sa prvim ključem iz S dok se ne pronađe (i njegova pozicija zapamti u P) ili do prve veće vrednosti. Pretraživanje na sledeći ključ iz S počinje tamo gde se sa pretraživanjem na prethodni ključ stalo, pa se zato niz K prolazi samo jednom. Niz K je rastuće uređeni niz sa n ključeva koji se pretražuje na pojavu m ključeva zadatih u nizu S. Izlaz predstavlja vektor P gde se na poziciji koja odgovara ključu u nizu S nalazi pozicija ključa u nizu K, ako se on tamo pronađe, ili vrednost 0 ako se ne pronađe. Složenost ovog algoritma je O(n) za slučaj kada je m << n.

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. zadatak

Postavka

(30p) Pitanja:

1. Kolike su performanse pretraživanja u stablu binarnog pretraživanja u najboljem, srednjem i najgorem slučaju i diskutovati implikacije.
2. Definisati Fibonacci-jeva stabla i navesti njihove glavne osobine.
3. Zašto se uvode 2-3 stabla? Objasniti njihovu organizaciju i glavne osobine.

Rešenje

1. Složenost je u funkciji visine - O(h). U najboljem slučaju h = log(n), a u najgorem h = n.
2. Fibonačijevo stablo je najgori slučaj AVL stabla, tj. stablo najveće visine za određen broj čvorova. Broj čvorova u Fibonačijevom stablu visine h je $n_{h} = n_{h-1} + n_{h-2} + 1$. Svi čvorovi imaju balans 1. Brisanje bilo kog čvora smanjuje visinu stabla. Svaki koren će biti Fibonačijev broj.
3. 2-3 stabla se uvode da bi se osigurala balansiranost, pa su sve operacije O(log(n)). Glavno svojstvo je postojanje 3-čvorova, koji imaju levo, desno i srednje podstablo, i time se omogućava da svi listovi budu na istom nivou. 3-čvorovi imaju dva ključa, K1 i K2 i u zavisnosti od intervala pripadanja određujemo podstablo.