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

1. Selitä täsmällisesti ja havainnollisesti, mitä funktioluokat O(f(n)) tarkoittavat ja miten niitä käytetään algoritmien suoritusajan luonnehdintaan? Miten algoritmien aikavaativuutta päätellään?

                                                                 (9 pistettä)
   

2. Yhteen suuntaan linkitettyyn tunnussolmuttomaan listaan pidetään osoitinta alkuun ja loppuun. Listan määrittely alkaa:

      public class Lista {
   
        private class Alkio {
          private Comparable tieto;
          private Alkio linkki;
        }
   
        private Alkio alku, loppu;    // listan alku ja loppu
        private int lkm;              // alkioiden lukumäärä
        ...
   

   Toteuta listaoperaatiot:
   • public boolean lisää(Comparable alkio, int paikka) lisää "alkion" kohdassa "paikka" olevan alkion seuraajaksi; lisäys paikkaan 0 tarkoitaa lisäystä listan alkuun; metodi palauttaa arvon true, jos lisäys onnistui, false, jos paikka oli mahdoton
   • public void pienetPois(Comparable arvo) poistaa listasta annettua "arvoa" pienemmät alkiot
   • public Lista liitä(Lista toinen) liittää listan perään toisen; liitetty lista, "toinen", muuttuu tyhjäksi
   • public Lista irroitaLoppu(Comparable alkio) irroittaa listan loppuosan alkaen ensimmäisestä "alkiosta"; alkuperäinen lista siis lyhenee; arvonaan metodi palauttaa irroitetun listan; jos "alkiota" ei löydy, metodi palauttaa tyhjän listan

                                                                 (8 pistettä)
   

3. Binääripuun määrittely alkaa:

      public class Puu {
   
        private class Solmu {
          Object tieto;
          Solmu vasen, oikea;
        }
   
        private Solmu juuri;
   
        public Puu() {
          juuri = null;
        }
        ...
   

   Ohjelmoi luokkaan metodit
   • public int korkeus() palauttaa arvonaan binääripuun korkeuden
   • private int syvyys(Solmu s) palauttaa arvonaan annetun solmun syvyyden
   • public void tulostaLehdet() tulostaa puun lehdet vasemmalta oikealle

                                                                 (8 pistettä)