Tlvunarfri 2

Vikubla 14


essi vika er sasta vikan ar sem fari verur eitthva ntt efni. a er reyndar bara fyrirlestur rijudeginum, ar sem fimmtudagurinn 21. aprl er sumardagurinn fyrsti og engin kennsla er eim degi. rijudeginum verur v loki vi umfjllun um tvleitartr (e. binary search trees) r kafla 12.

nstu viku vera eingngu dmatmar ar sem fari verur yfir dmin hr a nean. Einnig verur rijudeginum 26. aprl kl. 11:05 stutt yfirfer yfir nmsefni, kynning fyrirkomulagi prfsins, auk ess sem hgt verur a spyrja spurninga um efni nmskeisins.

Heimadmi 11

Leysi eftirfarandi dmi og skili hlf dmatmakennara ykkar fyrir kl 12:00 mnudaginn 25. aprl. eir taka ekki dmum sem koma seinna.

  1. Dmi 12.47 bls. 521 kennslubk.
    [ing: Teikni tvleitartr sem verur til egar i setji stk me lyklana E, A, S, Y, Q, U, E, S, T, I, O, N essari r inn tvleitartr sem er tmt upphafi. ]

  2. Hvaa r innsetninga inntakslyklunum E, A, S, Y, Q, U, E, S, T, I, O, N gefur tvleitartr sem er eins lgt og mgulegt er? Mii vi a innsetningunni s nota Forrit 12.8 bls. 517 kennslubkinni.

  3. Sni endurkvma skilgreiningu fallinu getmin( T ) tvleitartr. Falli skilar minnsta stakinu trnu T. Skilgreiningin a vera svipuum anda og skilgreiningar kafla 2 hefti nnu. i megi nota aeins myndrnni framsetningu trjnum, svipa og gert var fyrirlestri.

  4. Sni tr hr a nean eftir a hnti 15 hefur veri lyft upp fyrir hnt 10 (e. left rotation at 10):
                                      7
                                    /   \
                                   3    10
                                  /    /   \
                                 1    8    15
                                          /   \
                                         12   20
                                           \
                                           13
    

  5. [Haustprf 2004] Setja ll stk hrgu (e. heap) yfir tvleitartr (e. binary search tree). Hrgan er gefin sem N-staka vektor og i geti aeins nota agerina insert tvleitartr. i) Myndi a borga sig a setja inn stkin vektornum r fr byrjun hans, .e. fyrst pq[1], san pq[2], o.s.frv.? ii) Hva me fr hinum endanum (.e. byrja pq[N])? iii) Er einhver nnur r staka r hrguvektornum sem vri betri en r tvr ofangreindu? Rkstyji svr ykkar.


annaing (hja) hi.is / hh (hja) hi.is, 18. aprl, 2005.