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.   Alle klasser har metoden hashCode(). I klassen String returnerer den et heltall basert på strengens tegn. Lag metoden public static int hash(String a, String b). Den skal returnere et heltall basert på a og b. Du skal først konstruere en tegnstreng c (en String) der annethvert tegn kommer fra a og annethvert tegn fra b. Hvis f.eks. a = "Kari" og b = "Petter" skal c bli "KPaertiter" og hvis a = "Jorunn" og b = "Ola" skal c bli "JOolraunn". Metoden hash skal returnere hashCode()- verdien til c.

 1B.   Vi sier at et ord er inneholdt i et annet ord hvis hver bokstav i det første ordet forekommer like mange ganger i det andre ordet som i det første, men ikke nødvendigvis i samme rekkefølge. F.eks. er ABBA inneholdt i både BARAB, BARBARER og RABARBRA. ABBA har to A-er og to B-er og det har også de tre andre. Men ABBA er hverken inneholdt i BARBERER eller i AKROBAT. BARBERER har to B-er, men kun én A og AKROBAT har to A-er, men kun én B. Lag metoden public static boolean inneholdti(char[] a, char[] b) der a og b er «ord». Du kan ta som gitt at char-tabellene a og b kun har store bokstaver. Metoden skal returnere true hvis a er inneholdt i b og false ellers. Vi tenker oss her at et «ord» rett og slett er en oppramsing av bokstaver. Lag metoden så effektiv som mulig.

Flg. kode viser hvordan metoden skal virke:

  char[] a = "ABBA".toCharArray();
  char[] b = "BARBARER".toCharArray();
  char[] c = "BARBERER".toCharArray();

  System.out.println(inneholdti(a, b));  // Utskrift: true
  System.out.println(inneholdti(a, c));  // Utskrift: false

Oppgave 2

I vedlegget står klassen StakkPrioritetsKø som bruker to stakker som intern datastruktur. Metoden taUt() tar alltid ut den minste verdien. Det styres av en komparator.

 2A.   Anta at klassen StakkPrioritetsKø er ferdigkodet. Hva blir utskriften:

  Stakk<String> A = new TabellStakk<>(), B = new LenketStakk<>();
  Comparator<String> c = Komparator.naturlig();

  PrioritetsKø<String> kø = new StakkPrioritetsKø<>(A, B, c);

  String[] navntabell = {"Per","Kari","Ole","Berit","Arne"};
  for (String navn : navntabell) kø.leggInn(navn);

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

 2B.   I klassen StakkPrioritesKø skal alle verdiene ligge i sortert rekkefølge på stakken A, dvs. den minste skal ligge øverst, osv. Lag kode for kikk() og taUt(). Hvis køen er tom, skal begge kaste en NoSuchElementException med en passelig tekst. Metoden kikk() skal returnere, men ikke fjerne, den minste verdien fra køen. Metoden taUt() skal ta ut, dvs. returnere (og fjerne fra køen) den minste verdien. Lag så metoden leggInn(T verdi). Den må sørge for at stakken A holdes sortert. Stakken B kan brukes som hjelpestakk. Det skal ikke brukes andre hjelpestrukturer enn den. Hvilken orden vil de tre metodene få?

Oppgave 3

 3A.   Gitt tallene: 15, 5, 13, 25, 18, 3, 9, 11, 2, 8, 27, 10, 20. 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. Skriv også opp, for hvert nivå, hvor mange noder det er på det nivået.

Vedlegget har et «skjelett» av klassen SBinTre - et binært søketre. Der har hver node også en variabel forelder som peker til nodens forelder. Rotnodens forelder er null. Ved hjelp av denne pekeren er det mulig å gå oppover i treet. Metoden public boolean leggInn(T verdi) er ferdigkodet. Den setter rett verdi på variabelen forelder i hver ny node.

 3B.   En node i treet ligger på et bestemt nivå. Rotnoden ligger på nivå 0. Barna til rotnoden på nivå 1, osv. Lag metoden private static <T> int nivå(Node<T> p). Den skal returnere nivået til noden p. Det kan tas som gitt at p ikke er null.

 3C.   Lag metoden private static <T> Node<T> nestePreorden(Node<T> p). Den skal returnere den noden som kommer rett etter p i preorden. Hvis p er den siste i preorden, skal metoden returnere null. Det kan tas som gitt at p ikke er null. I denne oppgaven skal du, når det er nødvendig å gå oppover i treet, bruke at hver node har en peker til forelderen.

 3D.   Hvert nivå i et binærtre har et antall noder. Bredden til et binærtre er lik antallet noder på det nivået som har flest noder. Hva er bredden til treet du tegnet i punkt 3A? Lag metoden public int bredde(). Den skal returnere treets bredde. Et tomt tre har bredde 0.

