| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
Taurus
Forumaš(ica)
Pridružen/a: 05. 02. 2008. (23:11:51)
Postovi: (61)16
Spol: 
Lokacija: Psychiatric Mental Facility (PMF)
|
|
| [Vrh] |
|
ivica13
Forumaš(ica)
Pridružen/a: 03. 10. 2007. (14:01:02)
Postovi: (102)16
Spol:
|
|
| [Vrh] |
|
Blah
Forumaš(ica)
Pridružen/a: 11. 09. 2006. (18:07:56)
Postovi: (C1)16
Spol: 
|
|
| [Vrh] |
|
tihy
Forumaš(ica)
Pridružen/a: 19. 09. 2006. (09:43:16)
Postovi: (76)16
Spol: 
Lokacija: varaždin
|
|
| [Vrh] |
|
tajchi666
Forumaš(ica)
Pridružen/a: 14. 05. 2007. (20:55:39)
Postovi: (2B)16
|
|
| [Vrh] |
|
anekalo
Forumaš(ica)
Pridružen/a: 05. 03. 2007. (16:48:54)
Postovi: (55)16
|
|
| [Vrh] |
|
tajchi666
Forumaš(ica)
Pridružen/a: 14. 05. 2007. (20:55:39)
Postovi: (2B)16
|
|
| [Vrh] |
|
Atomised
Forumaš(ica)
Pridružen/a: 04. 09. 2007. (15:33:59)
Postovi: (399)16
Lokacija: Exotica
|
|
| [Vrh] |
|
tajchi666
Forumaš(ica)
Pridružen/a: 14. 05. 2007. (20:55:39)
Postovi: (2B)16
|
|
| [Vrh] |
|
anekalo
Forumaš(ica)
Pridružen/a: 05. 03. 2007. (16:48:54)
Postovi: (55)16
|
 Postano: 20:32 čet, 19. 2. 2009 Naslov: |
    |
