VPRAŠANJA 2006/7

Vsak na izpitu s klikom na spodnji gumb dobi šest vprašanja. Če sta dve vprašanji (ali celo tri ali štiri) slučajno enaki, se klika toliko časa, da ni izbranih 6 različnih vprašanj. Med temi vprašanji kandidat lahko enega takoj izloči, enega pa bo potem izločil še predavatelj.

Vp 1:   Vp 2:   Vp 3:   Vp 4:   Vp 5:   Vp 6:  

Nato ima do 15 minut časa za samostojno pripravo na odgovor.  Med pripravo lahko uporablja poljubno literaturo, računalnik, pomoč drugih oseb  in je lahko kjerkoli. Nato dobi zastavljeni dve vprašanji (izbere ju predavtelj) od teh štirih. Pri odgovarjanju ne sme uporabljati nobenih zapiskov, literature, ... Namen priprave je le v tem, da na hitro osvežite znanje in zagotovo ni čas, ko se učite določene stvari. Med pripravo si napravite pregledno osnovno zgodbo, ki poda pregled teme. Najboljše ocene bodo dobili tisti, ki bodo pregledno in samostojno povedali vse, kar se o temi da povedati, brez podvprašanj.

Vprašanja so le osnova  in ne pomenijo, da ne boste vprašani ničesar drugega. Gre za to, da se lažje začnemo pogovarjati!. Pri odgovarjanju nikakor ni potrebno pisati pravilne in popolne kode - implementacije algoritmov. Poudarek je na razumevanju algoritmov. Te lahko pišete v psevdokodi ali pa v "približni" Javi (ali v Perlu, Pythonu, C#, FORTRANu, pascalu, ...).

Največjo napako lahko naredite, če se učite odgovore na ta vprašanja. Vprašanj je namenoma zelo veliko, da bi takoj videli, da tak način priprave ni ravno smiselen. Ideja je v tem, da se naučite snov, ponavljate pa tako, da si "simulirate" izpit. In še enkrat - zagotovo je poudarek na razumevanju in ne na kakšnih podrobnostih. Seveda pa je to razumevanje potrebno pokazati. 

  1. Ugotovi in primerjaj časovno in prostorsko zahtevnost dveh algoritmov za izračun potence števila: z zaporednim množenjem in z razpolavljanjem.
  2. Kako si lahko z merjenjem pomagamo pri določanju časovne zahtevnosti
  3. Zapiši algoritem za metodo, ki sprejme kot parameter seznam nizov in vrne črko, ki se v teh nizih največkrat pojavi.
    a. Kaj v tem primeru predstavlja velikost problema?
    b. Zapiši algoritem v Javi.
    c. Oceni njegovo prostorsko in časovno zahtevnost.
    d. Denimo, da na voljo nima več dodatnega spomina kot za pet spremenljivk tipa int. Ali znaš popraviti algoritem tako, da bo to upošteval? Kakšni sta časovna in prostorska zahtevnost novega algoritma?
  4. Razloži vsaj dva algoritma za izračun maksimalne vsote podzaporedja v zaporedju celih števil.
  5. Razloži, kako bi poiskal VSA podzaporedja z maksimalno vsoto.
  6. Tipični razredi časovnih zahtevnosti. Za vsakega poišči konkreten primer algoritma in pokaži, da je časovna zahtevost res takega reda.
  7. Napiši dva algoritma , ki izračunata n-to potenco števila b. Prvi algoritem naj bo časovne zahtevnosti O(n), drugi pa časovne zahtevnosti O(log(n)).
  8. Imamo program, katerega čas izvajanja je  O(n2), vemo pa, da ima tudi nezanemarljiv del, ki potrebuje za izvajanje konstanten čas. Ko smo program pognali pri n = 10, je tekel 97 sekund, ko smo ga pognali pri n = 20, je tekel 100 sekund. Kako dolgo bi program delal za n = 1000?
    Za problem iz prejnjega dela smo uspeli najti postopek, ki je O(n). Del programa, ki se izvaja konstanten čas, je enak. Program smo pognali pri n = 1000 in je delo opravil v 1096 sekundah. Oba postopka želimo sestaviti tako, da bomo za določene n uporabljali prejšnji (kvadratni) postopek, za druge pa novega (verižnega). Kako?
  9. Primerjaj časovni zahtevnosti algoritma za iskanje v neurejenem zaporedju in z bisekcijo v urejenem zaporedju. Pokaži najboljši in najslabši primer.
  10. Razloži, kaj je to O notacija in kaj merimo z njo.
  11. Dana sta dva algoritma. Prvi je časovne zahtevnosti O(n), drugi pa O(n2). Kaj lahko poveš o času izvajanja algoritmov na istem računalniku in na istih problemih.
  12. Sestavi javno statično metodo, ki za dano tabelo celih števil vrne podzaporedje z maksimalno vsoto. Pri tem uporabi algoritem časovne zahtevnosti O(n3) in prostorske zahtevnosti O(n2). Algoritem je sledeč: Najprej generiraj vsote vseh možnih podzaporedij in jih shrani v tabelo. V dodatno tabelo shrani začetke in konce podzaporedij Nato v tabeli poišči maksimalni element in iz istoležnih indeksov rekonstruiraj ustrezno podzaporedje. Primerjaj algoritem z algoritmi, obravnavanimi na predavanjih.
  13. Jure je tabeliral zvezno funkcijo na intervalu od 0 do 1000 s korakom 1 in njene vrednosti shranil v tabelo dolžine 1000. Če veš, da ima funkcija na tem intervalu natanko eno ničlo in sta predznaka funkcije v krajiščih intervala različna, z uporabo bisekcije poišči interval, na katerem funkcija doseže ničlo!
  14. Kako si lahko z merjenjem časa pomagamo pri določanju časovne zahtevnosti algoritmov?
  15. Kaj pomeni časovna in kaj prostorska zahtevnost algortma? Kaj nam ta informacija sploh pove?
  16. Dan imaš algoritem kvadratne časovne zahtevnosti. Ali lahko iz podatka, da za obdelavo 100 podatkov algoritem porabi 10s sklepamo, koliko časa bo obdeloval 1000 podatkov? Odgovor obrazloži!
  17. Naštej tipične razrede časovnih zahtevnosti! Za vsakega poišči konkreten primer algoritma in pokaži, da je časovna zahtevost res takšnega reda.
  18. Kaj pomeni časovna in kaj prostorska zahtevnost algortma? Kaj nam ta informacija sploh pove?
  19. Sestavi javno statično metodo, ki za dano tabelo celih števil vrne maksimalno vsoto podzaporedja. Pri tem uporabi algoritem časovne zahtevnosti O(n). Razloži, kako bi poiskal VSA podzaporedja z maksimalno vsoto.
  20. Primerjaj časovni zahtevnosti algoritma za iskanje v neurejenem zaporedju in z bisekcijo v urejenem zaporedju. Pokaži najboljši in najslabši primer!
  21. Naštej nekaj podatkovnih struktur in na kratko opiši njihove osnovne značilnosti.
  22. Formalno opiši podatkovno strukturo sklad.
  23. Imamo dva sklada, v katerih so elementi urejeni naraščajoče (prvi element v skladu je najmanjši). Sestavi algoritem, ki s pomočjo osnovnih operacij nad skladom sestavi nov sklad, kjer so elementi (iz prvih dveh skladov) urejeni prav tako naraščajoče.
  24. Opiši, kako bi sklad predstavil v Javi.
  25. Predstavitev sklada s pomočjo tabele.
  26. Predstavitev sklada z verižnim seznamom.
  27. S pomočjo osnovnih operacij nad skladom iz danega sklada odstrani n-ti element.
  28. S pomočjo osnovnih operacij nad skladom iz danega sklada odstrani najmanjši element. Če jih je več, odstrani tistega, ki je v skladu najdlje.
  29. Problem postajenačelnika.
  30. Dane so dimenzije celoštevilskih matrik A, B, C, ... in pravilen izraz (denimo) (((((DE)F)A)B)C), ki določa vrstni red množenj teh matrik. Sestavi algoritem, ki izračuna število množenj.
  31. Zlivanje s pomočjo sklada.
  32. S pomočjo osnovnih operacij nad skladom iz danega sklada števil odstrani vsa soda števila.
  33. Dana sta dva nepadajoče urejena sklada. Sestavi metodo, ki vrne nepadajoče urejen sklad iz elementov, ki so v obeh skladih.
  34. Sestavite metodo public static String najdaljsiNiz(SkladNiz s), ki iz sklada nizov poišče in vrne najdaljši niz. Če je takih nizov več, naj vrne prvega. Prvotnega sklada več ne potrebujemo
  35. Sestavite metodo public static SkladDouble obrniSklad(SkladDouble s), ki sprejme sklad "realnih" števil in vrne obrnjen sklad. Prvotni sklad se pri tem ne spremeni.
  36. Sestavite metodo public static void vstavi(SkladInt s, int[] tabela), ki bo v sklad s vstavila po vrsti vse elemente iz tabele tabela, začenši z elementom na indeksu 0.
  37. S pomočjo osnovnih operacij nad skladom iz danega sklada odstrani najmanjši element. Če jih je več, odstrani tistega, ki je v skladu najdlje.
  38. Sestavi metodo public static void obrniElemente(Sklad s), ki obrne vrstni red elementov v skladu. Pri tem zahtevamo, da funkcija ne vrne novega sklada, ampak obrne prvotnega.
  39. Iz danega sklada odstrani prvi in zadnji element. Če je torej sklad [d, a, r, j, a] (najbolj desni je vrhnji element), potem mora biti sklad po izvedbi metode [a, r, j].
  40. Podan imamo sklad celih števil s. Sestavite metodo public static void odstraniLiha(Sklad s), ki s pomočjo osnovnih operacij nad skladom iz njega odstrani liha števila. Imamo podan sklad [18, 9, 5, -6, 50, 17] in po izvedeni metodi dobimo sklad [18, -6, 50].
  41. Sestavi metodo public static void odstraniNajvecje(Sklad s), ki s pomočjo osnovnih operacij nad skladom iz njega odstrani vse največje elemente.
  42. Imamo neprazen sklad celih števil. Napiši algoritem, ki s pomočjo osnovnih operacij nad skladom sestavi nov sklad, kjer so števila iz danega sklada urejena po velikosti (na vrhu je najmanjše število).
  43. Zapiši metodo, ki v danem skladu prešteje vsa soda števila.
  44. Zapiši metodo, ki iz danega sklada odstrani vse lihe elemente. Metoda naj vrne novi sklad s sodimi elementi.
  45. Iz danega sklada [5, 1, 6, 3, 2, 8] odstani število 3. Po izvedbi metode nad skladom moramo dobiti naslednji sklad [5, 1, 6, 2, 8].
  46. Napiši metodo, ki nam v danem skladu celih števil odstrani vsa števila, ki niso deljiva s 5.
  47. V skladu imamo ocene pisnega testa. Ravnatelj od nas zahteva, da mu povemo koliko ocen je negativnih. Teste smo vrnili dijakom, redovalnica je v razredu... ker smo na dobri poti, da postanemo "programerji", bomo sestavili navodila za program, ki bo iz sklada odstranil pozitivne ocene in preštel negativne.
  48. Sestavi metodo public static int samoPozitivna (Sklad s), ki s pomočjo osnovnih operacij nad skladom iz njega odstrani negativna števila.
  49. Dan je sklad. Želimo prešteti vse večkratnike števila 5, ki so v skladu. Prvotnega sklada pri tem ne smeš spremeniti.
  50. Dan je nepadajoče urejen sklad. S pomočjo osnovnih operacij izbriši vse podvojene elemente.
  51. Napiši metodo prelozi, ki iz vrste preloži elemente v sklad. Po prelaganju mora biti vrstni red pobiranja elementov iz sklada enak, kot če bi jih jemali iz prvotne vrste.
  52. Sestavi metodo static String oznaciGnezdenePare(String niz, char zacetni, char koncni), ki vrne niz tako, da v pravilno gnezdenem izrazu v nizu niz oznake znaka zacetni in koncni nadomesti z ustreznimi števili, ki označujejo kateri zaklepaj in oklepaj se ujemata. Tako klic metode oznaciGnezdenePare((a)(x)((xx)), (, )) vrne niz '1'a'1''2'x'2''3''4'xx'4''3'.
  53. Metka je vodja izmene v robotsko vodenem skladišču. Njeno delo je, da nadzira programerje, ki upravljajo robote-viličarje, ki skladajo zaboje v skladovnice. Janko jo je dolgo prosil, naj mu preskrbi delo programerja v tem skladišču. Končno je Metka le popustila in mu pri direktorju izposlovala zaposlitev. A že takoj prvi dan ga je Janko polomil. Robota je narobe sprogramiral. Tako so zabojniki v skladovnicah, ki jih nadzira Janko, zloženi (levo je naveden ZGORNJI zaboj skladovnice, v TEJ skladovnici so 4 zaboji) 1, 2, 3, 4; namesto 2, 1, 4, 3; ali pa (za 7 zabojev) 1, 2, 3, 4, 5, 6, 7 namesto 2, 1, 4, 3, 6, 5, 7 (po dva in dva zaboja sta torej v napačnem vrstnem redu). Metka mora hitro ukrepati in napisati ustrezen program, ki bo vodil robota, da preložil zaboje v vseh skladovnicah. Robot zna izvajati osnovne operacije nad skladom. Pomagaj Metki in napiši ALGORITEM za vodenje robota, ki v danem skladu preloži elemente tako, da zamenja po dva in dva elementa.
  54. Državni uradnik ima na mizi goro papirjev. Za vsakega ve, koliko časa mu bo vzela obdelava (denimo, da je to število, ki predstavlja čas obdelave v sekundah). Ker je uradnik len in urad plača uradnike po številu obdelanih papirjev, bi rad najprej obdelal tiste papirje, katerih obdelava mu ne bo vzela veliko časa (in druge po možnosti poslal naslednjemu uradniku). Zato želi narediti dva kupa: v enem naj bodo papirji, katerih čas obdelave je večji od povprečnega, v drugem pa vsi preostali. Ker je vrstni red papirjev važen, morajo biti papirji znotraj kupa urejeni po istem vrstem redu kot v začetnem kupu. Pomagaj mu pri tem mukotrpnem sortiranju! Ime funkcije naj bo public static void sortirajPapirje(Sklad s1, Sklad s2). Sklad s1 je vhodni sklad in vanj se shranijo papirji z nižjim časom obdelave od povprečnega, v s2 pa papirji z večjim časom obdelave. Pazi na to, da so vsi podatki v skladu tipa niz in jih je za primerjanje potrebno pretvoriti v število!
  55. Sestavi metodo public static void obrniElemente(Sklad s), ki obrne vrstni red elementov v skladu. Pri tem zahtevamo, da funkcija ne vrne novega sklada, ampak prvotnega z obrnjenimi elementi.
  56. Preveri, če so v danem izrazu oklepaji postavljeni pravilno. V izrazu lahko nastopajo ( in [ oklepaji. Vsak predklepaj mora imeti zaklepaj, prav tako pa morajo biti oklepaji pravilno gnezdeni. Izraz je dan kot niz, na voljo pa je sklad, v katerem lahko hranimo znake. Tako v [a(b(]b]bb fbf] oklepaji niso, v [a(b()b)b[b f]bf] pa so postavljeni pravilno.
  57. Iz danega sklada naredi dva sklada. V prvem naj bodo liha, v drugem pa soda števila iz prvega sklada.
  58. Sestavi algoritem, ki zlije dve urejeni zaporedji predstavljeni v verižnem seznamu. Pri tem ne prestavljaj elementov.
  59. Formalno predstavi strukturo verižni seznam in s pomočjo osnovnih operacij nad verižnim seznamom sestavi algoritem, ki zamenja elemente na sodih z elementi na lihih mestih (torej se element na mestu 2n zamenja z elementom na mestu 2n-1).
  60. Sestavi algoritem, ki vstavi nov element na začetek dvojno povezanega seznama, podanega s kazalcema na začetek in konec.
  61. Sestavi algoritem, ki na ustrezno mesto vstavi nov element v urejeni verižni seznam.
  62. Napiši objektno metodo public void urejenoVstavi(int elt); ki v nepadajoče urejen seznam vstavi nov element na pravo mesto, tako da ostane seznam še vedno urejen.
  63. Napiši objektno metodo public void obrniNaMestu(); ki seznam obrne tako, da ohrani vse vozle nespremenjene, le seznam je urejen v nasprotno smer: tisti element, ki je bil prej zadnji, je zdaj prvi, tisti, ki je bil prej prvi, je zdaj zadnji.
  64. Napiši objektno metodo dolzina(), ki vrne število elementov v verižnem seznamu.
  65. Napiši objektno metodo public void dodajNaKonec(int nn), ki na konec verižnega seznama doda nov element nn.
  66. Napiši objektno metodo public void vstavi(int nov, int nn), ki na nn-to mesto v verižnem seznamu vstavi nov vozel s podatkom nov. nn-to mesto je definirano tako, da metoda vrniNti potem vrne novo vstavljeni element.
  67. Napiši objektno metodo public void dodaj(VerSez ss), ki verižnemu seznamu doda verižni seznam ss. Metoda dodaj prilepi elemente seznama ss na konec našega seznama.
  68. Napiši objektno metodo public VerSez obrni(); ki vrne nov verižnega seznam z obrnjenimi elementi prvotnega seznama: tisti element, ki je bil prej zadnji, je zdaj prvi, tisti, ki je bil prej prvi, je zdaj zadnji. Prvotni seznam se pri tem ne sme spremeniti!
  69. Sestavi algoritem, ki iz verižnega seznama, v katerem hranimo cela števila, naredi dva seznama. V prvem so liha števila in v drugem soda števila. Pri tem ne smeš narediti prelagati elementov!
  70. Sestavi algoritem, ki izračuna povprečno dolžino besed, ki jih hranimo v enojno povezanem verižnem seznamu.
  71. Sestavi algoritem, ki vrne kazalec na element verižnega seznama v katerem je najdaljša beseda.
  72. Sestavi algoritem, ki določi, katera sta zadnja preostala elementa krožnega seznama, če izločamo vsak tretji element.
  73. Odstrani podatek iz enojno povezanega verižnega seznama.
  74. Predstavitev enojno povezanega verižnega seznama v Javi.
  75. Formalno opiši podatkovno strukturo vrsta.
  76. S pomočjo osnovnih operacij nad vrsto in skladom obrni vrstni red elementov v skladu.
  77. S pomočjo osnovnih operacij nad vrsto iz vrste odstrani n-ti element.
  78. Razloži, kako bi lahko vrsto predstavil s pomočjo tabele in opiši osnovne algoritme.
  79. Sestavi algoritem, ki z osnovnimi operacijami nad vrsto pove, kateri je n-ti element vrste (če obstaja).
  80. Napiši objektno metodo public int vrniNajvecjiEltSeznama(), ki vrne največji element v verižnem seznamu. V primeru, da je seznam prazen, vrne najmanjšo vrednost (Integer.MIN_VALUE).
  81. Napiši statično metodo, ki iz danega verižnega seznama odstrani vsak drugi vozel. V seznamu naj ostanejo med seboj povezani samo vozli, ki so bili prej na lihih mestih (prvi, tretji, peti ...)
  82. V mestu živijo družine z različnim številom otrok. Števila otrok so shranjena v vozlih verižnega seznama. Preštej, koliko otrok živi v mestu.
  83. Računovodkinja se je pri pripravi plač, ki jih vodi v verižnem seznamu (možnost: skladu, vrsti), zmotila. Po nalogu ravnatelja bi morala vsakemu zaposlenemu pri plači dodati enak znesek delovne uspešnosti. Pomagaj ji in ji napiši metodo public static void pristejZnesek, ki bo pri naslednji plači vsakemu zaposlenemu prištela enak znesek.
  84. Bliža se konec šolskega leta in da bodo dijaki, starši, šefi in sploh in oh vsi veseli, sestavi računalniški virus, ki bo vse ocene, ki so nižje od 5, povečal za ena. Ocene vodimo v vrsti ali pa v skladu.
  85. V knjižnični katalog je potrebno vpisati novo knjigo. Vsaka nova knjiga je postavljena na konec urejenega verižnega seznama. Sestavi metodo, ki bo dodala novo inventarno številko na konec knižničnega kataloga.
  86. Napiši metodo, ki prešteje vse večkratnike števila 3 v verižnem seznamu.
  87. Napiši metodo, ki odstrani večkratnike poljubnega števila iz verižnega seznama. Prvo število v verižnem seznamu naj ne bo večkratnik tega števila.
  88. Zapiši metodo, ki bo iz danega verižnega seznama vS vrnila drugo največje število.
  89. Napiši metodo, ki sešteje vsa soda števila verižnega seznama.
  90. Napiši metodo, ki v verižnem seznamu prešteje vse večkratnike števila 3.
  91. Predstavitev vrste s pomočjo tabele.
  92. Predstavitev vrste s pomočjo krožne tabele.
  93. Predstavitev vrste z uporabo verižnega seznama.
  94. Sestavi statično metodo void izloci(Vrsta v, int x), ki iz vrste izloči vse podatke, ki so enaki x.
  95. Sestavite metodo public static String vrniNTi(Vrsta v, int n), ki vrne n-ti element v vrsti v.
  96. Sestavite statično metodo public static Vrsta zlij(Vrsta v1, Vrsta v2), ki zlije nepadajoče urejeni vrsti v1 in v2 v novo nepadajoče urejeno vrsto in jo vrne. Vrsti v1 in v2 se po klicu metode ne smeta spremeniti.
  97. Imamo dve vrsti, v katerih so elementi urejeni naraščajoče. Sestavi algoritem, ki s pomočjo osnovnih operacij nad vrsto sestavi novo vrsto, kjer so elementi (iz prvih dveh vrst) urejeni prav tako naraščajoče.
  98. Imamo dva sklada, v katerih so elementi urejeni naraščajoče (oziroma pravilneje - nepadajoče). Sestavi algoritem, ki s pomočjo osnovnih operacij nad vrsto in skladom sestavi novo vrsto, kjer so elementi (iz prvih dveh skladov) urejeni prav tako naraščajoče.
  99. Imamo dva sklada, v katerih so elementi urejeni naraščajoče (prvi element v skladu je najmanjši). Sestavi algoritem, ki s pomočjo osnovnih operacij nad skladom sestavi nov sklad, kjer so elementi (iz prvih dveh skladov) urejeni prav tako naraščajoče.
  100. Algoritem, ki izpiše podatke iz enojno povezanega verižnega seznama.
  101. Algoritem, ki odstrani vsak drugi element iz dvono povezanega verižnega seznama.
  102. Formalno opiši podatkovno strukturo dvojiško drevo.
  103. Pregledi dvojiškega drevesa. Opiši in na praktičnem primeru izvedi.
  104. Sestavi algoritem, s katerim iz premega in vmesnega vrstnega reda rekonstruiraš drevo.
  105. Sestavi algoritem, s katerim iz obratnega in vmesnega vrstnega reda rekonstruiraš drevo.
  106. Sestavi metodo DvDrevo normiraj(DvDrevo d), ki s pomočjo osnovnih operacij nad dvojiškim drevesom naredi kopijo danega dvojiškega drevesa s pozitivnimi podatki, katerega vrednosti v vozliščih so celoštevilski kvocienti med vrednostmi v vozliščih originalnega dvojiškega drevesa in največjim elementom v dvojiškem drevesu.
  107. Sestavi algoritem, ki iz sklada zgradi iskalno dvojiško drevo.
  108. Sestavi algoritem, s katerim ugotoviš višino dvojiškega drevesa. Uporabi le osnovne operacije nad drevesom.
  109. V dvojiškem drevesu hranimo cela števila. Sestavi algoritem, s katerim izračunaš povprečno vrednost elementov v drevesu.
  110. V dvojiškem drevesu hranimo cela števila. Naj bo vsota poti do lista enaka vsoti elementov, ki jih prehodimo od korena do lista. Sestavi algoritem, ki ugotovi, če v danem drevesu obstaja list, ki ima vsoto poti enako vrednosti v tem listu.
  111. Predstavitev dvojiškega drevesa s tabelo.
  112. Predstavitve dvojiških dreves v Javi.
  113. Z osnovnimi operacijami sestavi zrcalno kopijo dvojiškega drevesa.
  114. Dano je dvojiško iskalno drevo. Izpiši elemente urejeno od najmanjšega do največjega.
  115. Dano je dvojiško iskalno drevo. Izpiši elemente urejeno od največjega do najmanjšega.
  116. Sestavi algoritem, ki iz sklada zgradi iskalno dvojiško drevo.
  117. Napiši algoritem int prestej(DvDrevo d), ki prešteje število vozlišč v dvojiškem drevesu d.
  118. Napiši metodo, ki bo izračunala razliko med največjim in najmanjšim elementom v danem iskalnem dvojiškem drevesu.
  119. Napiši algoritem String najvecji(DvDrevo d), ki vrne najdaljši niz drevesa (v drevesu kot podatke hranimo nize).
  120. Sestavi algoritem, s katerim prešteješ število listov v dvojiškem drevesu. Algoritem naj uporablja le osnovne operacije nad dvojiškim drevesom.
  121. Sestavi metodo, ki podatke v drevesu preloži v sklad tako, da so podatki v skladu razvrščeni glede na obratni pregled dvojiškega drevesa.
  122. V dvojiškem drevesu hranimo cela števila. Naj bo vsota poti do lista enaka vsoti elementov, ki jih prehodimo od korena do lista. Sestavi algoritem, ki ugotovi, če v danem drevesu obstaja list, ki ima vsoto poti enako vrednosti v tem listu.
  123. Sestavi algoritem, ki s pomočjo osnovnih operacij nad dv. drevesom, dano dvojiško drevo prezrcali (t.j. zamenja vlogo levega in desnega poddrevesa vsakega vozlišča).
  124. Sestavi algoritem, ki s pomočjo osnovnih operacij nad dv. drevesom, ugotovi, če sta dve drevesi identični (imata enako strukturo in hranita enake vrednosti)
  125. Sestavi algoritem, ki v iskalnem dvojiškem drevesu poišče minimalni in maksimalni element.
  126. Sestavi algoritem, ki s pomočjo osnovnih operacij nad dv. drevesom, v dvojiškem drevesu poišče minimalni in maksimalni element.
  127. Iskalno drevo.
  128. Dano je dvojiško iskalno drevo. Poišči največji in najmanjši podatek.
  129. V prazno iskalno drevo zaporedoma vstavljamo 11 8 7 6 3 5 4 1 2 .Zapiši vse tri preglede tega drevesa.
  130. Če je zaporedje 55 22 11 44 33 88 x 66 100 99 premi pregled, zaporedje 11 22 33 44 55 66 x 88 99 100, pa vmesni pregled dvojiškega iskalnega drevesa, potem kaj velja za x?
  131. Podano imamo tabelo celih števil, ki predstavlja levo poravnano iskalno dvojiško drevo. V tabeli manjkata dva podatka. Kakšne vrednosti lahko zavzameta?
    • 8, 5, y, x, 13, 15
    • x, 5, 11, 1, 7, y, 15
    • x, 5, y, 1, 7, 13, 15
  132. Sestavi algoritem, ki uredi elemente v skladu s pomočjo iskalnega dvojiškega drevesa.
  133. Vstavljanje v iskalno drevo.
  134. Razloži, kaj je to kopica in sestavi algoritem, ki vstavi nov podatek v kopico.
  135. Sestavi kopico, če vse elemente poznaš vnaprej.
  136. Podatke o plačah v podjetju hranijo v podatkovni strukturi kopica. Nihče od podrejenih namreč ne more imeti višje plače od svojega nadrejenega. Zaradi dobrih uspehov se odločijo za povišanje plač. Ampak tokrat bodo za spremembo povišali plače samo vsem na dnu lestvice. Povišanje bo 10 %, vendar samo če se s tem ne poruši osnovnega razmerja, da plača podrejenega ne more biti višja od plače nadrejenega. Drugače bo povišanje pri posameznikih po potrebi manjše. V ta namen napiši metodo v javi public static void povisajPlace(int[] kopica, int procenti) in jo preizkusi v glavnem programu.
  137. Napiši program v javi, ki uredi elemente v tabeli od najmanjšega do največjega z algoritmom, ki uporablja urejanje s kopico. Vzemimo, da program dobi vhodno tabelo a = { 75, 34, 62, 28, 18, 45, 61, 21, 25, 7} in nam jo s pomočjo urejanja s kopico naraščajoče uredi v a = { 7, 18, 21, 25, 28, 45, 61, 62, 75}.
  138. Imaš podane elemente 35, 6, 26, 22, 13, 74. Sestavi maksimalno kopico, če elementi prihajajo sproti.
  139. Odstrani podatek z vrha max kopice: 74, 21, 34, 5, 12, 3, 5.
  140. V javi sestavi algoritem, ki bo dano tabelo(ki predstavlja levo poravnano dvojiško drevo) preuredil tako, da bo postala MAX kopica. Predpostavi da: a.)prvi element tabele stoji na mestu z indeksom 1 b.)tabela ima liho število elementov (in ima vsaj tri elemente)
  141. Odstrani najmanjši podatek iz max kopice: 93, 45, 68, 43, 7, 56, 3, 32 tako, da bo dobljeno še vedno kopica.
  142. Imamo tabelo elementov: 3, 5, 15, 4, 6, 17, 3 .Sestavi kopico, če elementi prihajajo sproti.
  143. Podano imamo tabelo števil, ki predstavlja maksimalno kopico. Sestavi metodi, ki vrneta maksimalni oz. minimalni element v kopici. Sestavi kopico, če vse elemente poznaš vnaprej.
  144. Razloži razliko med sestavljanjem kopice z vstavljanjem elementov in s spajanjem manjših kopic. Kdaj uporabimo prvi in kdaj drugi algoritem?
  145. V algoritem za gradnjo kopic se nam je prikradla napaka. Poišči napačni element v spodnjih kopicah in povej, katere vrednosti lahko zavzame! Ali je ta element enolično določen?
    * 81,20,3,16,26
    * 90,79,54,22,35,27,43,8,23,13
    * 98,89,98,68,82,51,52,65,49,83,62,25,29,41,50,35,28,22,2,13
  146. Elementi so shranjeni v kopici. Sestavi algoritem s katerim jih preložiš v tabelo tako, da so v tabeli urejeni.
  147. Naj tabela

    40

    18

    15

    9

    x

    11

    15

    y

    1

    6

    3

    11

    5

    predstavlja max kopico celih števil (x in y seveda nista tiskarski napaki, ampak ustrezni celi števili). Katere (celoštevilske) vrednosti lahko zavzameta x in y?
  148. Sestavi algoritem, s katerim odstraniš vrhnji podatek iz kopice.
  149. Sestavi algoritem, ki poišče najbolj desni element v kopici, iskalnem drevesu in običajnem dv. drevesu. Ima element kakšne posebne značilnosti?
  150. Iz podatkov 3, 7, 934, 323, 436, 56, 68, 45, 563, 57, 56, 511, 9879, 234, 355, 53, 35, 34, 111, 22 sestavi dve kopici. Prva naj bo taka, da je oče večji in druga taka, da je oče manjši od sinov. Pri prvi kopici uporabi algoritem, ki predvideva, da podatke dobivaš sproti in pri drugi takega, kjer podatke poznamo vnaprej!
  151. Sestavi algoritem, s katerim odstraniš poljubni podatek iz kopice.
  152. Idejo podatkovne strukture dvojiška kopica lahko naravno razširimo na pojem trojiške kopice. Namesto dveh ima sedaj vsako vozlišče največ 3 sinove. Tudi tu je drevo levo poravnano. Denimo, da trojiško kopico predstavimo v tabeli (v razredu Trojiska_Kopica imamo komponento tabela z n elementi, kjer je n število elementov v kopici) (v tabeli element z indeksom 0 NE izpustimo!) . Opiši način predtsavitve trojiške kopice, relacije med očetom in sinovi, ...
  153. Sestavi algoritem, s katerim v kopici poiščeš najmanjši in največji element!
  154. Sestavi algoritem, s katerim poiščeš element v dvojiškem iskalnem drevesu.
  155. Dano je dvojiško iskalno drevo. Izpiši elemente urejeno.
  156. Sestavi algoritem, ki poišče najbolj desni element v kopici, iskalnem drevesu in običajnem dvojiškem drevesu. Ima element kakšne posebne značilnosti?
  157. Dana je tabela celih števil. Uredi jo tako, da so na začetku števila, katerih absolutna vrednost pri deljenju s 3 dajo ostanek 0, nato števila, ki dajo pri deljenju njihove aboslutne vrednosti s 3 ostanek 1 in nato še preostala števila. Analiziraj stabilnost tvojega algoritma – torej ali enaki podatki ohranijo isti relativni vrstni red v preurejeni tabeli.
  158. Sestavi algoritem, s katerim vstaviš nov element v dvojiško iskalno drevo.
  159. Opiši možne načine predstavitve grafa.
  160. Razloži pojme: poln graf, usmerjen graf, pot, cikel, stopnja vozlišča, stopnja grafa, izolirano vozlišče, povezan graf, sosednji točki, razdalja med točkami.
  161. Graf je predstavljen z matriko sosednosti. Sestavi algoritem, ki za vsako vozlišče ugotovi njegovo stopnjo.
  162. Razloži in s primerom pokaži, zakaj je dobro uporabljati stabilno metodo urejanja. Pokaži primer vsaj dveh nestabilnih in dveh stabilnih metod urejanja.
  163. Opiši hitro urejanje.
  164. S pomočjo algoritma za prerazporeditev elementov v tabeli bomo implementirali hitro urejanje. Napiši metodo public static void hitroUredi(int[] tabela), ki hitro uredi tabelo števil.
  165. Pokaži, kako postorep preurejanja iz HU preuredi  tabelo števil: 10, 3, 9, 26, 32, 12, 4, 9, 11, 15, 3, 1
  166. Tabelo števil hitro uredi 9, 3, 7, 10, 26, 42, 13, 2, 6, 1, 22, 30
  167. Tabelo števil uredi z zlivanjem 7, 26, 10, 5, 2, 30, 1, 40, 12, 3, 14, 4, 6
  168. V tabeli števil 13, 9, 6, 7, 15, 26, 1, 30, 42, 53, 2, 80, 5, 2, 30, 1, 40, 12 iščemo peti najmanjši element. Opiši postopek.
  169. V tabeli števil 13, 9, 6, 7, 15, 26, 1, 30, 42, 53, 2, 80, 5, 2, 30, 1, 40, 12 iščemo peti največji element. Opiši postopek.
  170. Opiši, kako bi z metodo Deli in Vladaj poiskal k-ti najmanjši element v tabeli števil 50, 60, 62, 76, 40, 45, 35, 1, 30, 42, 53, 2, 80, 5, 2, 1, 30, 42, 53, 2, 80, 5, 2.
  171. Opiši, kako bi z metodo Deli in Vladaj poiskal k-ti največji  element v tabeli števil 50, 60, 62, 76, 40, 45, 35, 1, 30, 42, 53, 2, 80, 5, 2, 1, 30, 42, 53, 2, 80, 5, 2.
  172. Tabela 332, 256, 110, 208, 286, 138, 180, 257 predstavlja število obiskovalcev na predstavi Romeo in Julia. Razvrsti podatke s pomočjo hitrega urejanja od najmanj do najbolj obiskane predstave. Prikaži postopek iskanja elementa v naraščajoče urejeni tabeli s strategijo deli in vladaj. Tabela: 5, 6, 8, 9, 10, 12, 15, 16, 17, 22, 24, 27, 28, 29, 30, 31, 33, 37, 41, 48, 49, 52, 53, 55, 60, 62, 72, 77, 78, 80. Iskalni element: 77 .
  173. Napiši metodo, ki bo s pomočjo algoritma Deli in vladaj poiskala največje realno število v dani tabeli.
  174. Napiši metodo, ki bo s pomočjo algoritma Deli in vladaj poiskala najmanjše realno število v dani tabeli.
  175. Primerjaj vstavljanje, izbiranje in urejanje z mehurčki.
  176. Razloži algoritem za urejanje z vstavljanjem.
  177. Dana je tabela neničelnih celih števil. Uredi jo tako, da bodo najprej soda negativna števila, nato soda pozitivna, nato liha negativna števila in še liha pozitivna števila. Analiziraj časovno zahtevnost svojega algoritma!
  178. Razloži algoritem za urejanje z izbiranjem.
  179. Razloži algoritem za urejanje z mehurčki.
  180. Tabelo števil uredi naraščajoče. Uporabi postopek urejanja z vstavljanjem. Prikaži posamezne korake urejanja. 9, 3, 7, 10, 26, 42, 13, 2, 6, 1, 22, 30
  181. Tabelo števil uredi naraščajoče. Uporabi postopek urejanja s stresanjem. Prikaži korake urejanja po rekurzivnih klicih. 10, 25, 13, 7, 17, 21, 5, 9
  182. Podana je tabela šestih naključno izbranih števk od 0 do 9. Izpiši največje in najmanjše število, ki ga dobiš iz podanih števk. Tabela [5, 2, 3, 7, 1, 2]
  183. Tabelo števil [10, 14, 45, 25, 3, 31, 4, 1, 49, 2, 26, 30] uredi naraščajoče. Podatki v tabeli niso urejeni. Uporabi algoritem za urejanje z izbiranjem.
  184. Z algoritmom za urejanje z izbiranjem uredi tabelo števil [9, 1, 7, 8, 3, 5, 4, 2, 6] tako, da bodo podatki razvrščeni naraščajoče.
  185. Tabelo števil 3, 10, 8, 2, 12, 1, 15 uredi naraščajoče. Uporabi postopek urejanja z mehurčki. Prikaži korake urejanja po rekurzivnih klicih.
  186. Uredi tabelo danih števil: 12, 5, 4, 7, 3, 9, 28, 16 Uporabi urejanje z vstavljanjem.
  187. Na praktičnem primeru pokaži, kako deluje hitro urejanje in urejanje z zlivanjem.
  188. Urejanje z zlivanjem.
  189. Osnova za algoritem hitrega urejanja je algoritem za preureditev tabele na dva dela - levo damo elemente manjše od izbranega, desno pa večje. Napiši metodo public static int razdeli(double[] tocke, int zacetek, int konec), ki to naredi na tabeli tocke z elementi med indeksoma zacetek ter konec in vrne ločnico med odsekoma preurejene tabele. To naredi učinkovito!
  190. Urejanje s kopico.
  191. Napiši algoritem za urejanje z vstavljanjem in analiziraj njegovo časovno zahtevnost.
  192. Napiši algoritem za urejanje z izbiranjem in analiziraj njegovo časovno zahtevnost.
  193. Napiši algoritem za urejanje z mehurčki in analiziraj njegovo časovno zahtevnost.
  194. Opiši metodo deli in vladaj.
  195. Opiši, kako bi z metodo deli in vladaj poiskal k-ti največji in k-ti najmanji element v tabeli števil.
  196. Opiši, kako bi z metodo deli in vladaj poiskal k-ti največji element v tabeli števil.
  197. Razloži osnovno idejo, kako bi z deli in vladaj poiskal konveksno ovojnico množice točk v ravnini.
  198. Verjetnost, da prestrežejo sporočilo agenta i agentu j je p[i,j]. Kako naj za sporočila izvedo vsi, tako da bo verjetnost, da sporočilo bo sporočilo prestreženo, minimalna.
  199. Šivilja bi rada sešila n oblek. Za vsako potrebuje en dan. Za njih dobi plačilo c_i, a le, če je obleka sešita do dneva d_i. V kakšnem vrstnem redu naj jih šiva, da bo zaslužila kar se da veliko?
  200. Mehanik mora popraviti n avtomobilov. Za i-tega potrebuje d_i dni. V kakšnem vrstnem redu naj jih popravlja, da bo skupna čakalna doba najkrajša? Dokaži pravilnost svoje strategije!
  201. Strassenovo množenje matrik.
  202. Razloži, kako z bisekcijo poiščeš element v urejeni tabeli števil. Analiziraj časovno zahtevnost metode.
  203. Naštej nekatere probleme, ki jih lahko rešiš s pomočjo metode deli in vladaj in opiši algoritem za enega od teh.
  204. Analiziraj časovno zahtevnost iskanja minimalnega elementa z direktnim iskanjem (zaporedno primerjanje) in z metodo deli in vladaj.
  205. S pomočjo metode deli in vladaj sestavi algoritem, ki poišče dve točki v ravnini, ki sta med sabo najmanj oddaljeni.
  206. Zelo veliko celo število (denimo 256 mestno) predstavimo v tabeli (enice na 0-tem mestu, desetice na 1-tem mestu, stotice na mestu v tabeli z indeksom 2...) S pomočjo metode deli in vladaj napiši učinkovit algoritem za množenje dveh takih tevil. Predpostavi, da sta dolžini obeh števil enaki in da sta dolžini potenci števila 2.
  207. Razporejanje programskih enot na trak - dokaz pravilnosti postopka.
  208. Požrešna metoda - opiši pojem dopustna rešitev in optimalna rešitev. Prikaži nekaj primerov.
  209. Definiraj dopustne in optimalne podmnožice pri požrešni metodi! Navedi nekaj primerov.
  210. Podano imamo množico T n opravil. Za vsako opravilo poznamo: začetek (s_i), ter konec (f_i) - seveda velja s_i < f_i. Na razpolago imamo stroje, izmed katerih vsak lahko naenkrat opravlja eno nalogo. Kako razporediti opravila, da bomo porabili kar čimmanj strojev?
  211. Problem enostavnega nahrbtnika.
  212. Dokaži pravilnost rešitve za problem enostavnega nahrbtnika.
  213. Dan je nahrbtnik velikost 30 in predmeti z vrednostmi 11, 23, 43, 5, 6, 77, 44, 2, 23, 4 in velikostmi 10, 10, 12, 5, 12, 5, 6, 20, 25, 1. Reši problem preprostega nahrbtnika.
  214. Ali strategija za rešitev 0/1 nahrbtnika nujno pripelje do rešitve tudi pri problemu preprostega nahrbtnika? Če ne, poišči protiprimer!
  215. Razporejanje programskih enot na trak.
  216. Kaj je minimalno vpeto drevo in uporaba slednjega.
  217. Na praktičnem primeru razloži, kako deluje Primov in  Kruskalov postopek.
  218. Meta ima šest prijateljic: Aljo, Jano, Tejo, Sašo, Kajo in Uro. Vse so navdušene uporabnice mobilnih telefonov. Ker mora vsako novico vsaka takoj sporočiti ostalim šestim, so njihovi telefonski računi zelo visoki. Ko so nekaj mesecev spremljale stroške povprečnega pogovora, so prišle do matrike stroškov posameznega klica. Zanima nas, kako naj se novica najceneje prenese med poljubnima dvema prijateljicama. Če se torej Meta pogovarja neposredno z Aljo, so stroki klica 50 SIT. A novica od Mete do Alje lahko pride tudi tako, da Meta pokliče Jano (kar stane 21 SIT), Jana pa potem prenese novico Alji (kar stane 16 SIT) - torej skupno 37 SIT (ceneje) ! Za poljubni dve prijateljici ugotovi, koliko ju stane, da si izmenjata novico.
  219. Meta ima šest prijateljic: Aljo, Jano, Tejo, Sao, Kajo in Uro. Vse so navdušene uporabnice mobilnih telefonov. Ker mora vsako novico vsaka takoj sporočiti ostalim šestim, so njihovi telefonski računi zelo visoki. Ko so nekaj mesecev spremljale stroške povprečnega pogovora, so prišle do matrike stroškov posameznega klica. Kako naj se kličejo med seboj, da se bo novica med njimi kar najhitreje raznesla?
  220. Razlike med Primovim in Kruskalovim postopkom, kdaj bi lahko uporabili ta postopek?
  221. Na praktičnem primeru demonstriraj način reševanja problema iskanja optimalnega zaporedja množenj matrik - tako določitve števila množenj kot načina množenja. Če je optimalnih načinov množenja več, moraš prikazati vse!
  222. Kako optimalno zmnožimo verigo matrik? Opiši algoritem!
  223. Razloži, zakaj uporaba rekurzije ni primerna za neposreden zapis Bellmanove enačbe pri množenju matrik.
  224. Problem 0/1 nahrbtnika.
  225. Pokaži in razloži zakaj požrešna metoda ni primerna za reševanje problema trgovskega potnika.
  226. Na praktičnem primeru pokaži, kako bi reševal problem 0/1 nahrbtnika.
  227. Dan je nahrbtnik velikost 30 in predmeti z vrednostmi 11, 23, 43, 5, 6, 77, 44, 2, 23, 4 in velikostmi 10, 10, 12, 5, 12, 5, 6, 20, 25, 1. Reši problem 0/1 nahrbtnika.
  228. Dan je nahrbtnik velikost 40 in predmeti z vrednostmi 11, 23, 43, 5, 6, 77, 44, 2, 23, 4 in velikostmi 10, 10, 12, 5, 12, 5, 6, 20, 25, 1. Reši problem 0/1 nahrbtnika.
  229. Zmnožiti je potrebno zaporedje matrik z velikostmi 2 x 3, 3 x 6, 6 x 8, 8 x 2, 2 x 10, 10 x 6 in 6 x 4. Kako moramo izvesti množenja, da bomo uporabili kar se da malo množenj realnih števil.
  230. Denimo, da pri problemu množenja matrik ne uporabljamo običajnega, ampak Strassenov postopek množenja matrik. Opiši, kako bi bil potem videti algoritem za optimalno množenje matrik.