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.

Oppgave 1

 1A.   I vedlegget står det en generisk metode med navn ukjentMetode. Inne i metodens kode er det en utskriftssetning. Hva blir utskriften hvis flg. kodebit utføres?

  Integer[] a = {3, 4, 2, 5, 1};
  ukjentMetode(a, Comparator.naturalOrder());

I metoden ukjentMetode inngår sammenligningen if (c.compare(a[j], mverdi) < 0). Hvor mange ganger blir den utført? Hvor mange ganger vil den bli utført hvis tabellen a har lengde n der n ≥ 0 ? Vi tenker oss nå at metodens utskriftssetning er fjernet. Hva blir i så fall metodens/algoritmens orden? Kjenner du et navn på denne algoritmen?

 1B.   Gitt tegntabellen char[] c = {'C','D','J','A','H','F','B','I','G','E'}. Tabellens indekser går fra 0 til 9. Det er A som er minst (dvs. først alfabetisk). Den har indeks 3. Deretter kommer B med indeks 6, så C med indeks 0, osv. til J med indeks 2.

Vi tenker oss at metoden public static int[] indeksTabell(char[] c) er kodet slik at den returnerer en indekstabell til parametertabellen c. Første verdi er indeksen til det minste tegnet i c, neste verdi er indeksen til det nest minste tegnet i c, osv. Siste verdi er indeksen til det største tegnet i c. Flg. kodebit viser hvordan metoden virker:

  char[] c = {'C','D','J','A','H','F','B','I','G','E'};
  int[] indeks = indeksTabell(c);               // returnerer indekstabellen
  System.out.println(Arrays.toString(indeks));  // skriver ut indekstabellen

  // Utskrift: [3, 6, 0, 1, 9, 5, 8, 4, 7, 2]   // c[indeks[0]] = A, osv.

1. La tegntabellen c = {'F','D','J','G','B','I','E','A','H','C'} inngå som parameter i metodekallet indeksTabell(c) i kodebiten over. Hva blir da utskriften?
2. Lag kode for metoden public static int[] indeksTabell(char[] c) slik at den virker som beskrevet over.

 1C.   Det er mulig å finne det største tallet i en samling av heltall ved å gjennomføre en utslagsturnering. Gjør dette for tallene 7, 15, 9, 11, 8, 5, 6, 14, 10, 12, 13. Tegn turneringstreet. Hvilke tall ble slått ut av «vinneren» i løpet av turneringen? Husk at et turneringstre er et komplett binærtre med like mange bladnoder som det er «deltagere». Hvor mange noder vil turneringstreet få hvis det er n «deltagere».

Oppgave 2

Vedlegget har et «skjelett» av den generiske klassen LenketKø<T>. Den skal virke som en vanlig kø (først inn - først ut). Metodene antall(), tom() og nullstill() er kodet.

 2A.   Anta at klassen LenketKø<T> er ferdigkodet. Klassen TabellStakk virker som en vanlig stakk (sist inn - først ut). Hva blir utskriften i flg. programbit (gi en kort forklaring)?

  Kø<Character> kø = new LenketKø<>();
  Stakk<Character> stakk = new TabellStakk<>();

  kø.leggInn('N'); kø.leggInn('I'); kø.leggInn('L'); kø.leggInn('E');

  while (!kø.tom()) stakk.leggInn(kø.taUt());
  while (!stakk.tom()) kø.leggInn(stakk.taUt());

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

LenketKø<T> skal organiseres som en sirkulær pekerkjede. Fra starten av skal pekerkjeden inneholde 8 noder og pekerne fra og til skal peke på en og samme node. Se Figur 1. Men generelt skal fra peke til den første i køen og til skal peke til den første ledige noden, dvs. den som kommer rett etter den siste i køen.

Figur 1		Figur 2	Figur 3