|
|
Ima jedan zadatak u zavrsnom iz 2007. u kojem treba rekonstruirati binarno stablo s cvorivima D, E, I, J, K, L, V, Z. A znamo da korijen ima samo jedno dijete, da na nivou 2 cvorovi imaju oznake I i V, da cvor K ima samo lijevo dijete te da na nivou 4 nalazi i cvor cija je oznakak samoglasnik.
I jedno od potpitanja je:kojim redosljedom trebaju biti ubacivani cvorovi u binarno stablo trazenja tako da se dobije stablo ? napisite jedan takav redosljed.
Sta me zapravo pita?! Kakav redosljed?
Hvala!!! :)
Ima jedan zadatak u zavrsnom iz 2007. u kojem treba rekonstruirati binarno stablo s cvorivima D, E, I, J, K, L, V, Z. A znamo da korijen ima samo jedno dijete, da na nivou 2 cvorovi imaju oznake I i V, da cvor K ima samo lijevo dijete te da na nivou 4 nalazi i cvor cija je oznakak samoglasnik.
I jedno od potpitanja je:kojim redosljedom trebaju biti ubacivani cvorovi u binarno stablo trazenja tako da se dobije stablo ? napisite jedan takav redosljed.
Sta me zapravo pita?! Kakav redosljed?
Hvala!!! 
|
|
| [Vrh] |
|
Spectre
Forumaš(ica)
Pridružen/a: 02. 10. 2006. (16:58:05)
Postovi: (167)16
Spol:
|
|
| [Vrh] |
|
anekalo
Forumaš(ica)
Pridružen/a: 05. 03. 2007. (16:48:54)
Postovi: (55)16
|
| Postano: 22:43 čet, 19. 2. 2009 Naslov: |
|
|
|
Hm, ja sam pala prosle godine spa pa imam od pretprosle godine kolokvije.
[size=9][color=#999999]Added after 31 minutes:[/color][/size]
Ukratko:
teorija:def stog, jednu efikasnu impl, nju ilustriraj dijagramom. Nabroji mane i prednosti te implementacije
def red, i isto kao gore.
2. zadatak je ono sto sam napisala na forumu. Jos moras napisati PRE, IN, POST. i napravisti bin. stablo S razlicito od T (koje je zadano u zadatku), a da imaju isti PRE i POST(moraju se razlikovati bar u 3 cvora).
3.zadatak: Nacrtaj dijagram hash tablice od 16 pretinaca pomocu lin. zat. hasiranja. Zadani su skup i hash funkcija.
DRuga grupa:otvoreno hasiranje
4. zadatak: QUICKSORT
teorija:pohlepni, primjergdje se dobije optim. rj i primjer gdje se ne dobije opt. rj.
podijeli pa vladaj. primjer uspjesnog koristenja i primjer gdje ne daje efikasan algoritam.
Hm, ja sam pala prosle godine spa pa imam od pretprosle godine kolokvije.
Added after 31 minutes:
Ukratko:
teorija:def stog, jednu efikasnu impl, nju ilustriraj dijagramom. Nabroji mane i prednosti te implementacije
def red, i isto kao gore.
2. zadatak je ono sto sam napisala na forumu. Jos moras napisati PRE, IN, POST. i napravisti bin. stablo S razlicito od T (koje je zadano u zadatku), a da imaju isti PRE i POST(moraju se razlikovati bar u 3 cvora).
3.zadatak: Nacrtaj dijagram hash tablice od 16 pretinaca pomocu lin. zat. hasiranja. Zadani su skup i hash funkcija.
DRuga grupa:otvoreno hasiranje
4. zadatak: QUICKSORT
teorija:pohlepni, primjergdje se dobije optim. rj i primjer gdje se ne dobije opt. rj.
podijeli pa vladaj. primjer uspjesnog koristenja i primjer gdje ne daje efikasan algoritam.
|
|
| [Vrh] |
|
CrniVG
Forumaš(ica)
Pridružen/a: 19. 02. 2009. (22:44:19)
Postovi: (23)16
|
| Postano: 22:57 čet, 19. 2. 2009 Naslov: |
|
|
|
[quote="anekalo"]Ima jedan zadatak u zavrsnom iz 2007. u kojem treba rekonstruirati binarno stablo s cvorivima D, E, I, J, K, L, V, Z. A znamo da korijen ima samo jedno dijete, da na nivou 2 cvorovi imaju oznake I i V, da cvor K ima samo lijevo dijete te da na nivou 4 nalazi i cvor cija je oznakak samoglasnik.
I jedno od potpitanja je:kojim redosljedom trebaju biti ubacivani cvorovi u binarno stablo trazenja tako da se dobije stablo ? napisite jedan takav redosljed.
Sta me zapravo pita?! Kakav redosljed?
Hvala!!! :)[/quote]
Imaš dovoljno podataka da odrediš da je obilazak inorder i da rekonstruiraš samo stablo (više mi je trebalo da natipkam ovo nego da na papiru skiciram stablo....)
[code:1]0. Z
/
1. L
/ \
2. I V
/ \
3. D K
\ /
4. E J[/code:1]
| anekalo (napisa): | Ima jedan zadatak u zavrsnom iz 2007. u kojem treba rekonstruirati binarno stablo s cvorivima D, E, I, J, K, L, V, Z. A znamo da korijen ima samo jedno dijete, da na nivou 2 cvorovi imaju oznake I i V, da cvor K ima samo lijevo dijete te da na nivou 4 nalazi i cvor cija je oznakak samoglasnik.
I jedno od potpitanja je:kojim redosljedom trebaju biti ubacivani cvorovi u binarno stablo trazenja tako da se dobije stablo ? napisite jedan takav redosljed.
Sta me zapravo pita?! Kakav redosljed?
Hvala!!! |
Imaš dovoljno podataka da odrediš da je obilazak inorder i da rekonstruiraš samo stablo (više mi je trebalo da natipkam ovo nego da na papiru skiciram stablo....)
| Kod: | 0. Z
/
1. L
/ \
2. I V
/ \
3. D K
\ /
4. E J |
|
|
| [Vrh] |
|
Luuka
Forumaš(ica)
Pridružen/a: 13. 02. 2007. (20:34:54)
Postovi: (925)16
Spol:
Lokacija: Hakuna Matata
|
| Postano: 0:16 pet, 20. 2. 2009 Naslov: |
|
|
|
[quote="anekalo"]I jedno od potpitanja je:kojim redosljedom trebaju biti ubacivani cvorovi u binarno stablo trazenja tako da se dobije stablo ? napisite jedan takav redosljed.
Sta me zapravo pita?! Kakav redosljed?
Hvala!!! :)[/quote]
Binarno stablo traženja ima svojstvo da se u lijevom podstablu čvora nalaze oni < od njega, a u desno oni >=.
Stablo koje je napravio CrniVg je bin stablo traženja... i INORDER daje sortirani niz (mislim da je to dobra provjera, al nisam siguran da je tako samo kod bin stabla traženja) :D
redoslijed kojim bi se dobilo to stablo je recimo:
Z, L, V, I, D, E, K, J.
Kopiram iz skripte što kaže za fju INSERT, kako ona ubacuje u bin stablo traženja:
[quote]Operacija INSERT( ) radi slicno. Ona poput MEMBER( ) trazi mjesto u binarnom stablu gdje bi morao biti novi element, te ubacuje novi cvor na to mjesto.
void INSERT (elementtype x, DICTIONARY *Ap) {
if (*Ap == NULL) {
*Ap = (celltype*) malloc (sizeof(celltype));
(*Ap)->element = x;
(*Ap)->leftchild = (*Ap)->rightchild = NULL;
}
else if (x < (*Ap)->element) INSERT(x,&((*Ap)->leftchild));
else if (x > (*Ap)->element) INSERT(x,&((*Ap)->rightchild));
/* ako je x == (*Ap)->element, ne radi niˇsta jer je x ve´c u rjecniku */
}[/quote]
| anekalo (napisa): | I jedno od potpitanja je:kojim redosljedom trebaju biti ubacivani cvorovi u binarno stablo trazenja tako da se dobije stablo ? napisite jedan takav redosljed.
Sta me zapravo pita?! Kakav redosljed?
Hvala!!! |
Binarno stablo traženja ima svojstvo da se u lijevom podstablu čvora nalaze oni < od njega, a u desno oni >=.
Stablo koje je napravio CrniVg je bin stablo traženja... i INORDER daje sortirani niz (mislim da je to dobra provjera, al nisam siguran da je tako samo kod bin stabla traženja) 
redoslijed kojim bi se dobilo to stablo je recimo:
Z, L, V, I, D, E, K, J.
Kopiram iz skripte što kaže za fju INSERT, kako ona ubacuje u bin stablo traženja:
| Citat: | Operacija INSERT( ) radi slicno. Ona poput MEMBER( ) trazi mjesto u binarnom stablu gdje bi morao biti novi element, te ubacuje novi cvor na to mjesto.
void INSERT (elementtype x, DICTIONARY *Ap) {
if (*Ap == NULL) {
*Ap = (celltype*) malloc (sizeof(celltype));
(*Ap)→element = x;
(*Ap)→leftchild = (*Ap)→rightchild = NULL;
}
else if (x < (*Ap)→element) INSERT(x,&((*Ap)→leftchild));
else if (x > (*Ap)→element) INSERT(x,&((*Ap)→rightchild));
/* ako je x == (*Ap)→element, ne radi niˇsta jer je x ve´c u rjecniku */
} |
_________________ "Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy |
|
| [Vrh] |
|
glava
Forumaš(ica)
Pridružen/a: 28. 03. 2007. (18:48:16)
Postovi: (89)16
Spol:
|
|
| [Vrh] |
|
ekatarina
Forumaš(ica)
Pridružen/a: 25. 11. 2007. (19:22:50)
Postovi: (161)16
Spol:
|
|
| [Vrh] |
|
Spectre
Forumaš(ica)
Pridružen/a: 02. 10. 2006. (16:58:05)
Postovi: (167)16
Spol:
|
| Postano: 13:18 pet, 20. 2. 2009 Naslov: |
|
|
|
0 prazna, ne znam zašto su to napravili, mogli su taj zadnji broj stavit za 1 veći pa bi se vidlo da li ljudi kuže šta se onda događa, no whatever...
A kod stabala imaš 5 komada. Mogu ti ga riješit ako hoćeš, no nakon ručka :)
Krećem.
Tražila su se sva binarna stabla traženja s elementima A, B, D, M, P, R, X koja u PREORDER poretku završavaju s ...X, a u POSTORDER poretku počinju s BDA...
Dakle, korijen mogu biti samo M, P i R.
1. stablo s M korijenom:
[code:1]
M
/ \
A P
\ \
D R
/ \
B X
[/code:1]
2. stablo s M korijenom:
[code:1]
M
/ \
A R
\ /\
D P X
/
B
[/code:1]
1. stablo s P korijenom:
[code:1]
P
/ \
M R
/ \
A X
\
D
/
B
[/code:1]
1. stablo s R korijenom:
[code:1]
R
/ \
M X
/\
A P
\
D
/
B
[/code:1]
2. stablo s R korijenom:
[code:1]
R
/ \
P X
/
M
/
A
\
D
/
B
[/code:1]
Eto, tu su sva BST koja zadovoljavaju gornje uvjete. :)
0 prazna, ne znam zašto su to napravili, mogli su taj zadnji broj stavit za 1 veći pa bi se vidlo da li ljudi kuže šta se onda događa, no whatever...
A kod stabala imaš 5 komada. Mogu ti ga riješit ako hoćeš, no nakon ručka
Krećem.
Tražila su se sva binarna stabla traženja s elementima A, B, D, M, P, R, X koja u PREORDER poretku završavaju s ...X, a u POSTORDER poretku počinju s BDA...
Dakle, korijen mogu biti samo M, P i R.
1. stablo s M korijenom:
| Kod: |
M
/ \
A P
\ \
D R
/ \
B X
|
2. stablo s M korijenom:
| Kod: |
M
/ \
A R
\ /\
D P X
/
B
|
1. stablo s P korijenom:
| Kod: |
P
/ \
M R
/ \
A X
\
D
/
B
|
1. stablo s R korijenom:
| Kod: |
R
/ \
M X
/\
A P
\
D
/
B
|
2. stablo s R korijenom:
| Kod: |
R
/ \
P X
/
M
/
A
\
D
/
B
|
Eto, tu su sva BST koja zadovoljavaju gornje uvjete.
_________________
Cry havoc, and let loose the dogs of war!
|
|
| [Vrh] |
|
glava
Forumaš(ica)
Pridružen/a: 28. 03. 2007. (18:48:16)
Postovi: (89)16
Spol:
|
|
| [Vrh] |
|
BitterSweet
Forumaš(ica)
Pridružen/a: 10. 10. 2007. (21:09:28)
Postovi: (174)16
Spol:
Lokacija: sjeverno od raja
|
|
| [Vrh] |
|
glava
Forumaš(ica)
Pridružen/a: 28. 03. 2007. (18:48:16)
Postovi: (89)16
Spol:
|
|
| [Vrh] |
|
|
