FONForum

1. Robusno interpolaciono pretrazivanje.
Postoji veza izmedju vrednosti kljuca u skupu vrednosnih kljuceva i pozicije u nizu zapisa sa tim kljucem, na osnovu koje se moze izracunati (interpolirati) pozicija trazenog elementa. Robusno interpolaciono pretrazivanje je brzo pretrazivanje, jer se uvodi promenljiva R (razmak) tako da je uvek Pk-Pmin i Pmax-Pk vece od R.

2. Postupak pretvaranja sume visegranskih stabala u jedno binarno stablo I dati primer.

3. Razlika izmedju FIFO i LIFO
Razlika je u tome sto se elementi razlicito skladiste i dohvataju. U slucaju FIFO dohvataju se onim redosledom kojim su skladisteni. U slucaju LIFO onaj koji je poslednji skladisten se prvi dohvata.

4. Hashing (olancavanje, otvoreno adresiranje)
Prva tehnika se naziva otvoreno adresiranje. Kada se primenom funkcije h(k) dobije adresa koja je vec zauzeta, tada se na dobijenu vrednost primenjuje nova funkcija r(k). Ona se primenjuje sve dok se dobije slobodna adresa. Najjednostavnija funkcija r(k) je ri+1(k)=ri(k)+1, r1(k)=h(k)+l, tj. funkcija cija vrednost je sledeca adresa u odnosu na prethodno izracunatu adresu. Ovom metodom se zapravo sekvencijalno, linearno ispituju adrese sve dok se ne nade slobodna adresa. Zato se ova metoda naziva linearno probanje.
Druga tehnika problem kolizije rešava olancavanjem zapisa ciji kljucevi imaju istu vrednost za h(k). Za smeštanje olancanih zapisa se može koristiti isti memorijski prostor kao i za ostale zapise bez kolizije tzv. primarni prostor a može se i rezervisati poseban prostor za njih. U prvom slucaju se zauzima manje prostora, tj. efikasnije se koristi prostor ali može dovesti do povecanog broja kolizija. Naime, smeštanjem zapisa cije adrese su zauzete u primarni prostor se zapravo zauzimaju adrese za neke zapise koje bi oni dobili sa funkcijom h(k). Slucaj da jedan zapis primenom funkcije h(k) dobije adresu koja je zauzeta od strane zapisa cija vrednost h(k) nije ta adresa se naziva sekundarno grupisanje.

5. Razlika izmedju linearne I nelinearne strukture
Elementi u linearnim strukturama imaju tacno jednog sledbenika, dok u nelinearnim elementi mogu imati vise sledbenika.

6. Data je jednostruko spregnuta lista od k cvorova gde svaki cvor sadrzi niz od t celih brojeva. Koja je kompleksnost algoritma za sekvencijalno pretrazivanje (pronalazenje celog broja)?
Kompleksnost zavisi od toga gde se element nalazi. Ako je na prvom elementu onda je slozenost 1, a u najgorem slucaju je potrebno pretraziti svih t*k elemenata, tako da u proseku je slozenost (t*k+1)/2

7. BST stablo, algoritam ubacivanja novog cvora
BST je binarno stablo kod koga za svaki cvor vaze sledeca dva uslova:
- Svi cvorovi u levom podstablu imaju sadrzaj koji je manji ili jednak sadrzaju datog cvora.
- Svi cvorovi u desnom podstablu imaju sadrzaj koji je veci ili jednak sadrzaju datog cvora.
- Prvo se pretrazi stablo i ubaci se na cvor na mesto gde se pretrazivanje zavrsilo.

8. Insertion sort
Insertion sort je metod sortiranja koji se zasniva na tome da imamo sortiran i nesrotiran deo niza. Sortiranje se vrsi tako sto se uzima element iz nesortiranog dela i direktno ubacuje u sortiran deo. Efikasan na malom broju podataka. Jednostavan za implementaciju.

9. Selection Sort
Metod sortiranja koji se zasniva na tome da imamo sortirani i nesortirani deo niza. Sortiranje se vrsi tako sto nalazimo najmanji ili najveci element u nesortiranom delu i on zameni mesta sa prvim elementom u nesortiranom delu, cime on prelazi u sortirani deo. Jednostavan za implementiranje, pogodan za mali broj podataka.

