581325-0 Data strukturer, andra deltenten 11.4.2001/AW

1. Ett AVL-träd är till en början tomt. Sedan förs dit nycklarna21, 23, 165, 203, 204 och 546. Rita AVL-trädet efter dessa tillägg.

   Sedan tilläggs ännu nycklarna 15, 14, 22, 12 och 9. Rita AVL-trädet efter dessa tillägg.

   Till slut tolkas trädet som ett vanligt sökträd och nycklarna 203 och 21 avlägsnas med hjälp av operationen remove. Rita sökträdet efter ändringarna. (Av två alternativa implementationer för avlägsningsoperationenanvänds här principen "maximum av vänstra underordnade trädet".)

   Försvinner sökträdets AVL-egenskap i och med avlägsningarna? Om den gör det, så när och varför?

                                                                 (6 poäng)
   
   
   
   

2. 1. Vad är en s.k. spridningsfunktion (hajautin)? Hur kan dess egenskaper utvärderas? Ge exempel på dåliga och bra spridningsfunktioner.

   2. Gränssnittsklassen Hashable specifieras så här:

        public interface Hashable {
          public int hash(int taulunKoko);
        }
      

      Vid sluten spridning (suljettu hajautus) används en lineär sonderingsstrategi. Programmera metoden

      • public void insert(Hashable värde)
        tillägger värdet i spridningstabellen; om det fanns där redan förändras inget.

      Beskriv detaljerna i implementeringen av spridningen så att man kan förstå implementeringen av operationen.

                                                                 (6 poäng)
   
   
   
   
   
   
   

3. Elementen i en binärstapel är Comparable-objekt

     public interface Comparable {
       public int compareTo(Object annan);
     }
   

   Stapeln har implementerats genom konsekutiv inmatning i en tabell. Programmera stapelfunktionerna:

   1. public boolean insert(Comparable element)
      lägger objektet som getts som parameter till stapeln ; metoden ger true om det lyckades och false om stapeln var full.
   2. public Comparable deleteMin()
      ger som sitt värde en referens till det minsta elementet i stapeln, och avlägsnar elementet från stapeln.
   3. public static void görStapel(Comparable[] tabell)
      ordnar vilken som helst Comparable-tabell som getts som parameter till en minimistapel på tiden O(n).
   Beskriv detaljerna i stapelns implementering så att man kan förstå operationernas implementering.

                                                                 (8 poäng)
   
   
   
   

4. 1. Beskriv detaljerat hur en graf kan representeras som närliggande matris (vierusmatriisi) och närliggande lista (vieruslista).
   2. Programmera en metod som ger som output antalet sidor som går ut från och in i knutpunkterna i grafen som representeras i den närliggande matrisen.

                                                                 (5 poäng)