Eksamensoppgaver

Råd og tips:  Bruk ikke for lang tid på et punkt i en oppgave hvis du ikke får det til innen rimelig tid. Gå isteden videre til neste punkt. Hvis du i et senere punkt får bruk for det du skulle ha laget i et tidligere punkt, kan du fritt bruke resultatet som om det var løst og at løsningen virker slik som krevd i oppgaven. Prøv alle punktene. Det er ikke lurt å la noen punkter stå helt blanke. Til og med det å demonstrere i en eller annen form at du har forstått hva det spørres etter og/eller at du har en idé om hvordan det kunne løses, er bedre enn ingenting. Det er heller ikke slik at et senere punkt i en oppgave nødvendigvis er vanskeligere enn et tidlig punkt. Alle 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 kommentere at du gjør det.

Oppgave 1

Grensesnittet Kø står i vedlegget.

 1A.   Hva blir utskriften fra flg. kodebit? Svaret må begrunnes!

  Kø<Integer> kø = new LenketKø<>();  // en lenket kø
  kø.leggInn(5);
  kø.leggInn(3);
  kø.leggInn(1);

  for (int i = 0; i < 5; i++) kø.leggInn(kø.taUt());

  while (!kø.tom()) System.out.print(kø.taUt() + " ");

 1B.   Lag metoden public static <T> void kopier(Kø<T> A, Kø<T> B). Metoden skal gjøre at køen B får de samme verdiene i samme rekkefølge som det A har. Køen A skal etterpå være som den opprinnelig var. Metoden skal helst kodes uten bruk av en hjelpestruktur. Se flg. eksempel:

  Kø<Integer> A = new TabellKø<>();  // A er en tom tabellkø
  Kø<Integer> B = new LenketKø<>();  // B er en tom lenket kø

  int[] tall = {1,2,3,4,5};
  for (int k : tall) A.leggInn(k);   // legger inn tallene i A

  kopier(A,B);                       // B blir en kopi av A

  System.out.println(A + " " + B);   // bruker toString-metoden

  // Utskrift: [1, 2, 3, 4, 5] [1, 2, 3, 4, 5]

Oppgave 2

Vedlegget inneholder et «skjelett» for klassen EnkelListe. Listen er organisert som en pekerkjede med et hode som peker til den første noden i listen. Noen av metodene som er satt opp, er ferdigkodet. Klassen skal ikke ha flere instansvariabler enn de som allerede er satt opp. Hvis du skulle trenge flere metoder enn de som er satt opp, må du sette dem opp og kode dem selv.

 2A.   Metoden public void leggInnFørst(T verdi) er ferdigkodet. Den legger en verdi først i listen. Lag metoden public void leggInnSist(T verdi). Den skal legge en verdi sist (bakerst) i listen.

 2B.   Lag metoden public void snu(). Den skal snu rekkefølgen i listen. I metoden skal det hverken forsvinne noder eller lages nye noder. Flg. eksempel viser hvordan det skal virke:

  char[] tegn = "ABCDEFGHIJ".toCharArray();

  EnkelListe<Character> liste = new EnkelListe<>();
  for (char c : tegn) liste.leggInnFørst(c);

  System.out.println(liste);
  liste.snu();
  System.out.println(liste);

  // Utskrift:
  // [J, I, H, G, F, E, D, C, B, A]
  // [A, B, C, D, E, F, G, H, I, J]
 

Oppgave 3

 3A.   Gitt tallene: 8, 3, 6, 9, 12, 2, 5, 10, 7, 13, 1, 4, 10, 5. Legg dem inn, i den gitte rekkefølgen, i et på forhånd tomt binært søketre (duplikater er tillatt). Tegn treet. Skriv ut verdiene i preorden.

Vedlegget inneholder et «skjelett» for klassen SBinTre - et binært søketre. Av de metodene som klassen inneholder, er noen ferdigkodet. Resten skal kodes.

 3B.   Lag metoden public T sistePreorden(). Den skal returnere den siste verdien i preorden. Hvis treet er tomt, skal det kastes en NoSuchElementException med en tekst.

 3C.   Lag metoden private Node<T> nestePreorden(Node<T> p). Den skal returnere den noden som kommer rett etter noden p i preorden. Du kan anta at   p ikke er null. I de tilfellene der den neste ligger oppover i treet (nærmere roten), kan en finne den ved å starte i roten og gå nedover til p ved hjelp av vanlig søketeknikk (dvs. søke etter verdien til p). Hvis p er den siste, skal metoden returnere null. Lag så metoden public void preorden(Oppgave<T> oppgave). Den skal traversere treet iterativt i preorden og utføre oppgaven for hver nodeverdi. Til dette skal du benytte metoden   nestepreorden selv om du ikke har kodet den. Da antar du bare at den virker som skal. Hvis treet er tomt, skal ingenting utføres. Grensesnittet Oppgave står i vedlegget.

 3D.   Lag metoden public String lengstgren(). Den skal returnere en tegnstreng som inneholder verdiene i treets lengste gren, dvs. grenen som går til den bladnoden som ligger lengst vekk fra roten. Hvis det er flere enn én bladnode som ligger lengst vekk, skal den av dem som ligger lengst til høyre brukes. Hvis treet er tomt, skal "[]" returneres. Flg. eksempel viser hvordan metoden skal virke på treet du tegnet i Oppgave 3A):

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

  Comparator<Integer> c = Komparator.naturlig();  // en komparator
  SBinTre<Integer> tre = new SBinTre<>(c);        // et tre
  for (int k : a) tre.leggInn(k);                 // bygger treet

  System.out.println(tre.lengstgren());   // den lengste grenen

  // Utskrift: [8, 9, 12, 10, 10]

