DIRI 2005/6

 PODATKOVNE STRUKTURE IN ALGORITMI
   

VPRAŠANJA 2005/6

 Vsak na izpitu s klikom na spodnji gumb dobi štiri vprašanja. Če sta dve vprašanji (ali celo tri ali štiri) slučajno enaki, se klika toliko časa, da so zastavljena 4 različna vprašanja.

Vp 1:   Vp 2:   Vp 3:   Vp 4:    

Nato ima do 15 minut časa za samostojno pripravo na odgovor. Če v 15 minutah predavatelju ne pove, da je pripravljen odgovarjati, se šteje, da je od izpita odstopil. Med pripravo lahko uporablja poljubno literaturo in je lahko kjerkoli. Nato dobi zastavljeni dve vprašanji 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. 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, ...).

  1. Ugotovi in primerjaj časovno in prostorsko zahtevnost dveh algoritmov za izračun potence števila: z zaporednim množenjem in z razpolavljanjem.
  2. 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?
  3. Razloži vsaj dva algoritma za izračun maksimalne vsote podzaporedja v zaporedju celih števil.
  4. Razloži, kako bi poiskal VSA podzaporedja z maksimalno vsoto.
  5. Primerjaj časovni zahtevnosti algoritma za iskanje v neurejenem zaporedju in z bisekcijo v urejenem zaporedju. Pokaži najboljši in najslabši primer.
  6. 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.
  7. Kaj pomeni časovna in kaj prostorska zahtevnost algortma? Kaj nam ta informacija sploh pove?
  8. Naštej nekaj podatkovnih struktur in na kratko opiši njihove osnovne značilnosti.
  9. Formalno opiši podatkovno strukturo sklad.
  10. 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.
  11. Opiši, kako bi sklad predstavil v Javi.
  12. Predstavitev sklada s pomočjo tabele.
  13. Predstavitev sklada z linearnim seznamom.
  14. S pomočjo osnovnih operacij nad skladom iz danega sklada odstrani n-ti element.
  15. 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.
  16. Problem postajenačelnika.
  17. Zlivanje s pomočjo sklada.
  18. S pomočjo osnovnih operacij nad skladom iz danega sklada števil odstrani vsa soda števila.
  19. Dana sta dva nepadajoče urejena sklada. Sestavi metodo, ki vrne nepadajoče urejen sklad iz elementov, ki so v obeh skladih.
  20. Dan je nepadajoče urejen sklad. S pomočjo osnovnih operacij izbriši vse podvojene elemente.
  21. 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.
  22. Iz danega sklada naredi dva sklada. V prvem naj bodo liha v drugem pa soda števila iz prvega sklada.
  23. Sestavi algoritem, ki zlije dve urejeni zaporedji predstavljeni v linearnem seznamu. Pri tem ne prestavljaj elementov.
  24. Sestavi algoritem, ki vstavi nov element na začetek dvojno povezanega seznama, podanega s kazalcema na začetek in konec.
  25. Sestavi algoritem, ki na ustrezno mesto vstavi nov element v urejeni linearni seznam.
  26. Sestavi algoritem, ki iz linearnega 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!
  27. Sestavi algoritem, ki izračuna povprečno dolžino besed, ki jih hranimo v enojno povezanem linearnem seznamu.
  28. Sestavi algoritem, ki vrne kazalec na element linearnega seznama v katerem je najdaljša beseda.
  29. Sestavi algoritem, ki določi, katera sta zadnja preostala elementa krožnega seznama, če izločamo vsak tretji element.
  30. Odstrani podatek iz enojno povezanega linearnega seznama.
  31. Predstavitev enojno povezanega linearnega seznama v Javi.
  32. Formalno opiši podatkovno strukturo vrsta.
  33. S pomočjo osnovnih operacij nad vrsto in skladom obrni vrstni red elementov v skladu.
  34. S pomočjo osnovnih operacij nad vrsto iz vrste odstrani n-ti element.
  35. Razloži, kako bi lahko vrsto predstavil s pomočjo tabele in opiši osnovne algoritme.
  36. Sestavi algoritem, ki z osnovnimi operacijami nad vrsto pove, kateri je n-ti element vrste (če obstaja).
  37. 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.
  38. 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.
  39. 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.
  40. Algoritem, ki izpiše podatke iz enojno povezanega linearnega seznama.
  41. Algoritem, ki odstrani vsak drugi element iz dvono povezanega linearnega seznama.
  42. Formalno opiši podatkovno strukturo dvojiško drevo.
  43. Pregledi dvojiškega drevesa. Opiši in na praktičnem primeru izvedi.
  44. Sestavi algoritem, s katerim iz premega in vmesnega vrstnega reda rekonstruiraš drevo.
  45. Sestavi algoritem, s katerim iz obratnega in vmesnega vrstnega reda rekonstruiraš drevo.
  46. Sestavi algoritem, s katerim ugotoviš višino dvojiškega drevesa. Uporabi le osnovne operacije nad drevesom.
  47. V dvojiškem drevesu hranimo cela števila. Sestavi algoritem, s katerim izračunaš povprečno vrednost elementov v drevesu.
  48. 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.
  49. Predstavitev dvojiškega drevesa s tabelo.
  50. Predstavitve dvojiških dreves v Javi.
  51. Z osnovnimi operacijami sestavi zrcalno kopijo dvojiškega drevesa.
  52. Dano je dvojiško iskalno drevo. Izpiši elemente urejeno od najmanjšega do največjega.
  53. Dano je dvojiško iskalno drevo. Izpiši elemente urejeno od največjega do najmanjšega.
  54. Sestavi algoritem, ki iz sklada zgradi iskalno dvojiško drevo.
  55. 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).
  56. 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)
  57. Sestavi algoritem, ki v iskalnem dvojiškem drevesu poišče minimalni in maksimalni element.
  58. Sestavi algoritem, ki s pomočjo osnovnih operacij nad dv. drevesom, v dvojiškem drevesu poišče minimalni in maksimalni element.
  59. Iskalno drevo.
  60. Dano je dvojiško iskalno drevo. Poišči največji in najmanjši podatek.
  61. Vstavljanje v iskalno drevo.
  62. Razloži, kaj je to kopica in sestavi algoritem, ki vstavi nov podatek v kopico.
  63. Sestavi kopico, če vse elemente poznaš vnaprej.
  64. Elementi so shranjeni v kopici. Sestavi algoritem s katerim jih preložiš v tabelo tako, da so v tabeli urejeni.
  65. 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?
  66. Sestavi algoritem, s katerim odstraniš vrhnji podatek iz kopice.
  67. Sestavi algoritem, ki poišče najbolj desni element v kopici, iskalnem drevesu in običajnem dv. drevesu. Ima element kakšne posebne značilnosti?
  68. 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!
  69. Sestavi algoritem, s katerim odstraniš poljubni podatek iz kopice.
  70. 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, ...
  71. Sestavi algoritem, s katerim v kopici poiščeš najmanjši in največji element!
  72. Sestavi algoritem, s katerim poiščeš element v dvojiškem iskalnem drevesu.
  73. 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?
  74. 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.
  75. Sestavi algoritem, s katerim vstaviš nov element v dvojiško iskalno drevo.
  76. Graf je predstavljen z matriko sosednosti. Sestavi algoritem, ki za vsako vozlišče ugotovi njegovo stopnjo.
  77. 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.
  78. Opiši hitro urejanje: algoritem, časovna zahtevnost, ...
  79. Primerjaj vstavljanje, izbiranje in urejanje z mehurčki.
  80. Razloži algoritem za urejanje z vstavljanjem.
  81. 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!
  82. Razloži algoritem za urejanje z izbiranjem.
  83. Razloži algoritem za urejanje z mehurčki.
  84. Na praktičnem primeru pokaži, kako deluje hitro urejanje in urejanje z zlivanjem.
  85. Urejanje z zlivanjem.
  86. Urejanje s kopico.
  87. Napiši algoritem za urejanje z vstavljanjem in analiziraj njegovo časovno zahtevnost.
  88. Napiši algoritem za urejanje z izbiranjem in analiziraj njegovo časovno zahtevnost.
  89. Napiši algoritem za urejanje z mehurčki in analiziraj njegovo časovno zahtevnost.
  90. Opiši metodo deli in vladaj.
  91. Opiši, kako bi z metodo deli in vladaj poiskal k-ti največji element v tabeli števil.
  92. Strassenovo množenje matrik.
  93. Razloži, kako z bisekcijo poiščeš element v urejeni tabeli števil. Analiziraj časovno zahtevnost metode.
  94. Naštej nekatere probleme, ki jih lahko rešiš s pomočjo metode deli in vladaj in opiši algoritem za enega od teh.
  95. Analiziraj časovno zahtevnost iskanja minimalnega elementa z direktnim iskanjem (zaporedno primerjanje) in z metodo deli in vladaj.
  96. S pomočjo metode deli in vladaj sestavi algoritem, ki poišče dve točki v ravnini, ki sta med sabo najmanj oddaljeni.
  97. Razporejanje programskih enot na trak - dokaz pravilnosti postopka.
  98. Požrešna metoda - opiši pojem dopustna rešitev in optimalna rešitev. Prikaži nekaj primerov.
  99. Problem enostavnega nahrbtnika.
  100. Dokaži pravilnost rešitve za problem enostavnega nahrbtnika.
  101. Razporejanje programskih enot na trak.
  102. Kaj je minimalno vpeto drevo in uporaba slednjega.
  103. Na praktičnem primeru razloži, kako deluje Primov in  Kruskalov postopek.
  104. 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.
  105. 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?
  106. Razlike med Primovim in Kruskalovim postopkom, kdaj bi lahko uporabili ta postopek?
  107. Opiši postopek reševanja problema postavitve n-kraljic na šahovsko desko.
  108. Sestavi algoritem, ki v labirintu poišče pot do izhoda.
  109. 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!
  110. Kako optimalno zmnožimo verigo matrik? Opiši algoritem!
  111. Razloži, zakaj uporaba rekurzije ni primerna za neposreden zapis Bellmanove enačbe pri množenju matrik.
  112. Problem 0/1 nahrbtnika.
  113. Črno/belo barvanje grafa
  114. Drevo stanj za problem trgovskega potnika potnika - pomen vozlišč in pomen ocen ..
  115. S strojem izdelujemo različne izdelke. Čas, potreben za pripravo stroja, je odvisen od tega, kaj želimo delati in kaj smo delali prej. Ta čas smo izmerili. Sedaj moramo izdelati n različnih izdelkov. V kakšnem vrstnem redu naj jih izdelamo, da bomo porabili za to najmanj časa?
  116. Za omrežje dano z matriko 4 x 4 skiciraj drevo stanj, kjer v vozliščih drevesa vpišeš točne vrednosti za minimalno dolžino pripadajočih ciklov.
  117. Navedi vse krožne poti vozlišč označenih od 1 do 7, ki vsebujejo
    a. Povezavo med vozlišči 1 in 3 ter 5 in 1.
    b. Pot 1 - 2 - 6 - 4 - 3
    c. Pot 2 - 6 - 4 - 3
    d. Povezave 1 - 2, 3 - 5, 7 - 4
    Kako bi predstavil ustrezno matriko omrežja, ki bi predstavljala zgoraj navedena stanja?
  118. Vrtalni stroj mora izvrtati n lukenj. V kakšnem vrstnem redu naj vrta, da bo vrtalna glava prepotovala najkrajšo pot?
  119. Na praktičnem primeru razloži, kako poteka reševanje problema trgovskega potnika z metodo razveji in omeji.
  120. Razloži pomen vozlišč in vrednosti v drevesu stanj pri reševanju problema trgovskega potnika z metodo z razveji in omeji.