Eksamensoppgaver

Råd og tips: Bruk ikke for lang tid på et punkt. Gå isteden videre til neste punkt og eventuelt tilbake hvis du får god tid. Resultatet fra et punkt som du ikke har løst, kan brukes senere i en oppgave som om det var løst. Prøv alle punktene. De 10 bokstavpunktene teller likt!

Hvis du skulle ha bruk for en datastruktur fra java.util eller fra kompendiet, kan du fritt bruke det uten å måtte kode det selv. Men du bør si fra dette i en kommentar.

Kode kan være selvforklarende hvis det er en enkel algoritme med standard kodeteknikk. Men hvis koden din er mer innfløkt, er det viktig med forklaringer. Hvis idéen din ville ha virket, men er feil eller mangelfullt kodet, kan den være vanskelig å forstå uten kommentarer. Dermed risikerer du å få færre poeng (eller 0 poeng) enn du ellers ville ha fått.

Der det spørres etter en utskrift, er det spesielt viktig med forklaringer. Hvis det du har satt opp er feil, kan du risikere å få 0 poeng hvis forklaringer mangler. Det kan jo hende at du har tenkt riktig, men kun gjort noen småfeil. Uten forklaringer er det ikke mulig å vite om det er småfeil eller om feilen skyldes at du har bommet fullstendig.

Oppgave 1

Et skjelett for klassen Mengde er satt opp i vedlegget. Klassen har en heltallstabell a som instansvariabel. Den har to konstruktører og metodene toString, equals og snitt.

 1A.   Lag konstruktøren public Mengde(int[] b, int n) (se vedlegget). Tabellen a skal ha lengde n og skal få som innhold de n første verdiene fra parametertabellen b. Hvis de n første verdiene i b ikke er sortert stigende eller inneholder like verdier, skal det kastes en IllegalArgumentException med en tekst. Lag så metoden toString (se vedlegget). Den skal returnere en tegnstreng som inneholder verdiene i a innrammet av hakeparenteser med komma og blank mellom hver verdi. Flg. kodebit viser hvordan dette skal virke:

  int[] b = {1,2,5,9,11,13,0,0,0,0};
  Mengde B = new Mengde(b, 6);   // de 6 første verdiene i b
  System.out.println(B);         // et implisitt kall på toString

  // Utskrift: [1, 2, 5, 9, 11, 13]

 1B.   Lag metoden public boolean equals(Mengde B) (se vedlegget). Den skal returnere true hvis instansen som kaller metoden og mengden B er like (dvs. har samme innhold) og false ellers. Lag så metoden public Mengde snitt(Mengde B) (se vedlegget). Den skal returnere en mengde som er snittet (det som er felles) for den instansen som kaller metoden og mengden B. Flg. kodebit viser hvordan det skal virke:

  int[] a = {2,3,4,5,7,9,11,15};
  int[] b = {1,2,5,9,11,13};
  int[] c = {3,4,6,10,12};

  Mengde A = new Mengde(a, a.length);  // hele a
  Mengde B = new Mengde(b, b.length);  // hele b
  Mengde C = new Mengde(c, c.length);  // hele c

  System.out.println(A.snitt(B) + "  " + B.snitt(C));
  // Utskrift: [2, 5, 9, 11]  []

Oppgave 2

 2A.  

Figur 1 : Et binærtre

Figur 1 til venstre viser et generelt binærtre der nodeverdiene er bokstaver. I et binærtre har hver node en posisjon. Rotnoden har posisjon 1. Videre gjelder at hvis en node har posisjon k, vil et eventuelt venstre barn ha posisjon 2k og et eventuelt høyre barn ha posisjon 2k + 1.

1. Lag en kopi av treet i Figur 1 i din besvarelse og skriv ved siden av hver node posisjonen til noden.

2. Legg inn to nye noder i treet: Den første skal ha verdi P og posisjon 26 og den andre verdi Q og posisjon 45.

 2B.   I vedlegget står grensesnittet Stakk. Hva blir utskriften fra flg. kodebit? Se nøye på koden! Gi en forklaring til svaret ditt.

  Stakk<Character> s = new TabellStakk<>();
  s.leggInn('A'); s.leggInn('B');
  s.leggInn('C'); s.leggInn('D');

  for (int i = 0; i < s.antall(); i++)
    System.out.println( i + " " + s.antall() + " " + s.taUt() );

Oppgave 3

 3A.  

Figur 2: Et binærtre uten verdier

Sett opp tallene fra 1 til 15 i en rekkefølge slik at hvis de settes inn i den rekkefølgen i et på forhånd tomt binært søketre, vil treet få samme form som i
Figur 2 til venstre. Gi en forklaring på svaret ditt.

Hver node i et binærtre har et bestemt antall noder i sitt venstre subtre. I treet i Figur 2 til venstre er det f.eks. syv noder i rotnodens venstre subtre. Kopier dette treet i din besvarelse og skriv ved siden av hver node antallet noder det er i det venstre subtreet. Hvis noden har et tomt venstre subtre, vil antallet noder i subtreet være 0.

