Tölvunarfræði 2

Vikublað 14

Í næstu viku verða eingöngu dæmatímar þar sem farið verður yfir dæmin hér að neðan. Einnig verður á þriðjudeginum 26. apríl kl. 11:05 stutt yfirferð yfir námsefnið, kynning á fyrirkomulagi prófsins, auk þess sem hægt verður að spyrja spurninga um efni námskeiðsins.

Heimadæmi 11

1. Dæmi 12.47 á bls. 521 í kennslubók.
   [Þýðing: Teiknið tvíleitartréð sem verður til þegar þið setjið stök með lyklana E, A, S, Y, Q, U, E, S, T, I, O, N í þessari röð inní tvíleitartré sem er tómt í upphafi. ]

2. Hvaða röð innsetninga á inntakslyklunum E, A, S, Y, Q, U, E, S, T, I, O, N gefur tvíleitartré sem er eins lágt og mögulegt er? Miðið við að í innsetningunni sé notað Forrit 12.8 á bls. 517 í kennslubókinni.

3. Sýnið endurkvæma skilgreiningu á fallinu getmin( T ) á tvíleitartré. Fallið skilar minnsta stakinu í trénu T. Skilgreiningin á að vera í svipuðum anda og skilgreiningar í kafla 2 í hefti Önnu. Þið megið þó nota aðeins myndrænni framsetningu á trjánum, svipað og gert var í fyrirlestri.

4. Sýnið tréð hér að neðan eftir að hnúti 15 hefur verið lyft upp fyrir hnút 10 (e. left rotation at 10):

                                     7
                                   /   \
                                  3    10
                                 /    /   \
                                1    8    15
                                         /   \
                                        12   20
                                          \
                                          13
   

5. [Haustpróf 2004] Setja á öll stök hrúgu (e. heap) yfir í tvíleitartré (e. binary search tree). Hrúgan er gefin sem N-staka vektor og þið getið aðeins notað aðgerðina insert á tvíleitartréð. i) Myndi það borga sig að setja inn stökin í vektornum í röð frá byrjun hans, þ.e. fyrst pq[1], síðan pq[2], o.s.frv.? ii) Hvað með frá hinum endanum (þ.e. byrja á pq[N])? iii) Er einhver önnur röð staka úr hrúguvektornum sem væri betri en þær tvær ofangreindu? Rökstyðjið svör ykkar.