Pitanja i odgovori (5).pdf

STRUKTURE PODATAKA PITANJA I ODGOVORI IPI AKADEMIJA TUZLA I ALGORITMI 1. Šta sadrži pokazivač inicijaliziran na varijablu tipa float? _______________________________________________________________________. ODGOVOR: adresu varijable 2. Varijablu a na koju po...

STRUKTURE PODATAKA PITANJA I ODGOVORI IPI AKADEMIJA TUZLA I ALGORITMI 1. Šta sadrži pokazivač inicijaliziran na varijablu tipa float? _______________________________________________________________________. ODGOVOR: adresu varijable 2. Varijablu a na koju pokazuje pokazivač p moguće je izmjeniti: a) isključivo preko naziva varijable, b) isključivo preko pokazivača, c) nije moguće izmjeniti, d) preko naziva varijable i pokazivača. ODGOVOR: d) preko naziva varijable i pokazivača 3. Pokazivač može pokazivati na varijablu drugog tipa u odnosu na tip pokazivača. TAČNO NETAČNO ODGOVOR: NETAČNO 4. Kako se vrši inicijalizacija/postavljanje vrijednosti pokazivača p na varijablu a? ODGOVOR: tip *p = &a; 5. Pokazivač koji je deklarisan, ali ne i inicijaliziran: a) važeći je isključivo za čitanje, b) važeći je isključivo za pisanje, c) sadrži adresu na početku radne memorije, d) važeći je za čitanje i pisanje. ODGOVOR: b) važeći je isključivo za pisanje 6. Kako je moguće vršiti prosljeđivanje varijabli u funkciju? ________________________________________________________________________________________ _________________________________________________________________________. ODGOVOR: po vrijednosti (kopiraju se vrijednosti) i po referenci (kopiraju se adrese) 7. Prosljeđivanje varijabli u funkciju može se vršiti po __________________________ i po ________________________. ODGOVOR: vrijednosti; referenci; 8. Kako je moguće mijenjati vrijednost varijable lokalne za drugu funkciju? ________________________________________________________________________________________ ________________________________________________________________________. ODGOVOR: prosljeđivanjem pokazivača na tu varijablu u funkciju iz koje se mijenja. 9. Vrijednost pokazivača je uvijek adresa varijable. TAČNO NETAČNO ODGOVOR: NETAČNO 10. Vrijednost inicijaliziranog pokazivača je adresa varijable na koju je inicijaliziran. TAČNO NETAČNO ODGOVOR: TAČNO 11. Za dinamičko dodjeljivanje memorije u C jeziku koriste se funkcije: a) malloc, calloc i realloc, b) falloc, malloc i free, c) malloc, calloc i free, d) malloc, realloc i free. ODGOVOR: d) malloc, realloc i free. 12. U slučaju unaprijed nepoznate veličine niza u C jeziku poželjno je koristiti ______________________________________________________________________________. ODGOVOR: dinamičko dodjeljivanje memorije. 13. Kako izgleda deklaracija malloc funkcije? _____________________________________________. ODGOVOR: void *malloc(size_t size); Strana 1 od 15 STRUKTURE PODATAKA PITANJA I ODGOVORI IPI AKADEMIJA TUZLA I ALGORITMI 14. Funkcije za dinamičko dodjeljivanje memorije nalaze se u zaglavlju a) malloc.h, b) alloc.h, c) dynmem.h, d) memalloc.h. ODGOVOR: malloc.h 15. Povratni tip podatka iz malloc i realloc funkcije je prazan pokazivač. TAČNO NETAČNO ODGOVOR: NETAČNO 16. Malloc i realloc funkcije vraćaju _______________________________ pokazivač na ______________________________________________________________________________. ODGOVOR: univerzalni; dinamički dodjeljeni blok memorije; 17. Realloc funkcija kao argument prima: a) broj varijabli za koje treba povećati dinamički dodjeljen blok memorije, b) pokazivač i veličinu za koju treba povećati dodjeljeni blok memorije, c) pokazivač i novu veličinu dinamički dodjeljenog bloka memorije, d) stari i novi pokazivač, te novu veličinu dinamički dodjeljenog bloka memorije. ODGOVOR: c) pokazivač i novu veličinu dinamički dodjeljenog bloka memorije 18. Algoritam je ____________________________________________________________________ _____________________________________________________________________________. ODGOVOR: konačan skup naredbi koji završava određeni zadatak. 19. Kriteriji koje svaki algoritam treba zadovoljiti su ________________________________________________________________________________________ ________________________________________________________________________. ODGOVOR: ulaz, izlaz, određenost, konačnost i učinkovitost; 20. Algoritam je: a) precizno opisan način rješenja nekog problema, b) skup pravila za postizanje željenog rezultata, c) jednoznačno određen tok radnji, d) sve gore navedeno. ODGOVOR: d) sve gore navedeno 21. Algoritam se sastoji od ________________________________________, ____________________ _____________________________ i ____________________________. ODGOVOR: početnih objekata; završnih objekata (rezultata); instrukcija; 22. Nabroj 4 izazova u postupku izrade algoritama. ________________________________________ ______________________________________________________________________________. ODGOVOR: dizajn, validacija, analiza, testiranje; 23. _______________________________________ algoritma znači konačno vrijeme izvršavanja, a __________________________ algoritma znači da je uspješan u odnosu na dodjeljene resurse. ODGOVOR: djelotvornost; učinkovitost; 24. Koji uslov ne mora zadovoljiti program (procedura), a algoritam mora? ______________________________________________________________________________. ODGOVOR: uslov konačnosti 25. Algoritam se može predstaviti a) mašinskim jezikom, b) pseudokôdom, c) kompajlerom, d) dijagramom toka. ODGOVOR: b) pseudokôdom; d) dijagramom toka; 26. Navedi 2 primjera procedura. ______________________________________________________. Strana 2 od 15 STRUKTURE PODATAKA PITANJA I ODGOVORI IPI AKADEMIJA TUZLA I ALGORITMI ODGOVOR: operativni sistem; uređivač teksta. 27. Program je algoritam koji je ______________________________________________________ _____________________________________________________________________________. ODGOVOR: prilagođen i zapisan u obliku za izvršavanje na računaru; 28. Složenost algoritma može se analizirati _____________________________________________ i ________________________________________________________________. ODGOVOR: a priori (analiza); a posterirori (mjerenja) 29. Prostorna složenost algoritma je: a) količina programskog kôda za zapis algoritma, b) količina memorije potrebna za izvršavanje, c) broj varijabli u programu, d) količina procesorskog vremena potrebna za izvršavanje. ODGOVOR: b) količina memorije potrebna za izvršavanje 30. Vremenska složenost algoritma je: a) količina procesorskog vremena potrebna za izvršavanje, b) količina memorije potrebna za izvršavanje, c) vrijeme dana u kojem se algoritam mora izvoditi, d) broj operacija koje se trebaju izvršiti. ODGOVOR: a) količina procesorskog vremena potrebna za izvršavanje 31. Šta je algoritam? _______________________________________________________________ ____________________________________________________________________________. ODGOVOR: Algoritam je konačan skup naredbi koji, ukoliko se prati, završava određeni zadatak 32. Algoritam mora zadovoljiti sljedeće kriterije: _________________________________________ ____________________________________________________________________________. ODGOVOR: ulaz; izlaz; određenost; konačnost; učinkovitost; 33. Algoritam je: a) jednoznačno određen tok radnji, b) skup pravila za postizanje željenog rezultata, c) precizno opisan način rješenja nekog problema, d) sve gore navedeno. ODGOVOR: d) sve gore navedeno 34. Algoritam se sastoji od sljedeće 3 stvari: __________________________________________, ______________________________________ i ____________________________________. ODGOVOR: početnih objekata; završnih objekata (rezultata); instrukcija; 35. Algoritam je precizno opisan način rješenja nekog problema. TAČNO NETAČNO ODGOVOR: TAČNO 36. Izvršavanje algoritma ne predstavlja algoritamski proces. TAČNO NETAČNO ODGOVOR: NETAČNO 37. Algoritam je neupotrebljiv ako se dobije rezultat u konačnom vremenu. TAČNO NETAČNO ODGOVOR: NETAČNO 38. Učinkovitost algoritma je sposobnost: a) da proizvede izlaz na osnovu ulaza, b) da proizvede izlaz brzo u odnosu na date resurse, c) da se algoritmom jednostavno opiše složen problem, d) da brzo proizvede izlaz. ODGOVOR: b) da proizvede izlaz brzo u odnosu na date resurse Strana 3 od 15 STRUKTURE PODATAKA PITANJA I ODGOVORI IPI AKADEMIJA TUZLA I ALGORITMI 39. Koja je razlika između djelotvornog (effective) i učinkovitog (efficient) algoritma? ________________________________________________________________________________________ ________________________________________________________________________________________ _________________________________________________________________. ODGOVOR: Djelotvoran algoritam ima konačno vrijeme izvršavanja, dok učinkovit algoritam ima relativno kratko vrijeme izvršavanja u odnosu na dodjeljene resurse. 40. Množenje sabiranjem je učinkovito. TAČNO NETAČNO ODGOVOR: NETAČNO 41. Algoritam se može predstaviti na više načina: ________________________________________, ______________________________ i _____________________________________________. ODGOVOR: prirodnim jezikom; pseudokôdom; grafički (dijagram toka); 42. Program je implementacija algoritma koja ne mora zadovoljavati uslov konačnosti. TAČNO NETAČNO ODGOVOR: TAČNO 43. Primjeri procedura su: ___________________________________________________________ ____________________________________________________________________________. ODGOVOR: operativni sistem; uređivač teksta; 44. Prostorna složenost algoritma je __________________________________________________ ____________________________________________________________________________. ODGOVOR: količina memorije potrebna za njegovo izvršavanje. 45. Vremenska složenost algoritma je _________________________________________________ ____________________________________________________________________________. ODGOVOR: količina procesorskog vremena potrebna za njegovo izvršavanje. 46. Analiza složenosti algoritama najčešće obuhvata sljedeće analize: a) a pentori i a posteriori, b) a pitagori i a ponteori, c) a priori i a posteriori, d) a priori i a pentori. ODGOVOR: c) a priori i a posteriori 47. Prilikom dizajna algoritama poželjno je podijeliti procedure u logičke podfunkcije. TAČNO NETAČNO ODGOVOR: TAČNO 48. A posteriori analiza algoritama vrši se ______________________________________________ ____________________________________________________________________________. ODGOVOR: mjerenjem vremena izvršavanja algoritma na određenom skupu podataka. 49. Navedite neke prednosti modularnosti u programiranju. ________________________________________________________________________________________ ________________________________________________________________________________________ __________________________________________________________________. ODGOVOR: paralelan dizajn; čitljivost kôda; smanjenje broja greški; olakšava održavanje programa; 50. Koja je svrha analize složenosti algoritama? ________________________________________________________________________________________ ________________________________________________________________________. ODGOVOR: predviđanje vremena izvršavanja i pronalazak učinkovitijih algoritama. 51. U analizi složenosti algoritama pretpostavlja se da je vrijeme obavljanja operacija ograničeno nekom konstantom kao donjom granicom. TAČNO NETAČNO ODGOVOR: NETAČNO 52. Analiza performansi algoritma vrši se za sljedeće slučajeve: _____________________________, __________________________ i _________________________________. ODGOVOR: najbolji; prosječan; najgori; Strana 4 od 15 STRUKTURE PODATAKA PITANJA I ODGOVORI IPI AKADEMIJA TUZLA I ALGORITMI 53. Kao funkcija čega se vrši a priori analiza trajanja izvođenja algoritma? ____________________________________________________________________. ODGOVOR: broja podataka 54. A priori analiza algoritma vrši se: a) prije pisanja algoritma, b) prije implementacije algoritma u programskom jeziku, c) prije i nakon implementacije, d) nakon izvršavanja algoritma na računaru. ODGOVOR: b) prije implementacije algoritma u programskom jeziku 55. A posteriori analiza algoritma vrši se ________________________ implementacije algoritma u programskom jeziku i dobija se ____________________________________________________. ODGOVOR: nakon; mjerenjem na računaru; 56. A priori analiza vrši se neovisno od vrste računara, programskog jezika i kompajlera. TAČNO NETAČNO ODGOVOR: TAČNO 57. O – notacijom složenosti algoritama predstavlja se: a) najbolje vrijeme izvođenja, b) prosječno vrijeme izvođenja, c) najgore vrijeme izvođenja, d) ni jedno od navedenog. ODGOVOR: c) najgore vrijeme izvođenja 58. Ako je algoritam ovisan o ulaznom argumentu n oblika polinoma m – tog stepena, onda je vrijeme izvođenja za taj algoritam __________. ODGOVOR: O(nm) 59. Vrijeme izvođenja algoritma ne ovisi o najvećoj vremenskoj konstanti. TAČNO NETAČNO ODGOVOR: NETAČNO 60. Složenost O(1) znači da je vrijeme izvođenja: a) ograničeno promjenjivom vrijednosti manjom od 1, b) ograničeno konstantom, c) nije moguće utvrditi, d) ograničeno, ali jako složeno za izvršavanje. ODGOVOR: b) ograničeno konstantom 61. Za složenost O(2^n) postoje tačno 2 polinoma koja ga mogu ograničiti i time riješiti u razumnom vremenu. TAČNO NETAČNO ODGOVOR: NETAČNO 62. U odnosu na složenost O(n) jednostavnija je: a) O(n^3), b) O(nlogn), c) O(2^n), d) O(logn). ODGOVOR: d) O(logn) 63. Ω – notacijom složenosti algoritama predstavlja se: a) najbolje vrijeme izvođenja, b) prosječno vrijeme izvođenja, c) najgore vrijeme izvođenja, d) ni jedno od navedenog. ODGOVOR: a) najbolje vrijeme izvođenja Strana 5 od 15 STRUKTURE PODATAKA PITANJA I ODGOVORI IPI AKADEMIJA TUZLA I ALGORITMI 64. ϴ – notacijom složenosti algoritama predstavlja se: a) najbolje vrijeme izvođenja, b) prosječno vrijeme izvođenja, c) najgore vrijeme izvođenja, d) ni jedno od navedenog. ODGOVOR: b) prosječno vrijeme izvođenja 65. Najpreciznije vrijeme izvođenja algoritma je: a) prosječno, b) najbolje, c) najgore, d) asimptotsko. ODGOVOR: d) asimptotsko 66. Drastično sporija vremena izvođenja u odnosu na logaritamska su: a) O(n!), b) O(n), c) O(n^x), d) O(2^n). ODGOVOR: a) O(n!); c) O(nx); d) O(2n) 67. Za a posteriori analizu može se koristiti C biblioteka __________________, koja sadrži funkciju __________________. ODGOVOR: timeb.h; ftime(); 68. Za učinkovito pretraživanje podataka potrebno je da su podaci organizovani kao par _______________________________________. ODGOVOR: ključ -> vrijednost 69. Kompozitni ključ je a) ključ sastavljen od više atributa, b) ključ koji pokazuje na drugi ključ, c) ključ sa ponavljajućim vrijednostima, d) ključ čija je vrijednost drugi ključ. ODGOVOR: a) ključ sastavljen od više atributa 70. Sekundarni ključ je primarni ključ u drugoj tabeli (zapisu, entitetu). TAČNO NETAČNO ODGOVOR: TAČNO 71. Kod serijskog pretraživanja zapisi ne moraju biti sortirani. TAČNO NETAČNO ODGOVOR: TAČNO 72. Kod serijskog pretraživanja složenost je ____________, a prosječno se čita ____________ zapisa. ODGOVOR: O(n); n/2; 73. Najbolji slučaj kod serijskog pretraživanja je a) O(n/2), b) O(logn), c) O(n), d) O(1). ODGOVOR: d) O(1) 74. Za direktne, sortirane datoteke serijsko pretraživanje može se ubrzati _____________________ ____________________________________________________________________________. ODGOVOR: dijeljenjem datoteke u blokove zapisa. Strana 6 od 15 STRUKTURE PODATAKA PITANJA I ODGOVORI IPI AKADEMIJA TUZLA I ALGORITMI 75. Svaki blok datoteke ima karakteristiku koja omogućava pretraživanje, a to je a) ključ, b) vodeći zapis, c) informaciju o veličini i broju zapisa u bloku, d) adresu memorijske lokacije. ODGOVOR: b) vodeći zapis 76. Kod serijskog pretraživanja, za datoteku sa F zapisa optimalna veličina bloka B je ________. ODGOVOR: korijen iz F 77. ____________________________________ pretraživanje je bolje od serijskog, a lošije od _____________________________________ pretraživanja. ODGOVOR: serijsko blokovsko; binarnog; 78. Za binarno pretraživanje podaci ne moraju biti sortirani. TAČNO NETAČNO ODGOVOR: NETAČNO 79. Prosječan broj čitanja kod binarnog pretraživanja je: a) O(2n), b) O(logn), c) O(log2n-1), d) O(log10n). ODGOVOR: c) O(log2n-1) 80. Binarno pretraživanje nije efikasno za medije sa direktnim pristupom poput DVD uređaja. TAČNO NETAČNO ODGOVOR: TAČNO 81. Na kojem glavnom principu se zasniva binarno pretraživanje? _____________________________________________________________________________. ODGOVOR: Zasniva se na polovljenju niza za pretragu. 82. Prednost indeksiranja datoteke je __________________________________________ podataka. ODGOVOR: brže pretraživanje 83. Raspršeno adresiranje (eng. hashing) je: a) razdvajanje adrese podatka na više segmenata, b) spremanje 2 dijela adrese (viši i niži) na 2 različite, nasumične memorijske lokacije, c) raspoređivanje više podataka na istu adresu, d) postupak transformacije ključa zapisa u adresu ili neki drugi broj. ODGOVOR: d) postupak transformacije ključa zapisa u adresu ili neki drugi broj 84. Hash funkcija je reverzibilna (može na osnovu datog izlaza proizvesti originalni ulaz). TAČNO NETAČNO ODGOVOR: NETAČNO 85. Ulaz u hash funkciju je _______________________________________, a izlaz je _________________________________________________________. ODGOVOR: ključ zapisa; pseudo – slučajni broj; 86. Za dati kapacitet bloka C i broj blokova M, gustoća pakiranja G za N zapisa prilikom raspršenog adresiranja računa se kao: _____________________________. ODGOVOR: G = N/(MC) 87. Šta se koristi u slučaju da raspršeno adresiranje popuni određeni blok? ________________________________________________________________________________________ ________________________________________________________________________________________ ___________________________________________________________________. ODGOVOR: Zapisi se snimaju u preljevni blok, a u originalnom bloku se snimi adresa zapisa u preljevnom bloku. Strana 7 od 15 STRUKTURE PODATAKA PITANJA I ODGOVORI IPI AKADEMIJA TUZLA I ALGORITMI 88. Idealnom transformacijom u hash funkciji za M zapisa vjerovatnoća da će se pojaviti 2 različita ključa sa istom adresom je: a) 1/2M, b) 0.001%, c) 1/M, d) M. ODGOVOR: c) 1/M 89. Navedi 4 karakteristike dobre transformacije ulaza u izlaz hash funkcije. ________________________________________________________________________________________ ________________________________________________________________________________________ ____________________________________________________________________. ODGOVOR: izlaz je isključivo funkcija ulaza; korištenje svih ulaznih podataka; ravnomjerno raspoređivanje izlaza; za slične ulazne podatke daju se dosta različiti izlazi; 90. Raspršeno adresiranje je pogodno za brzo i često pretraživanje podataka. TAČNO NETAČNO ODGOVOR: TAČNO 91. Raspršeno adresiranje nije pogodno za: a) provjeru jednakosti, b) baze sa čestim brisanjem zapisa, c) provjeru gramatičkih grešaka u tekstu, d) baze gdje se obrađuju svi zapisi. ODGOVOR: b) baze sa čestim brisanjem zapisa; d) baze gdje se obrađuju svi zapisi 92. Navedi tri prednosti korištenja virtuelne memorije. ________________________________________________________________________________________ ________________________________________________________________________________________ ________________________________________________________________________________________ ________________________________________________________________________________________ _______________________________________________________. ODGOVOR: mogućnost izvršenja programa koji je djelomično učitan u memoriju; manji broj ulazno – izlaznih operacija kod učitavanja programa; neograničavanje programa veličinom fizičke memorije; 93. Mana korištenja virtuelne memorije je ________________________________________________ ____________________________________________________________________________. ODGOVOR: Brzina pristupa zbog korištenja različitih fizičkih memorija 94. Proces je pokrenuta instanca programa učitana u radnu memoriju računara. TAČNO NETAČNO ODGOVOR: TAČNO 95. Ako se procesu dodijeli radna memorija na adresama [300,1000], onda su adrese dostupne procesu u opsegu: a) [300,1000], b) [0,700], c) [300,500], d) [500,1000]. ODGOVOR: b) [0,700] 96. Pokrenuti program je zadužen za preslikavanje adresa iz virtuelne u fizičku memoriju. TAČNO NETAČNO ODGOVOR: NETAČNO 97. Virtuelna memorija se: a) može dijeliti između procesa, b) može dijeliti samo u zajedničkom dijelu između procesa, c) ne može dijeliti između procesa, d) na zathjev operativnog sistema može privremeno dodjeliti drugom procesu. Strana 8 od 15 STRUKTURE PODATAKA PITANJA I ODGOVORI IPI AKADEMIJA TUZLA I ALGORITMI ODGOVOR: c) ne može dijeliti između procesa 98. Nabroj segmente virtuelne memorije u Windows OS-u. _______________________________________________________________________________. ODGOVOR: TEXT, DATA, BSS, HEAP, STACK; 99. DATA segment virtuelne memorije služi za: a) inicijalizirane globalne i statičke lokalne varijable, b) dinamički dodjeljenu memoriju, c) lokalne varijable u funkijama, d) instrukcije programa. ODGOVOR: a) inicijalizirane globalne i statičke lokalne varijable 100. HEAP segment virtuelne memorije služi za: a) inicijalizirane globalne i statičke lokalne varijable, b) dinamički dodjeljenu memoriju, c) lokalne varijable u funkcijama, d) instrukcije programa. ODGOVOR: b) dinamički dodjeljenu memoriju 101. Lokalne varijable u funkcijama nalaze se na HEAP segmentu virtuelne memorije. TAČNO NETAČNO ODGOVOR: NETAČNO 102. Instrukcije programa nalaze se u TEXT segmentu virtuelne memorije. TAČNO NETAČNO ODGOVOR: TAČNO 103. Memorija se dodjeljuje procesu na HEAP dijelu pomoću ________________________________. ODGOVOR: malloc() funkcije 104. Stog služi za smještanje _________________________________________________________ i _____________________________________________________________________________. ODGOVOR: privremenih varijabli; povratnih adresa; 105. Stog koristi sljedeće principe: a) NIFO, b) FIFO, c) SIFO, d) LIFO. ODGOVOR: d) LIFO 106. Šta sadrži okvir stoga? ____________________________________________________________ _____________________________________________________________________________. ODGOVOR: povratnu adresu; lokalne varijable; ulazne argumente; registre procesora; 107. Registri procesora smješteni su u TEXT segmentu virtuelne memorije. TAČNO NETAČNO ODGOVOR: NETAČNO 108. Prilikom pokretanja programa na stogu se nalazi okvir: a) za statičke varijable, b) svih funkcija u programu, c) svih inicijaliziranih varijabli, d) main() funkcije. ODGOVOR: d) main() funkcije 109. šta je rekurzivna procedura? ________________________________________________________________________________________ ________________________________________________________________________. ODGOVOR: To je procedura koja u proračunu rezultata poziva samu sebe. Strana 9 od 15 STRUKTURE PODATAKA PITANJA I ODGOVORI IPI AKADEMIJA TUZLA I ALGORITMI 110. Rekurzivna procedura obavezno mora imati a) manje od 10 poziva, b) osnovni slučaj, c) uslov kraja, d) uslov naglog prekida procedure. ODGOVOR: b) osnovni slučaj; c) uslov kraja; 111. Za pohranjivanje podataka u rekurzivnim procedurama koristi se HEAP segment. TAČNO NETAČNO ODGOVOR: NETAČNO 112. Fibonaccijev rekurzivni algoritam se značajno usložnjava povećanjem broja n za F(n). TAČNO NETAČNO ODGOVOR: TAČNO 113. Rekurzivna procedura mora uvijek napredovati prema osnovnom slučaju. TAČNO NETAČNO ODGOVOR: TAČNO 114. Rekurzivni postupak je jednostavniji za napisati i za izvođenje u odnosu na obični. TAČNO NETAČNO ODGOVOR: NETAČNO 115. Polovljenjem veličine problema složenost funkcije se izražava kao a) O(n/2), b) O(nlog2n), c) O(log2n), d) O(n^2). ODGOVOR: c) O(log2n) 116. Selection sort radi tako što nađe _______________________________ član niza i zamjeni ga sa _________________________________ članom niza. ODGOVOR: najmanji; prvim; 117. U algoritmu selection sorta vanjska petlja ____________________________________________ _________________________________________, a unutrašnja petlja _____________________ ______________________________________________________________________________. ODGOVOR: određuje granice sortiranog dijela niza; traži najmanji član niza; 118. Složenost selection sorta je a) O(n), b) O(logn), c) O(n^2), d) O(n/2). ODGOVOR: c) O(n2) 119. Najgori slučaj kod selection sorta je ________________________________________________. ODGOVOR: naopako sortiran niz 120. Na kojem principu radi bubble sort? _________________________________________________ _____________________________________________________________________________. ODGOVOR: Na principu zamjene susjednih članova, ukoliko nisu u dobrom redoslijedu. 121. Najgori slučaj kod bubble sorta je: a) naopako sortiran niz, b) već sortiran niz, c) niz sa približno istim vrijednostima članova, d) niz sa dosta članova sa istom vrijednosti. ODGOVOR: a) naopako sortiran niz 122. Insertion sort radi tako da se uzme ___________________ član nesortiranog dijela niza i postavi __________________________________________________________ u sortiranom dijelu niza. ODGOVOR: prvi; na ispravno mjesto; 123. Bubble sort ima manju apriornu složenost od insertion sorta. TAČNO NETAČNO Strana 10 od 15 STRUKTURE PODATAKA PITANJA I ODGOVORI IPI AKADEMIJA TUZLA I ALGORITMI ODGOVOR: NETAČNO 124. Položaj elemenata niza je bitan za učinkovitost insertion sorta. TAČNO NETAČNO ODGOVOR: TAČNO 125. Za koji algoritam sortiranja se koristi pojam k – sortiranog niza (k je korak)? a) insertion, b) quick, c) merge, d) shell. ODGOVOR: d) shell 126. Insertion sort je bolji od bubble sorta na nizu do 100.000 elemenata. TAČNO NETAČNO ODGOVOR: TAČNO 127. Od sortova složenosti O(n^2) na nizu do 100.000 elemenata najbolji od ponuđenih je: a) selecton, b) shell, c) insertion, d) bubble. ODGOVOR: b) shell 128. Merge i quick sort koriste princip __________________________________________________. ODGOVOR: podijeli pa vladaj 129. Složenost merge sorta je O(nlog2n). TAČNO NETAČNO ODGOVOR: TAČNO 130. Najbolji slučaj merge sorta je već sortiran niz. TAČNO NETAČNO ODGOVOR: NETAČNO 131. Koji je do sada najbrži poznati algoritam sortiranja? ___________________________________. ODGOVOR: quick sort 132. Izbor pivota kod quick sorta nije jednoznačan. TAČNO NETAČNO ODGOVOR: TAČNO 133. Merge sort je zbog složenosti O(nlogn) brži za izvođenje od quick sorta. TAČNO NETAČNO ODGOVOR: NETAČNO 134. Šta je indirektno sortiranje? ______________________________________________________ ________________________________________________________________________________________ _______________________________________________________________________. ODGOVOR: Izdvajanje tabele sa pokazivačima na ključeve koji su sortirani, umjesto zamjene mjesta velikih struktura podataka u bazi. 135. Šta je stog? ___________________________________________________________________ _____________________________________________________________________________. ODGOVOR: Struktura podataka kod koje se posljednji pohranjeni podatak prvi obrađuje 136. Stog koristi FIFO princip. TAČNO NETAČNO ODGOVOR: NETAČNO 137. Kako se rješava problem punog stoga? _____________________________________________ _____________________________________________________________________________. ODGOVOR: dinamičkom alokacijom novog bloka memorije 138. Linearna lista realizirana kao dinamička struktura podataka sadrži: a) pokazivač na prvi član liste i proizvoljan broj atoma, b) pokazivač na prvi član liste i broja koji označava veličinu liste, c) pokazivač na prvi član liste, proizvoljan broj atoma i veličinu liste, d) proizvoljan broj atoma. ODGOVOR: a) pokazivač na prvi član liste i proizvoljan broj atoma Strana 11 od 15 STRUKTURE PODATAKA PITANJA I ODGOVORI IPI AKADEMIJA TUZLA I ALGORITMI 139. Svaki atom linearne liste sadrži polja sa ____________________________________________ i ____________________________________________________________________________. ODGOVOR: vrijednosti člana liste; pokazivača na sljedeći član; 140. Dinamička linearna lista znači da: a) se stalno povećava broj članova liste, b) se lista može širiti neograničeno bez obzira na dostupnu količinu memorije, c) se lista zauzima i oslobađa memoriju po potrebi d) ima fiksnu veličinu memorijskog prostora za svoje članove. ODGOVOR: c) se lista zauzima memoriju po potrebi 141. Realizacija stoga pomoću reda zauzima više memorije nego realizacija pomoću liste. TAČNO NETAČNO ODGOVOR: NETAČNO 142. Kod realizacije stoga listom ograničenje broja članova je jedino u ________________________ _____________________________________________________________________________. ODGOVOR: kapacitetu memorije računara 143. Red funkcionira po _______________________________________________________ principu. ODGOVOR: FIFO (first in first out) 144. Struktura red obavezno sadrži a) dvostruki pokazivač na kraj reda, b) pokazivač na početak reda, c) pokazivače na početak i kraj reda, d) jednostruki pokazivač na vrh reda. ODGOVOR: c) pokazivače na početak i kraj reda 145. Pri realizaciji reda cirkularnim nizom mora se ostaviti jedno prazno mjesto u redu. TAČNO NETAČNO ODGOVOR: TAČNO 146. Dodavanjem članova u red mijenja se vrijednost _________________________, a brisanjem članova iz reda mijenja se vrijednost _________________________. ODGOVOR: ulaza; izlaza; 147. Navedi glavni problem u realizaciji reda nizom. ________________________________________ _____________________________________________________________________________. ODGOVOR: ograničen kapacitet tj. mogućnost popunjenja niza 148. Red realizovan listom sadrži: a) pokazivače na ulaz i izlaz, b) pokazivače na ulaz, izlaz i pokazivač na kraj liste, c) pokazivač na vrh i kraj liste, d) pokazivač na vrh liste. ODGOVOR: b) pokazivače na ulaz, izlaz i pokazivač na kraj liste 149. Red realizovan listom mora sadržavati dvostruke pokazivače. TAČNO NETAČNO ODGOVOR: TAČNO 150. Kako se realizuje cirkularnost reda? _____________________________________________________________________________. ODGOVOR: korištenjem operatora modulo (%) 151. Jednostruko povezana lista sadrži u svakom članu liste jednostruki pokazivač na ____________________________________________________________________________. ODGOVOR: sljedeći član liste 152. Novi element u listu se može dodati _______________________________________________. ODGOVOR: na bilo koje mjesto Strana 12 od 15 STRUKTURE PODATAKA PITANJA I ODGOVORI IPI AKADEMIJA TUZLA I ALGORITMI 153. Operacije koje podržava jednostruko povezana lista su: a) brisanje, dodavanje i pretraživanje (čitanje), b) dodavanje i čitanje, c) brisanje i dodavanje, d) brisanje, dodavanje. ODGOVOR: a) brisanje, dodavanje i pretraživanje (čitanje) 154. Brisanjem elementa liste ostavlja se mjesto u memoriji koje je zauzimao za kasnije. TAČNO NETAČNO ODGOVOR: NETAČNO 155. Šta je potrebno uraditi dodavanjem novog elementa u jednostruko povezanu listu? ________________________________________________________________________________________ _______________________________________________________________________. ODGOVOR: preusmjeriti pokazivač prethodnog na novi, a novog na sljedeći element. 156. Atom liste mora imati onoliko pokazivača na sljedeći član koliko ima i ključeva. TAČNO NETAČNO ODGOVOR: TAČNO 157. Dvostruko povezana lista sadrži: a) dvostruki pokazivač na sljedeći član, b) dvostruki pokazivač na prethodni član, c) dvije glave (pokazivače na početak i kraj liste), d) pokazivače na sljedeći i prethodni član u svakom atomu, te glavu i rep. ODGOVOR: d) pokazivače na sljedeći i prethodni član u svakom atomu, te glavu i rep 158. Koja je prednost dvostruko povezane liste u odnosu na jednostruku? ________________________________________________________________________________________ ________________________________________________________________________. ODGOVOR: Pretraga liste se može vršiti u 2 smjera, od početka prema kraju i obrnuto. 159. Stablo se sastoji od čvora korijena i od ostalih čvorova podijeljenih u podstabla. TAČNO NETAČNO ODGOVOR: TAČNO 160. Stepen čvora u stablu je: a) broj čvorova iznad tog čvora, b) broj čvorova iznad tog čvora, c) broj podstabala tog čvora, d) nivo u kojem se nalazi u stablu. ODGOVOR: c) broj podstabala tog čvora 161. Korijeni podstabla čvora x su ____________________, a čvor x im je ______________________. ODGOVOR: djeca; roditelj; 162. Šta je stepen stabla? ______________________________________________________________________________. ODGOVOR: najveći stepen svih čvorova stabla 163. Dubina stabla je najmanja razina svih čvorova stabla. TAČNO NETAČNO ODGOVOR: NETAČNO 164. Binarno stablo ima: a) dva čvora, b) dvije razine, c) čvorove 2. stepena, d) dubinu 2. ODGOVOR: c) čvorove 2. stepena 165. Šta je puno binarno stablo? ______________________________________________________________________________. ODGOVOR: to je stablo dubine k sa 2k – 1 čvorova Strana 13 od 15 STRUKTURE PODATAKA PITANJA I ODGOVORI IPI AKADEMIJA TUZLA I ALGORITMI 166. Realizacija binarnog stabla statičkim nizom je najefikasnija od svih realizacija. TAČNO NETAČNO ODGOVOR: NETAČNO 167. Kod prikaza binarnog stabla statičkim nizom nisu potrebni podaci o vezama elemenata. TAČNO NETAČNO ODGOVOR: TAČNO 168. Koji je najgori oblik binarnog stabla prikazanog statičkim nizom? _________________________. ODGOVOR: koso stablo 169. Struktura koja se koristi za binarno stablo sadrži polja: a) vrijednost, lijevo dijete, desno dijete, b) vrijednost, lijevo dijete, c) vrijednost, desno dijete, roditelj, d) vrijednost, lijevo i desno dijete, roditelj. ODGOVOR: d) vrijednost, lijevo i desno dijete, roditelj 170. Sortirano binarno stablo ima osobine: a) ključevi u lijevom podstablu su manji, a u desnom veći od njihovog korijena, b) svi ključevi na trenutnoj razini su manji od ključeva na višoj razini, c) sadrži parove sortiranih vrijednosti raspoređenih na različitim razinama, d) ključevi u lijevom podstablu su veći, a u desnom manji od njihovog korijena. ODGOVOR: a) ključevi u lijevom podstablu su manji, a u desnom veći od njihovog korijena 171. Tri standardna načina obilaska binarnog stabla su: ________________________________, ___________________________________ i ____________________________________. ODGOVOR: inorder; preorder; postorder; 172. Koje 2 osnovne operacije treba podržati prioritetni red? ________________________________ ____________________________________________________________________________. ODGOVOR: dodavanje novog i brisanje najvećeg elementa. 173. Najprirodniji i najučinkovitiji način predstavljanja prioritetnog reda je kao: a) statičkog niza elemenata, b) sortirane vezane liste, c) gomile, d) sortiranog binarnog stabla. ODGOVOR: c) gomile 174. Gomila je _________________________________________________________, gdje se čvorovi mogu porediti _________________________________________________________________. ODGOVOR: potpuno binarno stablo; nekom relacijom (npr. =) 175. Šta je potrebno uraditi nakon promjene prioriteta nekog čvora gomile? ________________________________________________________________________________________ ________________________________________________________________________. ODGOVOR: proći kroz gomilu u određenom smjeru i obnoviti gomilu 176. Dodavanje novog elementa u gomilu vrši se a) u korijenu gomile, b) na dnu gomile, c) u prvom redu nakon korijena gomile, d) na sredini gomile. ODGOVOR: b) na dnu gomile 177. Koje je vrijeme izvođenja (najgori slučaj) za dodavanje novog elementa u gomilu? _________ ODGOVOR: O(nlog2n) 178. Složenost heap sort algoritma je bolja od O(nlog2n). TAČNO NETAČNO ODGOVOR: NETAČNO 179. Eulerov graf je __________________________________________________________________. Strana 14 od 15 STRUKTURE PODATAKA PITANJA I ODGOVORI IPI AKADEMIJA TUZLA I ALGORITMI ODGOVOR: skup vrhova V i ivica E. 180. Jedinstvena zatvorena putanja u Eulerovom grafu postoji ako i samo ako je a) stepen svakog vrha paran, b) stepen svakog vrha neparan, c) stepen svake ivice paran, d) stepen svake ivice neparan. ODGOVOR: a) stepen svakog vrha paran 181. Kod _______________________________ grafova parovi vrhova (u,v) i (v,u) predstavljaju _______________________________________. ODGOVOR: neusmjerenih; istu ivicu 182. Graf ne smije imati ivicu sa vrha v koja vodi na isti vrh v tj. ivice oblika (v,v) ili. TAČNO NETAČNO ODGOVOR: TAČNO 183. Graf sa više instanci iste ivice se zove ________________________ ili ___________________. ODGOVOR: višestruki; multigraf 184. Šta je potpuni usmjereni graf? ____________________________________________________ ODGOVOR: To je graf sa n vrhova i n(n-1) ivica. 185. Potpuni neusmjereni graf sa n vrhova ima a) n(n-1) ivica, b) n2 ivica, c) n/2 ivica, d) n(n-1)/2 ivica. ODGOVOR: d) n(n-1)/2 ivica 186. Ako je (u,v) ivica u skupu ivica E(G) u grafu G, tada su vrhovi susjedni. TAČNO NETAČNO ODGOVOR: TAČNO 187. Šta je dužina putanje u grafu? ____________________________________________________. ODGOVOR: To je broj ivica na putanji. 188. Petlja u grafu je jednostavna putanja sa ____________________________________________ ____________________________________________________________________________. ODGOVOR: istim početnim i krajnjim vrhom 189. Stepen vrha kod grafa je ________________________________________________________. ODGOVOR: broj susjednih ivica vrha 190. Koja su 3 najčešće korištena prikaza grafova? ________________________________________ _____________________________________________________________________________. ODGOVOR: matrice, liste i višestruke liste susjedstva. Strana 15 od 15