FONForum

onaj zadatak iz prvog dela sada na ispitu sa interpolacionim pretrazivanjem gde se trazi broj 71..koji je tacan odgovor?

Ja sam stavio da se pronalazi pre trece iteracije, ali nisam siguran da je tacno

A isti taj zadatak samo trazi broj 8?

junski rok, sifrovane su grupe, pa ne znam da vam kazem koja sam tacno grupa bila, ali ovo su pitanja:

I deo

1. Sta je tip podatka?
2. Sta su strukture podataka?
3. Neki bubble sort
4. Ovo nesto sa (s+1) % kapacitet niza, znam da je to tacan odgovor, kolega je gore vec postavio pitanje to cini mi se
5. Prostorna kompleksnost za sekvencijalno pretrazivanje - O(n) je tacan odg
6. FIFO - brojevi ulaze ovim redosledom npr 5 8 2 6 4, koji ce izaci drugi po redu ako primenimo FIFO? Znaci 8
7. Jos neko pitanje sa redom, taj isti fazon FIFO ustvari
8. Ako imamo ljude koji cekaju red u banci, i radnica na salteru svakog momenta moze da prozove nekoga ko stoji u redu da pridje salteru (koliko sam ja shvatila moze da prozove bilo koga iz tog reda), za to je onda najbolje primeniti: 1. stek 2. red 3. DS lista ili 4. sve je jednako dobro (ja sam zaokruzila da je najbolja DS lista, ne znam da li je to tacan odgovor)
9. dat je neki niz i neke komande, pa da zaokruzis sta tu na kraju ispada i ostaje u nizu
10. Linearna strktura - to je ono najvise jedan prethodnik i najvise jedan sledbenik
11. ispisan kod
12. Zadatak: ubaciti u DS listu novi cvor na kraj te DS liste, dat je koren DS liste
13. Imamo JS listu, koja mora da sadrzi najmanje tri cvora. Napisati metodu koja izbacuje najveci zbir od neka tri uzastopna elementa u toj listi
14. neki mnogo tezak zadatak, ja ga nikad pre nisam videla!!! Nesto je dato O(n), pa O(log n), nemam pojma kakav kod je tu trebalo da se pise, a fazon 30 poena je nosio, ali nemoguc za uraditi po mom misljenju

II deo

1. nivo stabla
2. uraditi postfix od nacrtanog stabla
3. koji od elemenata nacrtanog stabla ce postati koren, ako izbacimo onaj glavni koren?
4. Ako imamo binarno stablo, visine 6 (koren je visina 1), koliki je najveci moguci broj cvorova koje to stablo moze da ima? Ja sam zaokruzila 63
5. AVL stablo visine 3, koliki je najveci moguci broj cvorova koje moze da ima? Ja sam zaokruzila 7
6. Neki graf
7. Sta ne vazi za AVL stablo, pa ponudjeno svasta, mislim da je odg bio da ne vazi da razlika medju nivoima treba da bude veca od 1
8. Ponudjeno sta je tacno neki iskazi, vezano za primarnu i sekundarnu koliziju, ja sam zaokruzila da je tacno da sekundarna kolizija nesto sa sudarom kljuceva h(k)
9. nesto vezano za roditelja i dete, da se sracuna onaj index
10. nacrtano stablo koje je bilo kompletno i striktno binarno
11. Zadatak iz AVL
12. Zadatak iz B *
i dva koda vezana za stabla, jedan je bio secam se da se izracuna prosecan broj elemenata u stablu (ima u zbirci zadatak), drugi je bio zeznut, nikad vidjen pre

Moze neko da postavi te teske (nikad vidjene) zadatke iz prvog i drugog dela?

_________________
"Deep in the human unconscious is a pervasive need for a logical universe that makes sense. But the real universe is always one step beyond logic."

tezi zadatak je glasio bas ovako: Dat je pokazivac na koren binarnog stable. Napisati metodu koja ispisuje elemente od korena do lista na putanji koja ima najveci zbir.
Da li bi neko bio voljan da napise kod za ovo jer pojma nemam kako da ovo izvedem. Kako da se pamte zbirovi do svakog lista pa onda da se izabere ona putanja sa najvecim zbirom I ona ispise?

ovo je ideja

if (koren.levo == null && koren.desno == null) {
SOP koren.podatak;
return;
}
SOP koren.podatak;
int s1 = suma (koren.levo);
int s2 = suma (koren.desno);
if (s1 > s2)
ispisi (koren.levo)
else
ispisi (koren.desno)


