Tietorakenteet, loppukoe 26.9.2000

Kirjoita jokaisen vastauspaperisi alkuun kurssin nimi ja kokeen päivämäärä sekä nimesi, henkilötunnuksesi ja allekirjoituksesi.

- Määrittele jono abstraktina tietotyyppinä API-kuvauksen tapaan. Jonon alkiot voivat olla mitä tahansa Javan olioita.
- Vertaile jonon erilaisia taulukkototeutuksia ja erilaisia linkitettyjä toteutuksia.
- Selitä piirroksin jonon toteutus linkitettynä rengaslistana.
- Mikä on AVL-puu ja millaisia ominaisuuksia sillä on?
- Määrittele täsmällisesti AVL-puun solmujen rakenne. Puuhun talletettavien arvojen luokat toteuttavat Comparable-rajapintaluokan, mitään muuta niistä ei tiedetä.
- Alunperin tyhjään AVL-puuhun viedään avaimet 9, 7, 5, 3, 1, 2. Piirrä kuvasarja puun elämästä. (Kahdesta vaihtoehtoisesta toteutuksesta tässä käytetään periaatetta: "vasemman alipuun maksimi".)
Hajautettavat avaimet ovat luvut 4371, 1323, 6173, 4199, 4344, 9679, 1989. Hajautin on h(avain)=avain%10. Esitä sarjakuvana avainten hajautus tapauksissa:
- avoin hajautus
- suljettu hajautus, lineaarinen törmäyksenselvitysstrategia
- suljettu hajautus, neliöivä törmäyksenselvitysstrategia
- Mikä on keko ja millaisia ominaisuuksia sillä on?
- Binäärikeko on toteutettu taulukkona. Keon alkiot toteuttavat rajapintaluokan ComparableAndPrintable:
```
 
     public interface ComparableAndPrintable {
       public int compareTo(Object toinen);
       public String toString();
     }
   
```
  Täsmennä keon talletustapa Java-määrittelyin ja ohjelmoi ilmentymämetodi, joka tulostaa keon alkiot sisäjärjestyksessä.