Strukture Podataka i Algoritmi 2009/10

marko_arsenal · **Poslato:** 30.06.2010. 17:34:09

Je l' dolaze hesing i sortiranje na ispitu? :cupavi:

undertaker_ca · **Poslato:** 30.06.2010. 17:59:26

Mozda kao teorijsko pitanje. prethodnih godina je dolazilo u nekim rokovima.

Hoce li biti izbachen neki raspored?

tijana88 · **Poslato:** 30.06.2010. 19:21:39

Da li neko zna da da primer za resavanje problema kolizije kljuceva prilikom pretrazivanja hesing algoritmom, ako se koristi metoda olancavanja? Javljalo se vise puta kao teorijsko pitanje prosle godine...

katjaA · **Poslato:** 30.06.2010. 19:31:09

Sta podrazumeva dati primer za insertion sort?

makitod · **Poslato:** 30.06.2010. 19:38:44

^^primer za resavanje kolizije olancavanjem je da se za svaki indeks umesto polja stavi neka dinamicka struktura, lista ili stablo

^primer za insertion sort verovatno znaci da treba da se napisu nekih 5,6 brojeva i sortiraju se pomocu insertion sorta, ja bih rekla da moze ovako na pr.
2 7 1 9 8 0 4
1 2 7 9 8 0 4
1 2 7 8 9 0 4
0 1 2 7 8 9 4
0 1 2 4 7 8 9

tijana88 · **Poslato:** 30.06.2010. 19:43:13

@makitod
hvala... a za metod otvorenog adresiranja ?

makitod · **Poslato:** 30.06.2010. 19:47:55

Kod metode otvorenog adresiranja se uvodi druga hasing funkcija, ona moze biti g(k)=h(k)+1, ako funkcija ne resi problem kolizije onda se uvodi nova g1(k)=g(k)+1 i tako dok se ne nadje slobodno mesto.

marko_arsenal · **Poslato:** 30.06.2010. 20:34:13

Je l' moze neko da pojasni ovaj kod?

Kod:

private void izbaciListPolulist(CvorStabla cvor){
      CvorStabla r = nadjiRoditelja(koren, cvor.podatak);
      CvorStabla dete = cvor.levo != null ? cvor.levo : cvor.desno;
      
      if (r == null)
         koren = dete;
      else {
         if (r.levo == cvor)
            r.levo = dete;
         else
            r.desno = dete;
      }
   }

Stifmeister · **Poslato:** 30.06.2010. 20:46:47

undertaker_ca je napisao:

Josh jedno pitanje, dat nam je pokazivach na koren stabla i pokazivach na neki chvor, treba ispisati najmanji(najveci) chvor koji se nalazi na toj putanji? Kako se ovo radi? Gledao sam u temi od proshle godine, ali mi nije bash najjasnije, pa ako bi mogao neko da napishe kod.
Hvala unapred!

Kod:

Cvor najmanjiCvor (Cvor c) {
int minimumStabla = min(c);
Cvor cvor = nadjiCvorPoPodatku (c, minimumStabla);
return cvor;
}


Cvor vratiPostojeci (Cvor c1, Cvor c2){
if( c1!=null){
return c1;
}else{
return c2; 
  }
}

