АСП2/К1 2020
Prvi kolokvijum 2020. godine održan je 3. novembra 2020.
1. zadatak
Postavka
(10p) Posmatra se tabela celobrojnih ključeva data na slici. Prikazati izgled tabele u svakom koraku prilikom pretrage na skup ključeva {25, 40, 25, 40} metodom transpozicije kao i metodom prebacivanja na početak i u oba slučaja izračunati prosečan broj poređenja prilikom pretraživanja.
| 12 | 7 | 3 | 27 | 25 | 78 | 98 | 21 | 22 | 40 | 51 |
|---|
Rešenje
Transpozicija:
| 12 | 7 | 3 | 25 | 27 | 78 | 98 | 21 | 22 | 40 | 51 |
|---|
Broj poređenja u ovom koraku - 5
| 12 | 7 | 3 | 25 | 27 | 78 | 98 | 21 | 40 | 22 | 51 |
|---|
Broj poređenja u ovom koraku - 10
| 12 | 7 | 25 | 3 | 27 | 78 | 98 | 21 | 40 | 22 | 51 |
|---|
Broj poređenja u ovom koraku - 4
| 12 | 7 | 25 | 3 | 27 | 78 | 98 | 40 | 21 | 22 | 51 |
|---|
Broj poređenja u ovom koraku - 9
Prosečan broj poređenja:
Prebacivanje na početak:
| 25 | 12 | 7 | 3 | 27 | 78 | 98 | 21 | 22 | 40 | 51 |
|---|
Broj poređenja u ovom koraku - 5
| 40 | 25 | 12 | 7 | 3 | 27 | 78 | 98 | 21 | 22 | 51 |
|---|
Broj poređenja u ovom koraku - 10
| 25 | 40 | 12 | 7 | 3 | 27 | 78 | 98 | 21 | 22 | 51 |
|---|
Broj poređenja u ovom koraku - 2
| 40 | 25 | 12 | 7 | 3 | 27 | 78 | 98 | 21 | 22 | 51 |
|---|
Broj poređenja u ovom koraku - 2
Prosečan broj poređenja:
2. zadatak
Postavka
(10p) Ukratko objasniti i ilustrovati primerima slučajeve pronalaženja čvora prethodnika po inorder poretku za zadati čvor u stablu binarnog pretraživanja.
Rešenje
Ukoliko čvor ima levo podstablo, njegov prethodnik je najdešnji potomak njegovog levog sina, a ukoliko nema levo podstablo, njegov prethodnik je njegov najniži predak čiji je desni sin takođe njegov predak. U primeru ispod, prethodnik od 3 je 1, a prethodnik od 6 je 5.
3. zadatak
Postavka
(15p) U AVL stablo sa slike se redom umeću ključevi 44, 72, 19, 22, 21, 5 i 1, nakon čega se uklanjaju ključevi 23 i 39. Prikazati stanja stabla nakon svake promene.[1]
Rešenje
4. zadatak
Postavka
(15p) Neka je data velika, uređena jednostruko ulančana lista list koju treba pretražiti na zadati ključ key. Kao pomoćna struktura, raspoloživ je indeks index veličine size.
- (5p) Objasniti i nacrtati strukturu indeksa i način povezivanja sa listom koja se pretražuje.
- (10p) Napisati u pseudokodu implementaciju funkcije za sekvencijalnu pretragu liste list uz korišćenje indeksa index na ključ key.
Rešenje
- Struktura index predstavlja niz čvorova koji sadrže informaciono polje sa vrednošću pronađenih ključeva i polje-pokazivač na taj pronađen ključ. Struktura index se čuva uređenom.
FIND KEY LIST(list, index, size, key) 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. zadatak
Postavka
(10p) Neka se u dato samopodešavajuće stablo ubacuje ključ 30, nakon čega se brišu ključevi 29 i 61, i na kraju se ubacuje ključ 33. Prikazati izgled stabla nakon svakog izvršenog koraka pri umetanju i brisanju.
Rešenje
U stablu se već nalazi ključ 33, tako da on ne treba da se ubacuje.
6. zadatak
Postavka
(15p) Napisati u pseudokodu implementaciju funkcije koja u datom binarnom stablu na čiji koren ukazuje pokazivač root pronalazi i ispisuje adrese korenova svih podstabala koja zadovoljavaju osobine stabla binarnog pretraživanja. Dozvoljeno je uvoditi dodatna polja u čvor stabla koja mogu olakšati implementaciju funkcije.
Rešenje
U ovom rešenju su korišćene funkcije inicijalizacije, brisanja i dodavanja u red, kao i funkcija provere da li je red prazan, koje su podrazumevano znanje sa ASP1 i kao takve mogu da se koriste bez posebnog pseudokoda za te operacije.
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_whileCHECK(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
return7. zadatak
Postavka
(15p) Neka se posmatra jedna strogo monotono rastuća funkcija f(x). Na primer, ili . Korišćenjem strategije binarnog pretraživanja, napisati u pseudokodu iterativnu implementaciju funkcije koja pronalazi vrednost n za koju funkcija f(x) postaje pozitivna prvi put, ukoliko važi da je x ≥ 0. Kratko objasniti postupak.
Rešenje
U rešenju se koristi binarno pretraživanje u tabeli nepoznate veličine.
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_while8. zadatak
Postavka
(10p) Analiza performansi stabla binarnog pretraživanja.
- (5p) Formalno definisati i objasniti prosečan broj poređenja Sn prilikom uspešnog pretraživanja i prosečan broj poređenja Un prilikom neuspešnog pretraživanja u stablu binarnog pretraživanja koje je nastalo umetanjem n čvorova u proizvoljnom poretku.
- (5p) Izvesti i kratko objasniti vezu između Sn i Un koji su definisani pod a). Odgovor ilustrovati slikom.
Rešenje
- Sn možemo predstaviti kao , jer ima za 1 više poređenja nego čvorova, a Un možemo predstaviti kao .
Napomene
- ↑ Prepisivač ovog roka je zaboravio kako se postupno radi umetanje i brisanje, tako da su dostupna rešenja samo posle svih umetanja i posle svih brisanja (u prevodu nisam radio postupno)