Vi legger først inn verdiene/bokstavene A, B, C, D, E og F, dvs. seks kall på leggInn(). Se Figur 2. Deretter gjør vi tre kall på taUt(). Da forsvinner A, B og C. Se Figur 3. Vi legger inn fire nye verdier: G, H, I og J. Se Figur 4. Da er det fortsatt en ledig node.

Figur 4		Figur 5

Hvis vi skal legge inn en verdi til (se Figur 4), f.eks. K, vil kjeden bli full og fra og til blir like. Men de to skal være like kun hvis køen er tom. Vi løser det ved å sette inn en ny og «tom» node mellom til og fra. Dermed kan K legges inn og til flyttes til neste ledige node. Dermed bevares «sirkelen». Se Figur 5.

 2B.   Lag kode for metodene kikk(), taUt() og toString(). Metoden kikk() skal returnere (men ikke fjerne) verdien som ligger først i køen, dvs. verdien i noden fra. Hvis køen er tom skal det kastes en NoSuchElementException. Metoden taUt() skal returnere (og fjerne fra køen) verdien som ligger først, dvs. verdien i noden fra. Hvis køen er tom skal det kastes en NoSuchElementException. Metoden toString() skal returnere en tegnstreng med køens verdier rammet inn med [ og ] og med komma og «space» mellom verdiene, og [] hvis køen er tom.

 2C.   Lag kode for konstruktøren og metoden leggInn(T verdi). Konstruktøren skal opprette en tom kø. Den skal være organisert som en sirkelformet pekerkjede med 8 noder som alle er «tomme», dvs. verdi er null. Pekerne fra og til skal peke på samme node. Metoden leggInn(T verdi) skal legge inn nye verdier i køen slik som beskrevet over, dvs. at det alltid skal være mulig å legge inn en verdi.

Oppgave 3

 3A.   Gitt tallene: 15, 18, 4, 8, 17, 5, 2, 12, 25, 9, 20, 13. Legg dem inn, i den gitte rekkefølgen, i et på forhånd tomt binært søketre. Tegn treet. Skriv ut verdiene i preorden, inorden og postorden. Verdiene skal komme sortert i inorden. Hvis ikke, har du gjort en feil!

Vedlegget har et «skjelett» av klassen SBinTre - et binært søketre. Nodeklassen og treklassen skal ikke ha flere instansvariabler enn de som er satt opp. Noen av treets metoder er ferdigkodet og kan derfor brukes. Spesielt er metoden leggInn() kodet slik at treet ikke får noen like verdier. Hvis du skulle trenge, som hjelpemetoder, andre enn de som allerede er satt opp, må du kode dem.

 3B.   Lag metoden public boolean inneholder(T verdi). Den skal returnere true hvis verdi finnes i treet og returnere false ellers.

 3C.   Lag metoden public String omvendtPreString(). Den skal returnere en tegnstreng som inneholder verdiene i omvendt (eller motsatt) rekkefølge av preorden. Flg. eksempel som bruker verdiene fra Oppgave 3A, viser hvordan den skal virke:

  int[] a = {15, 18, 4, 8, 17, 5, 2, 12, 25, 9, 20, 13};
  SBinTre<Integer> tre = new SBinTre<>(Comparator.naturalOrder());
  for (int verdi : a) tre.leggInn(verdi);

  System.out.println(tre.omvendtPreString());
  // Utskrift: [20, 25, 17, 18, 13, 9, 12, 5, 8, 2, 4, 15]

 3D.   En gren består av nodene fra og med rotnoden ned til og med en bladnode. Den korteste grenen er den som har færrest noder. Hvis det er flere som er kortest, sier vi at den korteste er den av dem som ligger lengst til venstre. Den lengste er den som har flest noder. Hvis det er flere som er lengst, sier vi at den lengste er den som ligger lengst til høyre.

