АСП2/К1П 2012

Popravni prvi kolokvijum 2012. godine održan je 9. januara 2012. Postavka zadataka je dostupna sa stranice predmeta.

1. zadatak

Postavka

(30p) Predložiti adekvatnu strukturu podataka i detaljno navesti uslove njene upotrebe, a zatim skicirati algoritam za efikasnu pretragu na više celobrojnih ključeva nad neopadajuće uređenom tabelom. Smatrati da u tabeli ne postoje duplirani ključevi niti da se više puta vrši pretraga nad istim ključem.

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;

2. zadatak

Postavka

(20p) U AVL stablo se redom umeću sledeći celobrojni ključevi: 13, 32, 14, 28, 15, 35, 44, 47, 22, 30, 24, 19, 20, a zatim se brišu ključevi 15, 30, 28, 24. Nacrtati izgled stabla nakon svake od navedenih izmena. Izračunati prosečan broj pristupa stablu za uspešnu pretragu nakon svih umetanja i u konačnom stanju.

Rešenje

Ukoliko želite da zadatak proverite korak po korak, to možete uraditi na linku.

Stablo nakon svih umetanja

Stablo nakon svih brisanja

Nakon svih umetanja: $S_{n} = \frac{5 + 5\cdot4 + 4\cdot3 + 2\cdot2 + 1}{13} = \frac{42}{13} = 3.23$

Nakon svih brisanja: $S_{n} = \frac{2\cdot4 + 4\cdot3 + 2\cdot2 + 1}{9} = \frac{25}{9} = 2.78$

3. zadatak

Postavka

(20p) Dati pseudokod i objasniti algoritam za određivanje sledbenika proizvoljno zadatog čvora u stablu binarnog pretraživanja.

Rešenje

Ukoliko čvor ima desnog sina, onda je njegov sledbenik najlevlji čvor u desnom podstablu, a ako nema, onda je njegov sledbenik najbliži predak čiji je levi sin takođe predak zadatog čvora.

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

Postavka

(30p) Pitanja:

1. Objasniti kako i zašto metod transpozije optimizuje sekvencijalno pretraživanje.
2. Ako se stablo binarnog pretraživanja koristi kao prioritetni red, objasniti kako izgedaju operacije PQ_INSERT i PQ_MIN_DELETE. Kolika je vremenska složenost ovih operacija?
3. Precizno definisati optimalno stablo binarnog pretraživanja.

Rešenje

1. Metod transpozicije optimizuje sekvencijalno pretraživanje tako što svaki put kada se traženi element nađe, on zameni mesto sa elementom levo od sebe i tako se priblližava početku niza. Time se obezbeđuje da su oni elementi kojima se češće pristupa bliže početku, pa pošto se sekvencijalno pristupa, i samo vreme pristupa tim elementima je skraćeno.
3. Optimalno stablo binarnog pretraživanja je ono stablo čija je cena najmanja, gde cenu definišemo kao: $C = \sum_{i}^{m-n} p_{i}(h_{i} + 1) + \sum_{i}^{m-n} q_{i}h_{i}$, gde su Pi verovatnoće pristupa ključevima Kn...Km, a Qi verovatnoće pristupa eksternim čvorovima. Osobina na kojoj se zasniva algoritam za nalaženje optimalnog stabla binarnog pretraživanja je da su sva podstabla optimalnog stabla pretraživanja takođe optimalna.