581325-0 Tietorakenteet, 2. välikoe 11.4.2001/AW

1. Alunperin tyhjään AVL-puuhun viedään ensin avaimet 21, 23, 165, 203, 204 ja 546. Piirrä AVL-puu näiden lisäysten jälkeen.

   Sitten puuhun lisätään vielä avaimet 15, 14, 22, 12 ja 9. Piirrä AVL-puu näiden lisäysten jälkeen.

   Lopuksi puu tulkitaankin vain tavalliseksi hakupuuksi ja siitä poistetaan remove-operaatiolla avaimet 203 ja 21. Piirrä hakupuu näiden poistojen jälkeen. (Kahdesta poisto-operaation vaihtoehtoisesta toteutuksesta tässä käytetään periaatetta: "vasemman alipuun maksimi".)

   Häviääkö hakupuun AVL-ominaisuus poistojen yhteydessä? Jos häviää, milloin ja miksi se häviää?

                                                                 (6 pistettä)
   
   
   
   

2. 1. Mikä ja millainen on ns. hajautin? Millä perusteilla hajauttimen hyvyyttä voidaaan arvioida? Anna esimerkkejä huonoista ja hyvistä hajauttimista.

   2. Rajapintaluokka Hashable on määritelty seuraavasti:

        public interface Hashable {
          public int hash(int taulunKoko);
        }
      

      Suljetussa hajautuksessa käytetään lineaarista törmäyksenselvitysstrategiaa. Ohjelmoi metodi:

      • public void insert(Hashable arvo)
        lisää "arvon" hajautustauluun; jos jo löytyi, mikään ei muutu

      Kuvaile hajautuksen toteutuksen yksityiskohtia sen verran, että operaation toteutus on ymmärrettävä.

                                                                 (6 pistettä)
   
   
   
   
   
   

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

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

   Keko on toteutettu peräkkäistalletuksena taulukkkoon. 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ä)
   
   
   
   

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

                                                                 (5 pistettä)