Tölvunarfræði 2

Vikublað 13

Í dæmatímum verður farið yfir Forritunarverkefni 2.

Heimadæmi 10

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. ]