Zadaci iz prethodnih godina . Neki se mozda ponavljaju - prikupio sam ih sa foruma .
za nizove zadaci: 1) napisati rekurzivni algoritam za binarno pretrazivanje niza 2) dat je pokazivac na pocetak js liste,sortirati je u opadajucem redosledu 3) dat je pokazivac na pocetak js liste koja je sortirana rastuce,napisati f-ju koja stampa elemente opadajuce 4) js lista opet,metoda treba da vrati zbir brojeva koji se ponavljaju (znaci vise od jednom) bio je slican zadatak ranije za brojeve koji se samo 2 puta ponavljaju nadam se da ce biti od koristi
Prvi deo: 1.Ako se redom ubacuju D,C,B,A sta ce uraditi metoda izbaci iz steka? 2.Pretpostavim da imamo red implementiran preko niza i u njega ubacenih 10 elemenata (od niz[5] do niz[15]) . Sa koje pozicije ce metoda dequeue() izbaciti element? Moze da pita i na koju poziciju ce metoda enqueue() ubaciti novi element? 3.Bilo je za merge i quick sort , kojoj kategoriji pripadaju? 4.Ako kazemo za neku strukturu da je FIFO /LIFO ,sta to znaci ?
Napisati algoritam za ubacivanje elemenata u red implementiran preko niza, da li sad na ispitu treba da ne se napise samo metoda ENQUEUE, ili je potrebno ispisati pre toga i onaj konstruktor za dimenziju, niz, prvi poslednji element, tu implementaciju? znaci generalno da li je dovoljno ispisati metodu iz zbirke ili traze jos neki uvodni deo zadatka?
1. Napisati metodu koja ubacuje elemnt u niz implementiran preko reda. 2. Dat je pokazivac na cvor DS liste, napisati metodu koja ce izracunati zbir parnih brojeva na neparnim mestima.
1. Napisati funkciju koja implementira rekurzivni algoritam za binarno pretrazivanje niza celih brojeva sortiranog u rastucem redosledu. (6 poena) 2. a) Napisati klasu koja definishe implementaciju reda celih brojeva preko niza. b) Napisati metodu koja pokazuje sve elemente reda u redosledu od poslednje ubachenog do prvog. (2 + 6 poena) 3. Dat je pokazivach na pochetak dvostruko spregnute liste celih brojeva. Napisati funkciju koja ce poslednji cvor prebaciti na prvo mesto. Metoda treba da ima sledece zaglavlje: void Prebaci(CvorDSListe pocetak). Nije dozvoljeno kreiranje novih chvorova, niti menjanja vrednosti postojecih. (9 poena) 4. Dati su pokazivachi na pochetak dve dvostruko spregnute liste celih brojeva. Napisati medotu CvorDSListe Unija(CvorDSListe p1, CvorDSListe p2) koja ce napraviti trecu listu koja predstavlja uniju prve i druge liste u smislu skupova (sadrzace sve elemente iz obe liste, ali bez ponavljanja). Na kraju operacije pochetne liste treba da ostanu nepromenjene. (11 poena) ps, ovo je Kosta kasnije naglasio: Elementi samo u prvoj ili samo u drugoj se ne ponavljaju, ali mogu imati iste zajednichke elemente. Takodje, neka moze biti prazna) 5. Objasnite algoritam za sortiranje umetanjem (Insertion sort). (3 poena) 6. Koja je razlika izmedju staka i reda kao linearnih struktura podataka? (3 poena)
A u temi od pretprosle godine...
PRVA GRUPA 1. Napisati metodu "Gurni" koja implementira algortam za ubacivanje novog elementa u stak celih brojeva koji je implementiran kao jednostruko spregnuta lista. (6 poena) 2. Dat je niz celih brojeva sortiran u rastucem redosledu. Impelmentirati rekurzivni algoritam za binarno pretrazivanje datog niza. (7 poena) 3. Dat je pokazivac na neki cvor dvostruko spregnute liste. Napisati funkciju koja ce poslednji cvor prebaciti na prvo mesto. (Ne menjati samo vrednosti, vec pokazivace!) (10 poena) 4. Dati su pokazivaci na pocetak dve dvostuko spregnute liste celih brojeva. Napisati metodu koja ce napraviti jednostruko spregnutu listu koja predstavlja razliku (u smislu skupova) prve i druge liste i vratiti pokazivac na pocetak nove liste. (11 poena) 5. Kada se kaze da algoritam ima vremensku kompexnost O(n) onda to znaci ... 6. Sta je tip podatka, a sta struktura podatka?
Трећа група је иста као и прва с тим шти је у другом било итеративно претраживање рекурзивно.
II grupa: 1. Metoda izbaci za red preko niza 2. Niz opadajuci, treba iterativni algoritam za binarno pretrazivanje. 3. isto samo sa prvog na poslednje mesto. 4. isto samo drugi razlika prvi. 5. isto. 6. razlika izmedju staka i reda.
IV grupa: 1. Metoda "Ubaci" u red implementiran preko niza. 2. Rastuci niz, implementirati rekurzivni algoritam za sekvencijalno pretrazivanje. 3. DS Lista, dat je pokazivac na neki cvor, prebaciti taj cvor na poslednje mesto. 4. Dve DS Liste, napraviti trecu, JS Listu koja predstavlja razliku (u smislu skupova) druge i prve liste. 5. Kada se kaze da algoritam ima vremensku kompeksnost O(n) onda to znaci... 6. Razlika izmedju staka i reda.
Dati su pokazivachi na pochetak dve dvostruko spregnute liste celih brojeva. Napisati medotu CvorDSListe Unija(CvorDSListe p1, CvorDSListe p2) koja ce napraviti trecu listu koja predstavlja uniju prve i druge liste u smislu skupova (sadrzace sve elemente iz obe liste, ali bez ponavljanja). Na kraju operacije pochetne liste treba da ostanu nepromenjene.
Zadatak : Napisati funkciju transformisi(STAK s1, STAK* s2) koja će od steka koji je implementiran kao jednostruko spregnuta lista formirati novi stek koji je implementiran preko niza?
metoda koja impementira algoritam za binarno pretrazivanje niza celih brojeva sortiranog u opadajucem redosledu
Jednostruko-spregnuta lista, izbaciti poslednji element u nizu. Neki od algoritama za pretrazivanje Quick Sort
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.
1. Dat je pokazivač na neki čvor dvostruko spregnute liste. Napisati funkciju za ubacivanje novog elementa pre datog pokazivača. Zanemariti pokazivače Head i Tail (nema potrebe da ih koristite). (12 poena)
2. Dat je pokazivač na početak reda celih brojeva, koji je implementiran kao jednostruko spregnuta lista. Napisati funkciju int Prebroj(CvorListe Vrh) koja će vratiti koliko elemenata reda ima vrednost veću od početnog elementa. (12 poena)
3. Data je dvostruko spregnuta (DS) lista čiji su elementi čvorova pokazivači na početak jednostruko spregnute (JS) liste. Napisati klasu koja opisuje čvor ovakve DS liste, a zatim napisati algoritam za ubacivanje novog elementa u ovako definisanu strukturu, koji funkcioniše po sledećem principu: kreće se od početka DS liste. Ako je element koji se ubacuje manji od prvog elementa JS liste trenutnog čvora DS liste, onda se taj element ubacuje na kraj te JS liste. U suprotnom, prelazi se na sledeći čvor DS liste i algoritam se ponavlja. Ako se stigne do kraja DS liste, onda se kreira novi čvor i u njegovu JS listu se ubacuje novi element. Početna metoda prihvata pokazivač na početak DS liste i ceo broj koji se ubacuje. (16 poena)
Sve se vrtelo oko glupavih pretrazivanja i sortova. Pitanja su bila tipa sta je zajednicko quick i merge sortu, koja je kompleksnost ovog/onog, koja je najbolja kompleksnost... A ja to nisam imao pojma nista. - Da se prepozna onaj deo enqueue komande gde je onaj % (StatickiRed) - Nesto tipa da se ispravi greska u binarnom pretrazivanju (dat source code, i podvucena jedna linija, da da zaokruzis sta tu treba da stoji - koliko se secam, trebalo je umesto s+1 da stoji s-1...). - Dali su niz brojeva kao tabelicu, npr. |2| 5 |7|8|12| | | gde su bili pokazivaci p na 2, i k na 12. Onda je dato ovako nesto: |4|17|7|8|12|34|11|. A pokazivaci: p na 7, a k na 17. Pitanje je glasilo. Koji niz komandi daje od prvog niza, ovaj sledeci. Pa komande: a) ubaci(34), izbaci(), ubaci(11), izbaci(), ubaci(4), ubaci(17)... b) ubaci(34),ubaci(11),ubaci(4)... c) ... d) nemoguce je dobiti iz prve slike ovakvu strukturu Ja sam oznacio ovo pod a)
- Bila su pitanja sta je struktura podataka a sta je tip podatka.
Sve je bilo na zaokruzivanje, 11 pitanja.
Zadaci
12. Data je dvostruko-spregnuta lista celih brojeva sa pokazivacem na prvi element. Pronaci prvi element liste koji je manji od trazenog (onog koji se dobije kao parametar) i pomeri ga na pocetak liste (12b) 13. Data je jednostruko-spregnuta lista celih brojeva sa pokazivacem na prvi element. Pronadji najmanji element liste i pomeri ga na pocetak. (ovde je islo jos nesto tipa neki uslov ako je na pocetku... Javite da editujem... ) 14. Date su dve jednostruko spregnute liste ciji su elementi poredjani u opadajucem redosledu. Napravi trecu listu, koja ce sadrzati sve elemente ove dve liste, da oni budu u neopadajucem redosledu, i da algoritam ima kompleksnost O(m+n) pri cemu su m i n brojevi elemenata u listama. Pri tom je neophodno da dve polazne liste ostanu netaknute. 15. Pokazati algoritam iterativnog interpolacionog pretrazivanja (tako nekako, skroz je cudno bilo definisano pitanje, niko nije znao sta tacno tu treba da se pise, valjda ona formula Pk=...)
prvi deo: 1.tip podataka 2.strukture podataka 3.LIFO struktura, sta znaci ( ubaci i izbaci sa istog kraja) 4.za binarno pretrazivanje je potrebno....(da je niz sortiran) 5.Interpolaciono pretrazivanje, najgori slucaj 6.merge sort i quick sort,sta ima je zajednicko ( podeli pa vladaj) 7.nesto za O(n), sta znaci n..
Što se tiče zadataka iz prvog dela: 1) Dat je pokazivač na kraj DSListe, napiši metodu koja ubacuje novi element na kraj DSListe 2)Dve JSListe su implementirane preko Stringa, potrebno je da proveriš da li slova iz prvog stringa mogu da se iskoriste u drugom stringu (npr. prvi string je dosta, treba proveriti da li reč jednostavno ima ta slova). (public boolean daLiMoze(CvorJSL L1, CvorJSL L2)) 3) Dat je pokazivač DSListe, treba ispisati tu listu inverzno. Ako se koristi neka pomoćna struktura, to donosi 18 poena, ako ne, zadatak nosi 28 poena. Teorija 1) Šta je tip podataka? 2) Šta je struktura podataka? 3) Merge i Quick sort pripadaju čemu (Podeli i vladaj) 4) Dat je niz, nakon prvog prolaska Quick sorta, kako treba da izgleda niz? 5) Isto kao 4) samo za Bubble sort. 6) Dato je opadajući niz i ima binarno pretraživanje, jedna linija koda je bolidrana, treba proveriti da li je tačna. 7) Šta znači O(n)? 8.) U stek se ubacuju slova DBAC, tim redom, napiši kojim redom izlaze iz steka. 9) Dati su elementi DSListe (1,2,3,4,5), šta radi sledeća metoda: x=prvi.sledeci.sledeci; x.sledeci=x.prethodni.sledeci; x.prethodbi=x.sledeci.prethodni; (treba 3 da ne stane) 10) Dat je indeks poslednjeg elementa niza. Kako glasi formula za sledeći indeks tog niza (to je ono s dimenzija %, ne mogu da se setim šta sam zaokružio, znam da sam na primeru to odradio) 11) Nešto vezano za cikličnu DSListu.
1. Kada se kaže da algoritam ima kompleksnost O(n) onda to znači da: a) Vreme izvršavanja algoritma je proporcionalno sa n b) Vreme izvršavanja algoritma je manje od n sekundi c) Algoritam ima n ugnježdenih petlji d) Algoritam je n puta sporiji od standardnog algoritma
Јел овде под а) тачно?
Zadaci 1.ubacivanje elementa u red 2.JS lista da se izbaci tekuci element 3.DS lista da se stavi u sort
|