1. Sett opp verdiene i den korteste og lengste grenen i det treet du tegnet i Oppgave 3A.
2. Lag metoden public String lengstGren(). Den skal returnere en tegnstreng som inneholder verdiene i den lengste grenen i treet (med [ , ] , komma og mellomrom).
3. Lag metoden public String kortestGren(). Den skal returnere en tegnstreng som inneholder verdiene i den korteste grenen i treet (med [ , ] , komma og mellomrom).

Obs: Lengden på en grens tegnstreng avgjøres av hvor "lange" nodeverdiene er.

Vedlegg

  /////// ukjentMetode ////////////////////
  public static <T> void ukjentMetode(T[] a, Comparator<? super T> c)
  {
    for (int i = 0; i < a.length - 1; i++)
    {
      int m = i; T mverdi = a[i];

      for (int j = i + 1; j < a.length; j++)
      {
        if (c.compare(a[j], mverdi) < 0)
        {
          m = j; mverdi = a[j];
        }
      }

      a[m] = a[i]; a[i] = mverdi;

      System.out.println(Arrays.toString(a));
    }
  }

/////// class LenketKø ////////////////////

import java.util.*;

public class LenketKø<T> implements Kø<T>
{
  private static final class Node<T>  // en indre nodeklasse
  {
    private T verdi;        // nodens verdi
    private Node<T> neste;  // peker til neste node

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

  } // class Node

  private Node<T> fra;     // den første i køen
  private Node<T> til;     // en etter den siste i køen
  private int antall;      // antall i køen

  public LenketKø()        // standardkonstruktør
  {
    // skal kodes
  }

  public void leggInn(T verdi)
  {
    // skal kodes
  }

  public T kikk()
  {
    // skal kodes
  }

  public T taUt()
  {
    // skal kodes
  }

  public int antall()
  {
    return antall;
  }

  public boolean tom()
  {
    return fra == til;
  }

  public String toString()
  {
    // skal kodes
  }

  public void nullstill()  // tar vare på 8 av nodene
  {
    Node<T> p = fra;
    for (int i = 1; i < 8; i++)
    {
      p.verdi = null;
      p = p.neste;
    }
    p.verdi = null;
    til = p.neste = fra;
    antall = 0;
  }

} // class LenketKø

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

import java.util.Comparator;
import hjelpeklasser.Oppgave;

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 Node(T verdi, Node<T> v, Node<T> h)  // konstruktør
    {
      this.verdi = verdi;
      venstre = v; høyre = h;
    }

    private Node(T verdi)  // konstruktør
    {
      this(verdi, null, 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; comp = c;
  }

  public int antall()        // antall verdier i treet
  {
    return antall;
  }

  public boolean tom()       // er treet tomt?
  {
    return antall == 0;
  }

  public boolean leggInn(T verdi)
  {
    if (verdi == null) return false;   // nullverdier ikke tillatt

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

    while (p != null)       // fortsetter til p er ute av treet
    {
      q = p;                                 // q er forelder til p
      cmp = comp.compare(verdi,p.verdi);     // bruker komparatoren
      if (cmp < 0) p = p.venstre;            // går til venstre
      else if (cmp > 0) p = p.høyre;         // går til høyre
      else return false;                     // finnes fra før
    }

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

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

    antall++;                                // én verdi mer i treet
    return true;                             // vellykket innlegging
  }

  public boolean inneholder(T verdi)
  {
    // skal kodes
  }

  // Oppgave er funksjonsgrensesnittet fra undervisningen
  public void preorden(Oppgave<? super T> oppgave)
  {
    if (!tom()) preorden(rot, oppgave);
  }

  private static <T> void preorden(Node<T> p, Oppgave<? super T> oppgave)
  {
    oppgave.utførOppgave(p.verdi);
    if (p.venstre != null) preorden(p.venstre, oppgave);
    if (p.høyre != null) preorden(p.høyre, oppgave);
  }

  public String omvendtPreString()
  {
    // skal kodes
  }

  public String kortestGren()
  {
    // skal kodes
  }

  public String lengstGren()
  {
    // skal kodes
  }

} // SBinTre