581325-0 Tietorakenteet, 2. kurssikoe 9.4.2003/AW

1. Alunperin tyhjään AVL-puuhun viedään ensin avaimet 33, 63, 23, 40, 38, 57. Piirrä AVL-puu näiden lisäysten jälkeen. Sitten puuhun lisätään vielä avaimet 1, 2, 3, 4. Piirrä AVL-puu näiden lisäysten jälkeen.

   Lopuksi puu tulkitaankin vain tavalliseksi hakupuuksi ja siitä poistetaan remove-operaatiolla avain 2. Piirrä hakupuu näiden poistojen jälkeen,

   • kun kahdesta poisto-operaation vaihtoehtoisesta toteutuksesta käytetään periaatetta: "vasemman alipuun maksimi",
   • kun kahdesta poisto-operaation vaihtoehtoisesta toteutuksesta käytetään periaatetta: "oikean alipuun minimi".
   Häviääkö hakupuun AVL-ominaisuus näiden poistojen yhteydessä? Miksi tai miksi ei?

                                                                 (8 pistettä)
   

2. Binäärikeon alkiot ovat Comparable-olioita:

     public interface Comparable {
       public int compareTo(Object toinen);
     }
   
   

   Keko on toteutettu peräkkäistalletuksena taulukkoon. Ohjelmoi keko-operaatiot:

   1. public boolean insert(Comparable alkio)
      lisää parametrina saadun olion kekoon; metodi palauttaa true, jos lisäys onnistui, false, jos keko oli täynnä
   2. public Comparable deleteMin()
      palauttaa arvonaan viitteen keon pienimpään alkioon ja poistaa tämän alkion keosta
   3. public static void teeKeoksi(Comparable[] taulukko)
      järjestää minkä tahansa parametrina annetun Comparable-taulukon O(n)-ajassa minimikeoksi
   Kuvaile keon toteutuksen yksityiskohtia sen verran, että operaatioiden toteutukset voi ymmärtää.

                                                                 (8 pistettä)
   

3. 1. Selitä ja kuvaile täsmällisesti verkon toteutus vierusmatriisina ja vieruslistana.
   2. Ohjelmoi metodi, joka tulostaa vierusmatriisina esitetyn verkon solmujen tuloasteet ja lähtöasteet.
   3. Ohjelmoi metodi, joka tulostaa vieruslistana esitetyn verkon solmujen tuloasteet ja lähtöasteet.

                                                                 (8 pistettä)