FONForum

Nastava:

1) Predavanja – Profesor Siniša Nešković će vam držati predavanja. Nema upisivanja, ali na predavanjima se radi gradivo koje dolazi za kolokvijum pa će vam biti lakše da slušate vežbe ako čujete uvodni teorijski deo za tu oblast. Teorija se uvek polaže pismeno bilo da je polažete preko kolokvijuma ili u ispitnom roku i za spremanje teorije su potrebni slajdovi sa predavanja jer ne postoji knjiga iz ovog predmeta.
2) Vežbe – Vežbe od prošle godine drži Dejan Stojimirović i na njima ćete raditi zadatke vezane za nizove, stekove, redove, liste i stabla. Na vežbama takođe nema upisivanja. Prošle godine je izašla probna zbirka u elektronskoj formi pa su je možda ove godine i spremili za štampanje, ali i asistent će vam kačiti pređene kodove na sajt pa ćete imati dovoljno materijala za spremanje.

Način polaganja:

1. Parcijalno preko kolokvijuma - Kolokvijumi se sastoje iz dva dela (zadaci i teorija). Nije moguće polagati samo teoriju ili samo zadatke. Za prvi kolokvijum se spremaju niz, stek, red, liste, sortiranja i pretraživanja, a za drugi kolokvijum stabla. Iz teorije dolaze samo pitanja na zaokruživanje, nema negativnih poena, ali konstruisana su tako da mora da se razume gradivo da biste znali tačan odgovor. Nije neophodno da položite i teoriju i zadatke nego da u zbiru imate dovoljno poena. Teorija ima 10 pitanja na zaokruživanje koje nose po 3 poena, jedno čitanje koda koje nosi 11 poena. I ostalo su zadaci, pisanje koda, uglavnom bude 4 zadatka. Da bi položili ceo ispit neophodno je da na oba kolokvijuma imate barem po 51 poen. Ako položite prvi, a padnete drugi kolokvijum, prvi vam važi do prvog izlaska na ispit. Kolokvijumi se rade sat vremena.

2. Preko ispita – Ispit ne može parcijalno da se polaže (jedino ako imate položen kolokvijum i prvi put izlazite na ispit). Ukoliko izlazite na ispit to vam je kao da polažete dva kolokvijuma odjednom. Ispit je potpuno iste strukture kao i kolokvijumi, dobijate odvojeno za prvi i drugi deo i morate na svakom imati minimum poena. Oni koji nisu zadovoljni sa predloženom ocenom ili su položili komisijski mogu da odgovaraju u terminu usmenog dela ispita. Profesor postavi nekoliko zadataka u zavisnosti od ocene za koju odgovarate, a može vas dodatno pitati i nesto iz teorije. Ispit se radi 2 sata.

Sva pitanja (i za profesora i za asistenta) šaljete na mejl strukture@fon.rs
Materijale za spremanje ispita možete naći na sajtu predmata ili u download sekciji.

Prošlogodišnja iskustva kolega

Napomena: Obavestite nas ukoliko je došlo do promene u pravilima polaganja.

Jesu li kolokvijumi uslovljeni?

Nisu.

Drugi kolokvijum:

Radi se sat vremena. Teorijska pitanja (ukupno ih ima 11) imaju po 4 ponudjena odgovora (od cega je samo 1 tacan). Nema negativnih (medju ponudjenim odgovorima nekada bude i nista od ponudjenog). Prvih 10 pitanja nose po 3 poena, a 11. nosi 11. Imaju 4 zadatka: Laksi kod (13 poena), tezi kod (18 poena), crtanje AVL stabla (13 poena) i B ili B* stabla (15 poena).
Konkretno pitanja:

1. Visina stabla je? (trebalo je zaokruziti maksimalni nivo cvora koji jeste list; bilo je ponudjeno i maksimalni nivo cvora koji nije list, broj cvorova koji se prodje od korena do datog cvora (sto je definicija nivoa cvora) i jos jedan odgovor)

2. Date su izjave u vezi sa stablima pa da se zaokruzi tacna. Tacan odgovor je kompletno binarno stablo je specijalan slucaj skoro kompletnog binarnog stabla (ponudjen je bio i obrnut odgovor)

3. AVL stablo ima ukupno m cvorova i visinu k. Vreme potrebno za pronalazenje nekog cvora u stablu proporcionalno je sa? (Tacan odgovor je K, a bilo je ponudjeno i M i M*k i jos jedan odgovor).

4. Primarna kolizija je? Tacan odgovor je Kada razliciti kljucevi imaju iste adrese. (Bilo je ponudjeno i Kada se sudara kljucevi koji imaju razlicite h(k)-sto je definicija sekundarne kolizije; osim toga, ponudjeno je bilo i Kada se koristi metoda olancavanja i Sve navedeno).

5. Dato je BST stablo. Ako se izbacuje koren, koji cvor iz levog podstabla ce doci na njegovu poziciju. (Takav je 4. zadatak u primeru drugog kolokvijuma koji ima na sajtu). Resava se tako sto, ako pita za levo podstablo, samo nadjete najveci broj, a ako pita za desno podstablo, nadjete samo najmanji broj.