malo treba promeniti ove uslove al to je to u principu, koristi se ona metoda sa vezbi suma(Cvor koren)

Evo ljudi ja sam zapisao onaj ceo zadatak, poslednji iz prvog dela, koji ima pod a i pod b.

Ovako glasi:

Dat je neopadajući sortiran niz koji je pomeren ulevo za k mesta. Odrediti k (offset) ako se zna da nijedan element ne zauzima više od 50% niza.
Ako je veličina niza 6 ili 7, jedan element se ne može ponoviti više od tri puta.
Primer
ulaz: {5, 6, 7, 1, 3}
izlaz: 2

a) ako metoda ima efikasnost O(n)
b) ako metoda ima efikasnost O(logN)

A zadatak sa čuvenom kviz metodom je glasio ovako:



Jedan zadatak iz prvog dela je bio
Dat je pokazivac na prvi cvor dvostruko spregnute liste, napisati algoritam za ubacivanje novog elementa na kraj liste.

A drugi je bio:
Dat je pokazivac na prvi cvor JEDNOSTRUKO spregnute liste, napisati metodu koja vraca najveci zbir neka tri uzastopna elementa u listi. Lista ima minimum 3 elementa.
ja sam to skapirao ovako: (ako recimo imamo JS listu sa ovakvim elementima)
prvi->( 9 ) -> ( 1 ) -> ( 3 ) -> ( 100 ) -> ( 101 ) -> ( 102 ) -> ( 19 ) -> null

maksimalni zbir 3 elementa cine cvorovi sa vrednostima 100, 101, 102 i on iznosi 303.

Ovo je metoda koju sam napisao i proverio u NetBeansu, radi:




ako vam treba objasnjenje koda, tu sam, ali mislim da je prilicno jasno sta se desava...
Siguran sam da postoji rekurzivna verzija koja je bolja.

_________________
Follow me @ http://twitter.com/neverovatan

Za prvi deo, stoji sve sto je stupi napisao, samo ne znam na koju formulu suma sa vezbi je mislio
Ta pomocna suma bi trebalo da izgleda ovako nekako:

U prevodu ista formula kao za visinu, samo umesto visine trazis zbir

A za prvi deo tezi zadatak, koliko vidim za pod a je trebalo uraditi sekvencijalno pretrazivanje, dok je za pod b trebalo odraditi binarno (sa malo promenjenim uslovima, naravno).

_________________
"Deep in the human unconscious is a pervasive need for a logical universe that makes sense. But the real universe is always one step beyond logic."

ja sam mislio na najobicniju sumu koja racuna sumu svih elemenata u stablu
return k.podatak + suma(k.levo)+suma(k.desno);

mislim da bi ovo tvoje vratilo broj koji je suma na jednoj putanji i ta suma je najveca od svih putanja...

al moze i ovakva suma() da se pozove msm da bi radilo isto

Pa bas mislim da ne bi U vecini slucajeva bi radilo ok, ali sigurno moze da se nacrta stabo kod koga bi obicna suma bagovala.


Npr ovde bi sa obicnom sumom, suma levo bila veca od sume desno, ali najveci zbir na putanji je desno

_________________
"Deep in the human unconscious is a pervasive need for a logical universe that makes sense. But the real universe is always one step beyond logic."

e ljudi, ja moram da vas pitam, odakle ste vi svi ovako dobro naucili ove strukture??? Ja presla celu zbirku i nista, samo jedan (onaj laksi) zadatak sam znala, jer je bio iz te zbirke.

Ljudi, pomagajte. Treba da polazem SPA u septembru, a nisam uopste izlazila na ispit. Nisam polozila ni principe programiranja, ne znam da l’ cu moci da spremim ovo. Mozete li da mi preporucite nekog za casove, znam da je mozda rano, al bih krenula sto pre da probam da spremim to za septembar.

evo ja mogu da ti preporucim decka sa faksa koji je mene spremao,stvarno dobro objasnjava..nemoj da te brine to sto nisi dala principe, jer sam ja dala spa preko kol a principe sad u junu i iz njih sam dobila 10, a i to mi je objasnjavao..spa sam nesto zabrjlala i dobila 7,al planiram opet da ga pozovem i da izadjem da popravim u septembru. evo ti link od njegovog oglasa koji je ostavio ovde na forumu pa vidi jel ti odgovara http://www.fonforum.org/viewtopic.php?f=4&p=746549#p746549

Je l moze mala pomoc kako se ubacije u B stablo. Tj ovaj zadatak:

16. Pokazati postupak formiranja B stabla drugog reda celih brojeva kada se u prazno stablo ubacuju
redom elementi: 17, 3, 30, 23, 25, 41, 35. Zatim iz dobijenog stabla izbaciti elemente: 35, 41, 30.
Potrebno je nacrtati svaki korak u postupuku! (15 poena)

Ako neko moze bio bih zahvalan. Moze i samo ubacivanje, snacicu se vec nekako za izbacivanje.

_________________
http://www.youtube.com/watch?v=nKIu9yen5nc#t=0

Dao sam preko kol, tako da mozda nije najpouzdanije ali:


Evo ubacivanje (nadam se da je jasno iz ovoga, kada su u istom cvoru, razdvojio sam ih sa |).
EDIT: Napravio sam gresku kod 2), pisalo je 3 17 a trebalo je 3|17, u istom cvoru su.

_________________
"Deep in the human unconscious is a pervasive need for a logical universe that makes sense. But the real universe is always one step beyond logic."

Jasno skroz. Hvala. Je l moze ovako izbacivanje? Treba da se izbaci 35, 41, 30



Mislim, skroz mi je nelogicno ovo sto sam uradio. Ako neko zna, bio bih zahvalan da pokaze? Hvala puno jos jednom.

_________________
http://www.youtube.com/watch?v=nKIu9yen5nc#t=0

OK je to izbacivanje koje si napisao.

_________________
"Deep in the human unconscious is a pervasive need for a logical universe that makes sense. But the real universe is always one step beyond logic."

Dat je neki niz celih brojeva i iterativni algoritam za interpolaciono pretraživanje. Na kojoj poziciji se nalazi element u nizu kome ptistupa algoritam u trecoj iteraciji, ako se trazi broj 36?

int[] b = { 7, 8, 15, 23, 36 };
public static int interpolaciono(int podatak, int[] n) {
int l = 0;
int d = n.length - 1;
while (l <= d) {
int index = l + (podatak - n[l])/(n[d] - n[l])*(d - l);
if (n[index] == podatak)
return index;
if (n[index] > podatak)
d = index - 1;
else
l = index + 1;
}
return -1;
}

a. 3 b. 4
c. 5 d. naćiće broj pre treće iteracije

Jel moze ovo neko da pojasni i da odgovor?

Teorija, slicna kao i uvek. Zadaci kod stabla, zbir svih elemenata koji su parnih, a drugi zadatak metoda koja proverava da li je dato stablo skoro kompletno binarno. Zadaci iz prvog dela: ubaci u red definisan preko niza, kod js liste da izbaci sve one koji imaju zadatu vrednost, i metoda koja vraca zbir 3 najveca elementa u nizu.

_________________
http://www.youtube.com/watch?v=nKIu9yen5nc#t=0

Da li B stabla dolaze kao stabla reda 2 ili 3?

U junskom i septembarskom su dosla 2. reda. Tako da docice sigurno opet isto.

_________________
http://www.youtube.com/watch?v=nKIu9yen5nc#t=0

Dati su elementi DS liste (1,2,3,4,5). Sta radi sledeca metoda?
X= prvi.sledeci.sledeci;
X.sledeci = x.prethodni.sledeci;
x.prethodni= x.sledeci.prethodni;

a)1,2,4,5 b)1,3,4,5
c)1,2,3,5 d)nista od navedenog

Zna li neko ovo da objasni?

Metoda izbacuje 3.

Nacrtaj pokazivace(strelice) da bi ti bilo jasnije.

X= prvi.sledeci.sledeci; X dobija pokazivac na 3

X.sledeci = x.prethodni.sledeci; X.sledeci je pokazivac na element posle 3, znaci pokazivac na 4 (3->4). Isto tako je X.prethodni pokazivac na 2 (2<-3). x.sledeci = x.prethodni.sledeci znaci da trojka sada ne pokazuje na 4, vec pokazuje na 2 a 2 pokazuje na 4.

x.prethodni= x.sledeci.prethodni; Slicno kao prethodno. 3 ne pokazuje na 2, vec 3 pokazuje na 4 a 4 na 2, tako da se 3 brise.

Ova metoda ne radi nista.

Da je napisano u obrnutom redosledu, onda bi se izbacila 3.

x = prvi.sledeci.sledeci;

x.prethodni.sledeci = x.sledeci; (Ovde 2 pokazuje na 4)

x.sledeci.prethodni = x.prethodni; (Ovde 4 pokazuje na 2)