10. Razlika izmedju insertion i selection
Slicni su po tome sto oba imaju sortiran i nesortiran deo niza. Razlikuju se po tome sto insertion sort direktno ubacuje element na njegovo mesto u sortiranom delu, a selection nalazi min/max u nesortiranom delu i zameni mesto sa prvim elementom u nesortiranom delu, cime on prelazi u sortiran deo.

11. Shell sort
Deli niz na vise grupa od kojih svaka ima vise elemenata. Pojedinacne grupe se sortiraju koristeci Insertion metodu sortiranja. Elementi grupe se nalaze na ekvidistantnom rastojanju, tj. na pozicijama sa jednakim inkrementima. Inkrement se tokom algoritma smanjuje, broj elemenata u grupi se povecava, a broj grupa smanjuje dok se ne dodje do inkrementa 1, sto znaci da je citav niz jedna grupa cijim sortiranjem se dolazi do konacnog rezultata.

12. Bubble sort
Poredi dva susedna elementa i ako nisu u pravilnom poretku, oni menjaju mesta.

13. Sta je graf (mreza) i koji su njegovi elementi (opisite ih)
- Grafovi su nelinearne strukture podataka. Predstavljaju najopštije strukture podataka . Odnos između elemenata nije linearan; jedan element može imati više sledbenika i više prethodnika. Nema ograničenja u pogledu povezivanja elemenata. Elementi grafa se nazivaju čvorovi. Veze između čvorova se nazivaju lukovi

14. Sta je AVL stablo? Algoritam ubacivanja novog cvora.
AVL stablo je binarno stablo pretrage kod kojeg apsolutna razlika visina levog I desnog podstabla svakog elementa nije veca od jedan.
- Prvo se pretrazi stablo i ubaci se cvor na mesto gde se pretrazivanje zavrsilo.
- Proveri se za svaki cvor da li postoji debalans.
- Ako postoji, vrsi se odgovarajuca rotacija oko cvora k koji je najblizi mestu ubacivanja.
- Ako je oznaka debalansa deteta cvora k suprotna, onda se pre rotacije iz prethodnog koraka, vrsi suprotna rotacija oko deteta cvora k

15. Objasnite pojam nelinearne strukture:
Svaki element ima jednog ili više prethodnika i više sledbenika.

16. Koliko cvorova ima kompletno binarno stablo reda 9?
511

17. koliko cvorova ima kompletno binarno stablo reda 10?
1023

18. Da li postoji slucaj kada je binarno pretrazivanje brze od interpolacionog pretrazivanja?
Kada raspodela elemenata nije uniformna.

19. Da li postoji slucaj kada je interpolaciono pretrazivanje brze od binarnog pretrazivanja?
Kada se trazeni element nalazi “slepljen” uz desnu ili levu ivicu skupa koji se pretrazuje, jer se tada binarno pretrazivanje degenerise u sekvencijalno.

20. B stablo reda n
Koren stabla, ako nije list, ima najmanje 2 podstabla. Svi cvorovi, osim korena i listova imaju najmanje n/2 (zaokruzuje se na veci). Svi listovi su na istoj visini.

21. B+ stablo
Kljucevi u okviru cvora su uredjeni i omogucen im je sekvencijalni pristup. Svi listovi su na istoj dubini i uvezani u ulancanu listu.

22. Sta je B* stablo?
Kod B* stabala, za razliku od B stabla, svi podaci se skladiste u listovima; samo kljucevi se skladiste u unutrasnjim cvorovima

23. Quick Sort

^Ne, meni ni na ispitu ni na kolokvijumima se nije ponovilo pitanje koje je bilo ranije. Ali i nema toliko mnogo. Vecina stvari moze da se zapamti citanjem.

Kolege, da li bi neko mogao da okaci septembarski rok ako ima? Hvala unapred

ajde nek neko okaci septembarski? PLEASE

ne razumem bas prvo pitanje, al evo ti kod za bin pret (opadajuci redosled);

public int binPret (int pod, int[] niz){
int l=0;
int d=niz.length-1;

while (l<=d)
int s=(l+d)/2;

if ( n[s]==pod)
return s;

if(n[s]<pod)
d=s-1;
else
l=s+1;
}
return -1;

Hashing (otvoreno adresiranje)

Ako neko zna da resi:

Dat je pokazivac na prvi element u JSListi celih br.Napisati metodu "Ubaci" koja ubacuje novi element nakon prvog elementa koji je veci od njega.Ako takav element ne postoji,novi element se ubacuje na krja liste.

Hvala