Vedlegget har et «skjelett» av klassen SBinTre - et binært søketre. Der har hver node i tillegg til variablene verdi, venstre og høyre, også en heltallsvariabel vAntall. Mer om den i Oppgave 3C.

 3B.   Lag metoden (se vedlegget) public T minst(). Den skal returnere treets minste verdi, dvs. den verdien som er først i inorden. Hvis treet er tomt, skal det kastes en NoSuchElementException med en passende tekst.

 3C.   Etter en innlegging vil noen noder (men normalt ikke alle) få én node mer i sitt venstre subtre enn det var fra før. Gjør om leggInn-metoden (se vedlegget) slik at etter hver innlegging vil variabelen vAntall ha korrekt verdi i hver node, dvs. ha som verdi det antallet noder det er i nodens venstre subtre. I besvarelsen din holder det om du tar med den delen av koden der endringene skjer. Gi en forklaring på hva du gjør.

Lag så metoden (se vedlegget) public T hent(int indeks). Den skal returnere den verdien i treet som ligger som nr. indeks i inorden. Indeks 0 betyr den første i inorden, indeks 1 den andre i inorden, osv. Hvis det ikke finnes noen verdi i treet med oppgitt indeks, skal det kastes en NoSuchElementException med en passende tekst. Lag metoden så effektiv som mulig. Du kan ta som gitt at variabelen vAntall har korrekt verdi i hver node. Forklar hvordan du har tenkt at metoden din skal virke. Hvilken orden har metoden din?

 3D.   Lag metoden public String toString() (se vedlegget) i klassen SBinTre. Den skal returnere en tegnstreng som inneholder treets verdier i inorden innrammet av hakeparenteser med komma og blank mellom hver verdi. Hvis treet er tomt, skal tegnstrengen inneholde []. Flg. eksempel viser hvordan det skal virke:

  Comparator<Integer> c = Komparator.naturlig(); // den vanlige ordningen

  SBinTre<Integer> tre = new SBinTre<>(c);

  int[] a = {8,2,1,4,3,6,5,7,11,9,10,15,13,12,14};

  for (int k : a) tre.leggInn(k);

  System.out.println(tre);  // toString kalles implisitt

  // Utskrift: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

Oppgave 4

 4A.   Koden for metoden public static void ukjent(char[] a) står i vedlegget. Hva blir utskriften fra flg. programbit? Gi en forklaring på svaret ditt.

  char[] c ="TETRAROTS".toCharArray();
  ukjent(c);
  System.out.println(Arrays.toString(c));

 4B.  

Figur 3: En binær minimumsheap

Figur 3 til venstre har en binær minimumsheap, dvs. et binært og komplett minimumstre. 1) Legg inn verdien 6 i treet i Figur 3 ved å bruke regelen for innlegging i en minimumsheap. Tegn treet. 2) Legg deretter inn 10 på samme måte. Tegn treet. 3) Gå så tilbake til treet slik det er i Figur 3. Ta ut den minste verdien ved å bruke regelen for å ta ut fra en minimumsheap. Tegn treet.

Vedlegg

///////// class Mengde ////////////////////////////

public class Mengde
{
  private int[] a;

  public Mengde()  // konstruktør
  {
    a = new int[0];
  }

  public Mengde(int[] b, int n)  // konstruktør
  {
    // kode mangler - skal lages
  }

  public String toString()
  {
    // kode mangler - skal lages
  }

  public boolean equals(Mengde B)
  {
    // kode mangler - skal kodes
  }

  public Mengde snitt(Mengde B)
  {
    // kode mangler - skal lages
  }

} // class Mengde

///////// interface Stakk ////////////////////////////

public interface Stakk<T>
{
  public void leggInn(T verdi);   // legger verdi på toppen
  public T kikk();                // ser på den øverste
  public T taUt();                // tar ut den øverste
  public int antall();            // antall på stakken
  public boolean tom();           // er stakken tom?
  public void nullstill();        // tømmer stakken
}

///////// klassen SBinTre ////////////////////////////

public class SBinTre<T>
{
  private static final class Node<T> // en indre nodeklasse
  {
    private T verdi;                 // nodens verdi
    private Node<T> venstre, høyre;  // venstre og høyre barn
    private int vAntall;             // antall noder i venstre subtre

    private Node(T verdi)  // konstruktør
    {
      this.verdi = verdi;
      venstre = høyre = null;
      vAntall = 0;
    }
  } // class Node

  private Node<T> rot;
  private int antall;
  private final Comparator<? super T> comp;

  public SBinTre(Comparator<? super T> c)  // konstruktør
  {
    rot = null;
    antall = 0;
    comp = c;
  }

  public int antall(){ return antall; }

  public boolean tom(){ return antall == 0; }

  public boolean leggInn(T verdi)
  {
    Node<T> p = rot, q = null;
    int cmp = 0;

    while (p != null)
    {
      q = p;
      cmp = comp.compare(verdi,p.verdi);
      p = cmp < 0 ? p.venstre : p.høyre;
    }

    p = new Node<>(verdi);

    if (q == null) rot = p;
    else if (cmp < 0) q.venstre = p;
    else q.høyre = p;

    antall++;
    return true;
  }

  public T minst()
  {
    // mangler kode - skal kodes
  }

  public T hent(int indeks)
  {
    // mangler kode - skal kodes
  }

  public String toString()
  {
    // mangler kode - skal kodes
  }

} // SBinTre


///////// metoden ukjent ////////////////////////////

  public static void ukjent(char[] c)
  {
    int v = 0, h = c.length - 1;

    while (v < h)
    {
      char d = c[v];
      c[v] = c[h];
      c[h] = d;
      v++;
      h--;
    }
  }