581325-0 Tietorakenteet, 1. kurssikoe 28.2.2003/AW

1. Object-alkioinen taulukko, jonka "koko kasvaa tarpeen mukaan", voisi toisinaan olla näppärä ohjelmointiväline. Tehdään siis itse sellainen! Määritellään tietotyyppi Vector seuraavina operaatioina (lähde: Java^TM 2 Platform Std. Ed. v1.3 ) (Huomaa ettei näitä kaikkia ole tarkoitus ohjelmoida!)
   1. public Vector(): Constructs an empty vector.
   2. public int size(): Returns the number of components in this vector.
   3. public boolean isEmpty(): Tests if this vector has no components.

   4. public int indexOf(Object elem): Searches for the first occurence of the given argument, testing for equality using the equals method.
   5. public int lastIndexOf(Object elem): Returns the index of the last occurrence of the specified object in this vector.

   6. public Object get(int index): Returns the element at the specified position in this Vector.
   7. public Object set(int index, Object element): Replaces the element at the specified position in this Vector with the specified element.

   8. public boolean add(Object o): Appends the specified element to the end of this Vector.
   9. public boolean remove(Object o): Removes the first occurrence of the specified element in this Vector If the Vector does not contain the element, it is unchanged.
   10. public void add(int index, Object element): Inserts the specified element at the specified position in this Vector. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
   11. public Object remove(int index): Removes the element at the specified position in this Vector. Shifts any subsequent elements to the left (subtracts one from their indices). Returns the element that was removed from the Vector.
   1. Selitä Vector-tietotyypin toteutus tavalla tai toisella taulukkona ja toteuta operaatiot 1, 2, 5, 6, 8 ja 11. Jos oletusarvoisesti varattu taulukko (koko esim. 10) jää liian pieneksi, taulukko korvataan suuremmalla. Pyri tehokkaisiin toteutuksiin.
   2. Selioitä Vector-tietotyypin toteutus kahteen suuntaan linkitettynä listana ja toteuta operaatiot 1, 2, 4, 7, 9 ja 10. Pyri tehokkaisiin toteutuksiin.

                                                                 (8 pistettä)
   
   
   
   

2. Eräs ystäväsi ei ole ihan täydellisesti ymmärtänyt O-luokkien käyttöä algoritmien suoritusajan arvioinnissa. Auta siis ystävää hädässä ja kirjoita hänelle selkeitä ja kuvaavia esimerkkejä algoritmeista, jotka kuuluvat luokkiin O(1), O(log n), O(n), O(n²) ja O(2ⁿ). Ystävä on kuitenkin epäluuloinen. Perustele siis miksi juuri nuo algoritmit kuuluvat luokkiinsa.

                                                                 (8 pistettä)
   
   
   

3. Sellaista puuta, jonka solmujen lapsiluku voi olla 0-3, voitaisiin kutsua "trinääripuuksi". Olkoon tämän puun solmuissa tieto- ja linkkikenttien lisäksi vielä kenttä solmun korkeudelle ja syvyydelle:

      public class Puu {
        public Object tieto;
        public int korkeus, syvyys;
        public Puu vasen, keski, oikea;
      }
   

   Ohjelmoi tällaiselle "trinääripuulle" metodit:
   1. public static void asetaSyvydet(Puu juuri): asettaa puun joka solmuun kyseisen solmun syvyyden

   2. public static void asetaKorkeudet(Puu juuri): asettaa puun joka solmuun kyseisen solmun korkeuden.

                                                                 (8 pistettä)