581325-0 Tietorakenteet, 1. kurssikoe 11.3.2002/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. Tarkenna Vector-tietotyypin toteutus peräkkäistalletuksena taulukkoon ja toteuta operaatiot 1, 2, 4, 7, 9 ja 10. Jos oletusarvoisesti varattu taulukko (koko esim. 10) jää liian pieneksi, taulukko korvataan suuremmalla. Pyri tehokkaisiin toteutuksiin.
   2. Tarkenna Vector-tietotyypin toteutus linkitettynä listana ja toteuta operaatiot 1, 2, 5, 6, 8 ja 11. Pyri tehokkaisiin toteutuksiin.
   3. Luettele taulukkona operaatioiden 4-11 aikavaativuudet molemmissa toteutuksissa O-luokkina. Jos jokin kohta on mielestäsi odottamattoman tehokas, perustele. (So. jos olet keksinyt jotakin ovelaa, varmista että tarkastajakin ymmärtää, miten operaatio toteutetaan.)

                                                                 (8 pistettä)
   
   
   
   

2. 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.

                                                                 (8 pistettä)
   
   
   

3. 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
   1. public String kaukaisinEsivanhempi() palauttaa arvonaan puun kaukaisimman sukulaisen nimen, so. sen esivanhemman nimen, johon juuresta (so. "minusta") on pisin polku. Jos vastaus ei ole yksikäsitteinen, riittää palauttaa jonkin kaukaisimman sukulaisen nimi. Arvioi operaation aikavaativuusluokka.

   2. public void tulostaPerinteisenNimenSaaneet() tulostaa kaikki ne henkilöt, joilla on täsmälleen sama nimi kuin edes yhdellä esivanhemmalla (tai vanhemmalla). Henkilön tulostaminen tarkoittaa tässä nimen ja syntymävuoden tulostamista. Arvioi operaation aikavaativuusluokka.

                                                                    (8 pistettä)