Tietorakenteet, loppukoe 9.6.2000

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

Vastaa lyhyesti (enintään yksi sivu jokaisesta)

Miten O(n)-tekniikkaa käytetään algoritmien arvioinnissa?
Määrittele lista abstraktina tietotyyppinä.
Miten yleinen puu voidaan esittää binääripuuna? Entä metsä? Hahmottele pseudokielellä algoritmi, joka käy metsän läpi jossakin järjestyksessä.
Alunperin tyhjään AVL-puuhun viedään avaimet 7, 5, 8, 11, 10 ja 9. Piirrä kuvasarja puun elämästä. (Kahdesta vaihtoehtoisesta toteutuksesta tässä käytetään periaatetta: "vasemman alipuun maksimi".)
Mistä on kyse hajauttamisessa? Millainen hajautin on hyvä?
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 ja ohjelmoi ilmentymämetodi, joka tulostaa keon alkiot jälkijärjestyksessä.