Tietorakenteet, 1. välikoe 12.3.2001

581325-0 Tietorakenteet, 1. välikoe 12.3.2001/AW

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

Selitä täsmällisesti ja havainnollisesti, mitä funktioluokat O(f(n)) tarkoittavat ja miten niitä käytetään algoritmien suoritusajan luonnehdintaan? Anna esimerkkejä algoritmeista, jotka kuuluvat luokkiin O(1), O(log n), O(n), O(n²) ja O(2ⁿ). Perustele.
```
                                                              (7 pistettä)
```
Juna esitetään kahteen suuntaan linkitettynä listana. Veturi ja vaunut ovat merkkijonoja. Ohjelmoi luokka Juna, jolla on operaatiot:
- public Juna(String veturi)
  luo pelkästä veturista muodostuvan junan
- public void lisääPerään(String vaunu)
  lisää vaunu:n junan perään
- public Juna liitä(Juna toinen)
  liittää junan perään toisen junan vaunut; liitettävä vaunujono irroitetaan vanhasta veturista; metodi palauttaa arvonaan pidennetyn junan; liitettävän junan veturia ei siis oteta mukaan;
- public Juna irroitaHäntä(int moneskoVaunu, String veturi)
  irroittaa this-junasta loppuosan vaunusta numero moneskoVaunu alkaen omaksi junakseen, jonka veturi annetaan parametrina; arvonaan metodi palauttaa lopusta irroitetun junan vetureineen; myös alkuperäinen juna siis muuttuu
- public int monentenako(String vaunu, int mistäEteenpäin)
  palauttaa arvonaan junan ensimmäisen vaunu:n järjestysnumeron, kun etsintä aloitetaan vaunusta, jonka järjestysnumero annetaan parametrina; vaunut on numeroitu yhdestä alkaen
- public int pituus()
  junan vaunujen lukumäärä
- public String toString()
  luo junan merkkijonoesityksen
Määrittele metodien käyttäytyminen myös virhetilanteissa.
Laadi luokkaa Juna käyttäen ratapihan töidensuunnittelijalle kirjastoluokka Tyokalut, joka sisältää seuraavat välineet:
- laske annetun nimisten vaunujen määrä junassa (esim. "makuuvaunu")
- poista annetun nimiset vaunut junasta (esim. "säiliövaunu")
- vaihda junan vaunujen järjestys päinvastaiseksi ("paluumatkaa" varten... :-)
Huom: Työkalut on toteutettava käyttäen pelkästään yllä lueteltuja julkisia metodeita.
```
                                                              (7 pistettä)
```

Määrittele lista, pino ja jono abstraktina tietotyyppinä.

                                                              (4 pistettä)

Binääripuu esittää sellaista sukupuuta, jossa juurena on "minä". Juuren alipuut ovat "äiti" ja "isä", jne. Puun määrittely alkaa seuraavasti:
```
   public class Sukupuu {

     private class Sukulainen {
       private String nimi;
       private int syntymävuosi;
       private Sukulainen äiti, isä;
     }

     private Sukulainen juuri;

     public Sukupuu() {
       juuri = null;
     }
     ...
```
Ohjelmoi luokkaan metodit (määrittele toiminta myös virhetilanteissa)
- public int kaukaisinEsivanhempi() palauttaa arvonaan puun pisimmän polun pituuden "minusta" esivanhempaan.
- public String sukulaisuus(String nimi) palauttaa arvonaan "minun" ja annetun esivanhemman sukulaisuussuhteen muodossa "äidin isän isän äidin isän äidin äiti". Voit olettaa, että puun henkilöillä on yksikäsitteiset nimet.
- public void tulostaVanhinSynnyttäjä() tulostaa sen esivanhemman nimen, joka on synnyttänyt lapsensa vanhimpana. Jos henkilö ei ole yksikäsitteinen, kaikki vanhimmat tulostetaan.
```
                                                              (7 pistettä)
```