АСП2/К1 2020

Zadaci na stranici predmeta.

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.

Stanje niza iz postavke zadatka

12	7	3	27	25	78	98	21	22	40	51

Rešenje

Transpozicija:

Stanje niza nakon pretrage na ključ 25

12	7	3	25	27	78	98	21	22	40	51

Broj poređenja u ovom koraku - 5

Stanje niza nakon pretrage na ključ 40

12	7	3	25	27	78	98	21	40	22	51

Broj poređenja u ovom koraku - 10

Stanje niza nakon pretrage na ključ 25

12	7	25	3	27	78	98	21	40	22	51

Broj poređenja u ovom koraku - 4

Stanje niza nakon pretrage na ključ 40

12	7	25	3	27	78	98	40	21	22	51

Broj poređenja u ovom koraku - 9

Prosečan broj poređenja: $\frac{5+10+4+9}{4} = \frac{28}{4} = 7$

Prebacivanje na početak:

Stanje niza nakon pretrage na ključ 25

25	12	7	3	27	78	98	21	22	40	51

Broj poređenja u ovom koraku - 5

Stanje niza nakon pretrage na ključ 40

40	25	12	7	3	27	78	98	21	22	51

Broj poređenja u ovom koraku - 10

Stanje niza nakon pretrage na ključ 25

25	40	12	7	3	27	78	98	21	22	51

Broj poređenja u ovom koraku - 2

Stanje niza nakon pretrage na ključ 40

40	25	12	7	3	27	78	98	21	22	51

Broj poređenja u ovom koraku - 2

Prosečan broj poređenja: $\frac{5+10+2+2}{4} = \frac{19}{4} = 4.75$

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.

Primer

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.

Početno stanje

Rešenje

Posle svih umetanja

Posle svih brisanja

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.

1. (5p) Objasniti i nacrtati strukturu indeksa i način povezivanja sa listom koja se pretražuje.
2. (10p) Napisati u pseudokodu implementaciju funkcije za sekvencijalnu pretragu liste list uz korišćenje indeksa index na ključ key.

Rešenje

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

Struktura indeksa

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

Početno stanje

Rešenje

U stablu se već nalazi ključ 33, tako da on ne treba da se ubacuje.

• 

  Nakon umetanja ključa 30.

• 

  Nakon brisanja ključa 29.

• 

  Nakon brisanja ključa 61.

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

Postavka

(15p) Neka se posmatra jedna strogo monotono rastuća funkcija f(x). Na primer,$x^3 - 3x^2 +6x - 1$ ili $3^x$. 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_while

8. zadatak

Postavka

(10p) Analiza performansi stabla binarnog pretraživanja.

1. (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.
2. (5p) Izvesti i kratko objasniti vezu između Sn i Un koji su definisani pod a). Odgovor ilustrovati slikom.

Rešenje

1. Sn možemo predstaviti kao $Sn = (PI + n)/n$, jer ima za 1 više poređenja nego čvorova, a Un možemo predstaviti kao $Un = PE/n_{e} = PE/(n+1)$.
2. $PE = PI + 2n$

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

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