Tölvunarfręši 2

Vikublaš 13


Ķ žessari viku veršur lokiš yfirferš um hrśgur, en sķšan tekur Anna viš og talar um tįknatöflur (e. symbol tables) og tvķleitartré (e. binary search trees) śr kafla 12 ķ kennslubókinni.

Ķ dęmatķmum veršur fariš yfir Forritunarverkefni 2.

Heimadęmi 10

Leysiš eftirfarandi dęmi og skiliš ķ hólf dęmatķmakennara ykkar fyrir kl 12:00 mįnudaginn 18. aprķl. Žeir taka ekki dęmum sem koma seinna.

  1. [Próf 2004] Hér aš nešan eru gefnar inorder, preorder og postorder rašir hnśta ķ tvķundartré meš 9 hnśta, žar sem hnśtarnir hafa gildin A til I. Žvķ mišur hafa nokkur gildi skemmst ķ sendingu, žannig aš viš vitum ekki gildin į nokkrum stöfum (tilgreindir meš ?). Reyniš aš bśa til tvķundartréš śt frį žessum ófullkomnu upplżsingum og lżsiš röksemdafęrslu ykkar. Ef upplżsingarnar eru ekki nęgar til aš bśa til einkvęmt tvķundartré, lżsiš žį žeim trjįm sem koma til greina.
         Inorder: IC?HBE?DA
         Preoder: ?C???H?D?
         Postorder: IHGB??DAE
      

  2. [Haustpróf 2004] Ein leiš til aš velja vendistakiš (e. partitioning element) ķ Quicksort er aš velja žaš af handahófi. Žį er kallaš į slemitölugjafa til aš velja tölu k į bilinu l til r og stakiš ķ sęti a[k] er notaš sem vendistak. Vandamįliš er aš góšir slembitölugjafar gera veriš tķmafrekir. Reikniš śt hversu oft yrši kallaš į slembitölugjafann ķ Quicksort ķ versta tilfelli. En ķ besta tilfelli?

  3. [Haustpróf 2004] Śtfęriš ķ C++ nżja śtgįfu af hrśgufallinu getmax. Ķ žvķ er gatinu sem myndast ķ rótinni żtt nišur ķ lauf trésins meš žvķ aš fęra sķfellt upp stęrra barniš. Sķšan er aftasta stakiš (ž.e. stakiš ķ pq[N]) sett ķ gatiš og žvķ vķxlaš uppį viš žar til hrśgueiginleikinn er uppfylltur.
    Beriš žessa ašferš saman viš getmax falliš į bls. 386 ķ kennslubókinni. Hvor ašferšin teljiš žiš aš sé hrašvirkari og hvers vegna?
    [Žar sem žetta er heimadęmi og žiš hafiš ašgang aš tölvu, žį skuluš žiš tķmamęla žessar tvęr ašferšir meš žvķ aš setja inn ķ hrśgu einhvern mikinn fjölda staka og takiš žau sķšan aftur śt meš žessum mismunandi getmax ašgeršum.]

  4. Dęmi 9.18 į bls. 383 ķ kennslubók.
    [Žżšing: Stęrsta stakiš ķ hrśgu er alltaf ķ sęti 1 og nęststęrsta stakiš er alltaf ķ sęti 2 eša 3. Fyrir hrśgu af stęršinni 15, sżniš öll žau sęti sęti žar sem k-ta stęrsta stakiš (i) getur veriš, og (ii) getur ekki veriš, fyrir k = 2, 3, 4. Geriš rįš fyrir aš gildin ķ hrśgunni séu öll mismunandi. ]

  5. Dęmi 9.25 į bls. 389 ķ kennslubók.
    [Žżšing: Bętiš ašferšinni skipta um stęrsta viš hrśgu-śtfęrsluna af forgangsbišröš ķ Forriti 9.5. Passiš aš taka į tilfellinu žar sem nżja stęrsta stakiš er stęrra en öll gildin ķ hrśgunni. Ath.: Nokun į pq[0] leišir til snišugrar lausnar. ]


annaing (hja) hi.is / hh (hja) hi.is, 11. aprķl, 2005.