Oppgave 4

 4A.   Nederst i vedlegget står metoden parter(). Hva blir utskriften fra flg. programbit:

  int[] a = {2, 9, 12, 10, 11, 4, 15, 1, 5, 13, 7, 8, 6, 3, 14};
  int p = Tabell.parter(a, 0, a.length - 1, 8);

  System.out.println(p + "  " + Arrays.toString(a));

 4B.   I vedlegget står hovedtrekkene i algoritmen for å legge inn verdier i et rød-svart binærtre. Gitt verdiene 10, 7, 4, 13, 12, 6, 8, 9, 11. Legg dem inn, i den gitte rekkefølgen, i et på forhånd tomt rød-svart binærtre. Tegn treet når de fire første verdiene er lagt inn, så når syv verdier er lagt inn og til slutt når alle verdiene er lagt inn. Skriv en S ved siden av hver svart node og en R ved siden av hver rød node (eller bruk fargepenn hvis du har det).

Vedlegg

Algoritme for å legge inn verdier i et rød-svart binærtre:

1. Treets første verdi legges i en svart rotnode.
2. Generelt legges en ny verdi i en rød node på rett sortert plass i treet. La den hete X.
3. Hvis forelder F til X er svart, stopper vi. Hvis F er rød, må F ha en svart forelder B (besteforelder til X) og F et søsken S (der S kan være en svart nullnode).
4. Hvis F sitt søsken S er svart, må det utføres en enkel eller en dobbel rotasjon (høyre eller venstre) og deretter et fargeskifte (Enkel rotasjon: F til svart og B til rød − Dobbel rotasjon: X til svart og B til rød). Dermed kan vi stoppe.
5. Hvis F sitt søsken S er rød, må det utføres et fargeskifte (F og S til svart og B til rød). Hvis B er roten, settes den tilbake til svart og vi kan stoppe. Hvis ikke, omdøper vi B til X og går tilbake til pkt. 3.

///////// klassen StakkPrioritetsKø ////////////////////////////

public class StakkPrioritetsKø<T> implements PrioritetsKø<T>
{
  private Stakk<T> A, B;
  private final Comparator<? super T> c;

  public StakkPrioritetsKø(Stakk<T> A, Stakk<T> B, Comparator<? super T> c)
  {
    this.A = A; this.B = B; this.c = c;
  }

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

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

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

  public int antall() { return A.antall(); }

  public boolean tom() { return A.tom(); }

  public void nullstill() { A.nullstill(); }

} // StakkPrioritetsKø

///////// 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 Node<T> forelder;        // nodens forelder

    private Node(T verdi, Node<T> v, Node<T> h, Node<T> v)
    {
      this.verdi = verdi;
      venstre = v;
      høyre = h;
      forelder = f;
    }

    private Node(T verdi)
    {
      this(verdi, null, null, null);
    }

  } // 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, null, null, q);

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

    antall++;
    return true;
  }

  private static <T> int nivå(Node<T> p)
  {
    // mangler kode - skal kodes
  }

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

  public int bredde()
  {
    // mangler kode - skal kodes
  }
} // SBinTre


///////// metoden parter ////////////////////////////

  public static int parter(int[] a, int v, int h, int skilleverdi)
  {
    while (v <= h && a[v] < skilleverdi) v++;   // h er stoppverdi for v
    while (v <= h && skilleverdi <= a[h]) h--;  // v er stoppverdi for h

    while (true)
    {
      if (v < h) bytt(a,v++,h--);          // bytter om a[v] og a[h]
      else  return v;                      // partisjoneringen er ferdig
      while (a[v] < skilleverdi) v++;      // flytter v mot høyre
      while (skilleverdi <= a[h]) h--;     // flytter h mot venstre
    }
  }