6. Izjave u vezi sa stablima. Tacan odgovor je da je Svako kompletno binarno stablo i striktno binarno stablo. (Bilo je ponudjeno i Svako binarno stablo je ili striktno ili kompletno; Svako striktno je kompletno; i jos jedan odgovor)

7. Data je slika grafa pa da se zaokruzi odgovor koji ne predstavlja prolaz po dubini. Takav je 9. zadatak u primeru sa sajta.

8. Dato je binarno stablo pa da se napise kako ce se ispisati brojevi, ako se prodje prefiksnim prolazom. Takav je 7. zadatak sa sajta.

9. Posmatrajmo cvor skoro kompletnog binarnog stabla, implementiranog preko niza, cija je vrednost sacuvana u niz[7]. Posmatrano od ovog cvora, gde ce biti sacuvana vrednost njegovog roditelja. Tacan odgovor je 3 (bilo je ponudjeno i 2 i 4 i jos jedan odgovor). Ovo se racuna po formuli (ima greska u Maksinim sredjenim predavanjima):
indeks levog deteta: i*2+1
indeks desnog deteta: i*2+2
indeks roditelja: (i-1)/2

10. Date su izjave za B stablo:
Svi cvorovi nisu na istom nivou. (ovo nije sigurno tacno, jer je suprotno od ona dva uslova)
Cvorovi koji nisu roditelji imaju isti broj dece (Ovo nije tacno jer, ako je na primer stablo reda 2, koren tog stabla (dakle cvor koji nije list) moze da ima dvoje dece, a neki cvor ispod njega moze da ima troje dece).
Stablo reda 22 ima cvor sa 1 kljucem (Ovo tacan odgovor). I bio je ponudjen jos jedan.

11. Kao i uvek quiz metoda i kao i uvek malo izmenjena (sto potpuno menja odgovor):
void quiz(int i){
System.out.println("*");
if (i>1){
quiz(i/2);
System.out.println("*");
quiz(i/2);
}
}
Tacan odgovor je 10 zvezdica. Uvek je jedan od ponudjenih odgovora i nista od ponudjenog, sto je takodje moguc odgovor (jer, asisitent Dejan je na vezbama pricao da kada sastavi metodu, nasumicno stavi odogvore).

Zadatak sa AVL stablom je kao i na primeru sa sajta. Dato je najpre da se ubaci 7 brojeva, a onda 3 da se izbace.

Zadatak sa B* stablom je dosao. Takodje 7 brojeva za ubacivanje i 3 za izbacivanje.

Prvi zadatak sa kodom. Dat je pokazivac na koren BST stabla. Napisati metodu koja ispisuje listove u rastucem redosledu.

Trebalo je samo napisati infiks prolaz, ali staviti i uslov da je cvor.levo==null && cvor.desno==null (jer takvi cvorovi su listovi)

Drugi zadatak sa kodom ne mogu ni da ponovim. Nesto kao: Dati su pokzivaci na koren i na cvorove P i Q kod binarnog stabla. Potrebno je vratiti zbit zajednickih predaka cvorova P i Q. Tako nesto.

Septembarski rok

I deo:
1. Selection sort, kako ce izgledati posle dve iteracije, rastuci redosled
2. Red - ubaceni elementi redom DCBA, kojim redom ce se izbaciti
3. Algoritam ima vremensku kompleksnost (O^2), pa sta to znaci...
4. Dat pokazivac na prvi element DS liste i podatak koji je ceo broj. Ako lista ima najmanje jedan element, napisati algoritam koji novi element ubacuje na drugo mesto
5. public boolean sadrziSe(CvorJSListe L1, CvorJSListe L2). Lista implementariana preko stringa, potrebno je proveriti da li se prvi string L1 sadrzi u drugom stringu. primer: (da li se rec "nedelja" sadrzi u "ponedeljak");

IIdeo
1. B* stablo, drugog reda
2. AVL stablo
3. Napisati metodu koja proverava da li je stablo striktno binarno
4. Napisati metodu koja ce izbrojati koliko elemenata stabla ima vrednost vecu od svojih potomaka
5. Napisati metodu koja ce vratiti pokazivac na cvor sa najvecom vrednoscu na putanji od korena do lista na najmanjoj dubini

Oktobar

I deo
- Napisati metodu za binarno pretrazivanje niza u rastucem redosledu
- Dat je pokazivac na prvi element JS liste. Napisati metodu koja izbacuje sve elemenete koji su veci(manji) od date vrednosti
- Napisati metodu koja vraca zbir 3 najveca elementa u nizu:
a) u vise prolaza
b) u jednom prolazu (za 10)

II deo
- Dat je pokazivac na koren binarnog stabla. Napisati metodu koja racuna zbir parnih elemenata u stablu
- Dat je pokazivac na koren binarnog stabla celih brojeva. Napisite algoritam koji ce dato stablo urediti tako da za svaki cvor vazi da je element u njemu veci od elemenata njegove dece