Oppgave 4

 4A.   En melding inneholder kun tegnene A, B, C, D, E, F, G og H. Tegnenes frekvensfordeling gir flg. Huffmantre der hvert tegn står under tilhørende bladnode:

I et binærtre har hver node en posisjon. Rotnoden her posisjon 1. Hvis en node har posisjon k, har venstre barn posisjon 2k og høyre barn posisjon 2k + 1.

1. Sett opp posisjonene til bladnodene i Huffmantreet.
2. Sett opp de bitkodene som treet gir for de åtte tegnene.
3. En melding som ble komprimert ved hjelp av disse bitkodene, ble komprimert til 11001110010110011111011. Dekomprimer dette.

 4B.   I en prioritetskø er det alltid den minste verdien (minst med hensyn på en komparator) som tas ut. Hva blir utskriften fra flg. kodebit. Komparatoren SKomparator står i vedlegget. Gi en begrunnelse for svaret!

  Comparator<String> c = new SKomparator();
  PrioritetsKø<String> kø = new HeapPrioritetsKø<>(c);

  kø.leggInn("Per");
  kø.leggInn("Kari");
  kø.leggInn("Ole");
  kø.leggInn("Asta");

  while (!kø.tom()) System.out.print(kø.taUt() + " ");

Vedlegg

public interface Kø<T>
{
  public void leggInn(T verdi);   // legger inn bakerst
  public T kikk();                // ser på det som er først
  public T taUt();                // tar ut det som er først
  public int antall();            // antall i køen
  public boolean tom();           // er køen tom?
  public void nullstill();        // tømmer køen

} // grensesnittet Kø

public class EnkelListe<T>
{
  private static final class Node<T>  // en indre nodeklasse
  {
    private T verdi;
    private Node<T> neste;

    private Node(T verdi, Node<T> neste)  // nodekonstruktør
    {
      this.verdi = verdi; this.neste = neste;
    }
  }

  private Node<T> hode;   // pekere til første node
  private int antall;     // antall noder i listen  

  public EnkelListe()     // standardkonstruktør
  {
    hode = null;  antall = 0;
  }

  public void leggInnFørst(T verdi)
  {
    hode = new Node<>(verdi,hode);
    antall++;
  }

  public void leggInnSist(T verdi)
  {
    // mangler kode - skal kodes
  }

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

  public int antall() { return antall; }

  public void snu()
  {
    // mangler kode - skal kodes
  }

  public String toString()
  {
    if (tom()) return "[]";

    StringBuilder s = new StringBuilder();
    Node<T> p = hode;
    s.append('[').append(p.verdi);
    p = p.neste;

    while (p != null)
    {
      s.append(',').append(' ').append(p.verdi);
      p = p.neste;
    }
    s.append(']');
    return s.toString();
  }

} // class EnkelListe


////////////////////////////////////////////////////////////////////////


public class SBinTre<T>  // et binært søketre
{
  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 Node(T verdi) // konstruktør
    {
      this.verdi = verdi;
      venstre = høyre = null;
    }

  } // class Node

  private Node<T> rot;                         // peker til rotnoden
  private int antall;                          // antall noder
  private final Comparator<? super T> comp;    // komparator

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

  public int antall() { return antall; }

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

  public void leggInn(T verdi)
  {
    if (verdi == null)
      throw new NullPointerException("Nullverdier er ulovlig!");

    Node<T> p = rot, q = null;             // pekere
    int cmp = 0;                           // hjelpevariabel

    while (p != null)                      // while-løkke
    {
      q = p;                               // q skal være forelder til p
      cmp = comp.compare(verdi, p.verdi);  // sammenligner
      if (cmp < 0) p = p.venstre;          // går til venstre
      else  p = p.høyre;                   // går til høyre
    }

    p = new Node<>(verdi);                 // en ny node

    if (q == null) rot = p;                // tomt tre
    else if (cmp < 0) q.venstre = p;       // blir venstre barn
    else  q.høyre = p;                     // blir høyre barn

    antall++;                              // en ny node i treet
  }

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

  private Node<T> nestePreorden(Node<T> p)
  {
    // mangler kode - skal kodes
  }

  public void preorden(Oppgave<T> oppgave)
  {
    // mangler kode - skal kodes
  }

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

} // class SBinTre


////////////////////////////////////////////////////////////////////////


public interface Oppgave<T>
{
  public void utførOppgave(T t);
}


////////////////////////////////////////////////////////////////////////


public class SKomparator implements Comparator<String>
{
  public int compare(String s, String t)
  {
    int k = t.length() - s.length();

    if (k != 0) return k;

    return s.compareTo(t);
  }
}