Cvor nadjiCvorPoPodatku(Cvor c,  int pod){
  if (c!=null){
  if (c.pod == pod){
  return c;
  }else{
  Cvor c.vratiPostojeci(nadjiCvorPoPodatku(c.levo,pod), nadjiCvorPoPodatku(c.desno,pod));
  return c;
  }else{
  return null;
  }
}

Archduke · **Poslato:** 30.06.2010. 20:48:51

^^

Kod:

private void izbaciListPolulist(CvorStabla cvor){ 
      CvorStabla r = nadjiRoditelja(koren, cvor.podatak);   
//nadjiRoditelja je f-ja koja je negde implementirana, kao sto ime kaze, nalazi roditelja



      CvorStabla dete = cvor.levo != null ? cvor.levo : cvor.desno; 
//novi CS dete uzima vrednost cvor.levo ako je cvor.levo != null, inace uzima vrednost cvor.desno; 

       
      if (r == null) 
         koren = dete; 
//u slucaju da pokusavamo da izbacimo koren, onda njegovo jedino dete (posto je polulist) postaje koren


      else { 
         if (r.levo == cvor) 
            r.levo = dete; 
         else 
            r.desno = dete; 
      } 
//prespajamo dete umesto cvora


   }

makitod · **Poslato:** 30.06.2010. 22:10:01

Ja mislim da vazi raspored kao za 2 kolokvijum, jer se secam da je Kosta rekao pred drugi kolok.da je isti raspored kao za prvi, ali kao stavice ponovo, ako se neko ne seca. Po toj logici verovatno je isti raspored i za ispit.

goggga · **Poslato:** 30.06.2010. 23:31:08

"Studenti koji nisu na spisku ili imaju manje od 40 poena su pali ispit. Studenti koji imaju između 40 i 49 poena su položili uslovno i moraće da rade dodatne zadatke kako bi položili ispit. Usmeni ispit (upis ocena) će biti u četvrtak 10.07.2008. u 09:00 u sali 200. Uvid u radove će biti sat vremena pre usmenog dela u kabinetu 017. Studenti koji su ispit položili preko kolokvijuma i domaćih zadataka (koji nisu izlazili u roku) treba da sa sobom ponesu ispitne prijave."

Ovako je bilo prosle god! A ove? Zna li neko?????

marko_arsenal · **Poslato:** 30.06.2010. 23:41:17

makitod je napisao:

Kako se radi ovaj zad:
Dat je pokazivač na koren binarnog stabla čiji čvorovi sadrže cele brojeve. Napisati funkciju koja će vratiti pokazivač na čvor koji je na najvećoj dubini u stablu.

Kod:

 private int dubina(CvorStabla tek){
            if(tek==null || (tek.levo==null && tek.desno==null))return 0;  
            return 1+Math.max(dubina(tek.levo), dubina(tek.desno));
}

Kod:

public CvorStabla najdublji(CvorStabla cvor){
      if(visina(cvor)==0) return cvor;
      if(visina(cvor.levo)>=visina(cvor.desno) && cvor.levo!=null) return najdublji(cvor.levo);
      else return najdublji(cvor.desno);
   }

Trebalo bi da moze ovako..

StevieG · **Poslato:** 01.07.2010. 01:58:29

moze neko samo ukratko da mi objasni ovaj debalans kod rotacije? nije mi jasno kad je -1 kad je -2 kad je +1 :zbun:

Psychotix · **Poslato:** 01.07.2010. 02:17:32

I jedno skakljivo pitanje:

Uradio sam prvi i drugi domaci, zelim sutra da popravim drugi deo (fale mi 7 poena za prolaz), smem li da radim teoriju (npr, uradim samo teorijsko i imam za prolaz)...
Posto po ovim rokovima pise da teorijsko zamenjuje domaci, a ja imam domaci... :S

goggga · **Poslato:** 01.07.2010. 02:41:33

ne mozes da radis teorijsko onda. sem ako ne zelis da ponistis domaci, ali ne vidim razlog za tim.
moraces da radis II deo, da nadoknadis poene.

marko_arsenal · **Poslato:** 01.07.2010. 03:17:58

StevieG je napisao:

moze neko samo ukratko da mi objasni ovaj debalans kod rotacije? nije mi jasno kad je -1 kad je -2 kad je +1 :zbun:

Pa kad vam Dzerard i Tores odu, a zaigraju Ngog i Lukas automatski ste debalansirani... :cupavi:

Balansni fak. levog podstabla minus bal. fak. desnog podstabla. Ako dobijes -2 rotiras u levo, a za 2 u desno..
Treba i da vodis racuna kod rotacije, ako cvorovi koji menjaju mesta imaju bal. fak. suprotnog znaka prvo moras da rotiras onaj sa bil. fak. 1 ili -1, pa onda onaj sa 2 ili -2..

NancY_88 · **Poslato:** 02.07.2010. 13:27:15

evo jun 2010

http://www.2shared.com/file/pqaSth90/jun_2010.html

marko_arsenal · **Poslato:** 02.07.2010. 15:06:09

*ivy* · **Poslato:** 03.07.2010. 13:33:26

Evo i I grupe, ako nekom bude trebalo:

http://i47.tinypic.com/2iibqqv.jpg

http://i50.tinypic.com/w1zrx1.jpg

cvelle89 · **Poslato:** 28.07.2010. 20:21:27

Postovanje,
Imam par pitanja pa da pocnem:
1.Ako u sept dam I deo jel se racuna, za okt kao polozeni I deo?To nisam skapirao...
2.Sad cu ukratko izloziti sta sam ja shvatio sta treba da se sprema za ispit, pa neka me neko ispravi posto mi je ovaj ispit od sada NAJKONFUZNIJI..:

I DEO
-jednostruko spregnuta lista
-dvostruko spregnuta lista
ovde dolazi: ubaciNaKraj, ubaciNaPocetak, izbaciIspredTrenutnog,izbaciSaPocetka, ispisiElementeListe, pretrazi, i sl.

Sortiranje:
-selection,insertion,shell i bubble,
manje verovatno da ce doci kod za sprtiranje:
heap, merge i quick sort – samo teorijsko pitanje

Pretrazivanje:
to ima sve u strukutre2010.zip sa sajta jel tako?
-Binarno
-Interpolaciono...

Pretrazivanje & sortiranje - uci se napamet?

Teorija - iz skripte by User. (mada mi je tamo nesto tanko sve)

II DEO
ovaj deo jos nisam krenuo da radim,ali otprilike:

STABLA:
AVL, B, B*, crtanje

Teorijsko pitanje...iz skripte byUser

Jel to to?

makitod · **Poslato:** 30.07.2010. 16:04:09

^Ja mislim da ti je najbolje da ucis teoriju sa slajdova sa predavanja, ima ih na sajtu njihovom.
Pretrazivanje i sortiranje-bolje je da razumes kod, ali ako ne razumes onda mozes i napamet posto ne daju zadatke sa tim, vec samo da se ispise kod za neko pretrazivanje ili sortiranje. Bio je u junu kod za sortiranje tako da nisu male sanse da dodje.
U sustini, vezbaj prethodne rokove i doci ce neki zadatak koji je vec bio sigurno.

Gorbash · **Poslato:** 30.07.2010. 17:54:36

Prvo, ne racuna ti se parcijalno polaganje, tj. ne mozes samo prvi deo, pa u drugom roku drugi deo.

Takodje, moguce je da ce ti doci da ubacis/izbacis iz reda/steka, kao prvi zadatak. Posto su to specificne strukture, moguc je samo jedan nacin, tako da iako su male sanse da dodje to, nije lose da naucis, mali su kodovi za to.

Drugi zadatak, kao sto je receno bude ili neko sortiranje (insertion, selection, bubble, shell) ili pretrazivanja.

Treci zadatak je malo teze programiranje, sa ciklicnim listama i slicno.

Kao teorijska pitanja su u poslednje 3-4 godine dolazila ova:

Citiraj:

- Data je jednostruko spregnuta lista od k cvorova gde svaki cvor sadrzi niz od t celih brojeva. Koja je kompleksnost algoritma za sekvencijalno pretrazivanje ovakve strukture (pronalazenje celog broja)?

- Data je jednostruko spregnuta lista od m elemenata ciji svaki cvor sadrzi niz od n elemenata. Koja je kompleksnost pretrazivanja ovakve strukture?

- Data je jednostruko spregnuta lista od elemenata ciji svaki cvor sadrzi niz od k elemenata. Koja je kompleksnost algoritma za sekvencijalno pretrazivanje ovakve strukture (pronalazenje celog broja)?

- Objasniti robusno interpolaciono pretrazivanje

- Recite da li postoji slucaj kada je interpolaciono pretrazivanje sporije od binarnog pretrazivanja. Objasnite ga.

- Recite da li postoji slucaj kada je interpolaciono pretrazivanje brze od binarnog pretrazivanja. Objasnite ga.

- Objasniti razliku izmedju FIFO i LIFO strukture.

- Objasniti razliku izmedju linearne i nelinearne strukture.

- Shell Sort algoritam

- Insertion sort

Drugi deo.

Prvi zadatak je AVL stablo, ubacivanje. Medjutim, desi se ponekad da daju dva ubacivanja u stablo (jedno kao prvi zadatak, drugo kao drugi, jelte) u kom slucaju prvi zadatak ce biti da ubacis elemente u vec zapoceto stablo, a zatim da neke elemente i izbacis iz njega.

Uglavnom bude neko lako programiranje, naci najveci na putanji i slicno, medjutim moze da se desi da bude ubacivanje u B ili B* stablo (onda kada dobijes vec postojece AVL stablo i treba da izbacis na kraju) i isti je slucaj, neke ubacis, neke izbacis.

Teze programiranje je treci zadatak.

I kao teorijsko pitanje sam sakupio da dolaze sledeca pitanja:

Citiraj:

- Kako se resava problem kolizije kljuceva prilikom pretrazivanja hesing algoritmom ako se koristi metoda otvorenog adresiranja

- Recite sta je BST stablo i kratko objasnite algoritam ubacivanja novog cvora u BST stablo.

- Recite sta je AVL stablo i kratko objasnite algoritam ubacivanja cvora u AVL stablo.

- Objasniti postupak pretvaranja sume visegranskih stabla u jedno binarno stablo i dati primer.

- Sta je graf (mreza) I koji su njegovi elementi (opisite ih).

- Sta je hashing i kako se resava problem kolizije kljuceva olancavanjem?

- Sta je hashing i kako se resava problem kolizije kljuceva otvorenim adresiranjem

- Koliko cvorova ima kompletno binarno stablo reda 9?

- Sta je B* stablo?

cvelle89 · **Poslato:** 31.07.2010. 01:07:25

hvala puno na odgovorima. Ako mi jos nesto ne bude bilo jasno, pitacu.
Izgleda da sam ja jedini koji ovo nije polozio..haha :yo:

lud zbunjen normalan · **Poslato:** 31.07.2010. 12:01:59

Nisam ni ja

i ne znam kad cu! Meni je ovo najtezi ispit na drugoj. Ako naucim prethodne rokove koji nadam se imaju na njihovom sajtu, imam li sanse? Naravno, govorim o ucenju napamet

FONForum

Strukture Podataka i Algoritmi 2009/10

Ko je OnLine