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
1A.
Gitt tabellen int[] a = {1,2,3,6,7,12,13,26,27}. Hva er tabellens lengde? Hva er tabellens
midtverdi og hvilken posisjon/indeks har midtverdien? Avgjør så
hva utskriften i flg. programbit blir. (Koden for binærsøk står i vedlegget.)
Begrunn svarene dine!
int[] a = {1,2,3,6,7,12,13,26,27}; int i = binærsøk(a,13); int j = binærsøk(a,14); System.out.println(i + " " + j);
1B.
I et binærtre har hver node en posisjon gitt som et heltall (posisjonstall). Rotnoden har posisjon 1. Videre
gjelder for enhver node at hvis den har posisjon k, så vil et eventuelt venstre barn ha posisjon 2k
og et eventuelt høyre barn posisjon 2k + 1. Mengden av posisjonstall kalles treets
posisjonstallmengde. Mengden av posisjonstall som hører til bladnoder kalles treets
bladnodeposisjonstallmengde.
|
| Figur 1 |
1. Lag en kopi av treet i Figur 1 i din besvarelse og skriv ved siden av hver node posisjonstallet til noden. Sett opp posisjonstallmengden. Sett også opp bladnodeposisjonstallmengden.
2. Tegn det treet som har flg. posisjonstallmengde: {1,2,3,6,7,12,13,26,27}. Sett opp bladnodeposisjonstallmengden.
1C.
Lag metoden public static int[] bladnodeposisjoner(int[] pos). Det er gitt at parametertabellen
pos utgjør posisjonstallmengden til et binærtre. Det tas som gitt at den ikke er tom og
at den er sortert stigende.
Metoden skal returnere en tabell som utgjør bladnodeposisjonstallmengden.
Hvilken effektivitet (orden) vil metoden din få? Flg. eksempel viser hvordan den skal virke:
int[] pos = {1,2,3,6,7,12,13,26,27}; int[] a = bladnodeposisjoner(pos); System.out.println(Arrays.toString(a)); // Utskrift: [2, 7, 12, 26, 27]
Oppgave 2
2A.
Hva blir utskriften fra flg. programbit? Grensesnittet Stakk står i
vedlegget. Gi en begrunnelse for svaret ditt!
String[] navn = {"Per",Kari","Ole","Elin"};
Stakk<String> A = new TabellStakk<>();
Stakk<String> B = new LenketStakk<>();
for (String s : navn) A.leggInn(s);
while (!A.tom()) B.leggInn(A.taUt());
while (!B.tom()) System.out.print(B.taUt() + " ");
2B.
En melding inneholder bokstavene A, B, C, D, E og F med frekvenser på
henholdsvis 10, 6, 1, 8, 20 og 11. Lag det Huffmantreet som denne
frekvensfordelingen gir. Sett opp bitkodene for tegnene.
Dekomprimer sekvensen 10010010111.
Oppgave 3
3A.
Gitt følgende heltall: 4, 23, 11, 3, 25, 8, 10, 20, 14, 6, 15, 21. Legg dem inn,
i den gitte rekkefølgen, i et på forhånd tomt binært søketre av vanlig type.
Tegn treet. Hvor mange nivåer har treet? Skriv opp antallet noder på
hvert av nivåene. Husk at rotnoden er på nivå 0. Fjern så verdien 11 fra treet.
Tegn treet etter at 11 er fjernet.
Vedlegget inneholder et «skjelett» for klassen SBinTre - et binært søketre av vanlig type.
Den private klassen Node har tre instansvariabler - nodens verdi og pekere til venstre
og høyre barn. Det skal ikke legges inn flere variabler i denne klassen. Klassen SBinTre
har fire instansvariabler - en rotpeker, antall, høyde og en komparator.
Variabelen høyde skal inneholde høyden til treet.
Det skal ikke legges inn flere variabler i klassen.
3B.
Lag metoden (se vedlegget) public int høyde().
Den skal returnere treets høyde. Et tomt tre har høyde lik -1. Du kan anta
at variablen høyde inneholder treets høyde.
3C.
I vedlegget er metoden public void leggInn(T verdi) delvis ferdigkodet.
Den legger inn en verdi på rett plass i treet og oppdaterer variabelen
antall. Men når treet får en ny verdi vil treets høyde kunne bli
større enn den var. I så fall må variabelen høyde oppdateres.
Forklar hvordan dette kan løses og
legg så inn den ekstra koden som trengs i metoden
public void leggInn(T verdi) slik at variabelen høyde
får rett verdi etter innleggingen. Lag koden slik at oppdateringen skjer på
en mest mulig effektiv måte.
3D.
Lag metoden (se vedlegget) public T mindre(T verdi). Den skal returnere den siste av de verdiene
i treet som er mindre enn verdi, dvs. den siste av de som kommer foran
verdi i inorden. Parameterverdien verdi kan, men behøver ikke
ligge i treet. Hvis treet er tomt eller det ikke finnes noen verdier i treet som er mindre
enn verdi, returneres null. Forklar hvordan du har tenkt at koden din skal fungere.
Flg. eksempel viser hvordan metoden skal virke:
int[] a = {4,23,11,3,25,8,10,20,14,6,15,21}; SBinTre<Integer> tre = new SBinTre(Komparator.naturlig()); for (int k : a) tre.leggInn(k); // bygger treet System.out.println(tre.mindre(30)); // Utskrift: 25 System.out.println(tre.mindre(23)); // Utskrift: 21 System.out.println(tre.mindre(9)); // Utskrift: 8 System.out.println(tre.mindre(3)); // Utskrift: null
3E.
Lag metoden (se vedlegget) public String nivåVerdier(int nivå).
Den skal returnere en tegnstreng som inneholder (i sortert rekkefølge) de verdiene som ligger på
nivået gitt av parameterverdien nivå. Hvis nivå
ikke finnes i treet, kastes et passelig unntak.
Flg. eksempel viser hvordan den skal virke og hvordan tegnstrengen skal se ut:
int[] a = {4,23,11,3,25,8,10,20,14,6,15,21}; SBinTre<Integer> tre = new SBinTre(Komparator.naturlig()); for (int k : a) tre.leggInn(k); // bygger treet String s = tre.nivåVerdier(1); // verdiene på nivå 1 String t = tre.nivåVerdier(4); // verdiene på nivå 4 System.out.println(s + " " + t); // Utskrift: [3, 23] [6, 10, 14, 21]
Vedlegg
public static int binærsøk(int[] a, int verdi) { int v = 0, h = a.length - 1; while (v <= h) { int m = (v + h)/2; int midtverdi = a[m]; if (verdi > midtverdi) v = m + 1; else if (verdi < midtverdi) h = m - 1; else return m; } return -(v + 1); } 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 } // ------------------------------------------------------ public class SBinTre<T> // et standard 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; } } // class Node private Node<T> rot; // peker til rotnoden private int antall; // antall noder private int høyde; // treets høyde 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 høyde = -1; // et tomt tre har høyde lik -1 comp = c; } public int antall() { return antall; } public int høyde() { // kode mangler - skal lages } 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; int cmp = 0; while (p != null) { q = p; cmp = comp.compare(verdi, p.verdi); if (cmp < 0) p = p.venstre; else p = 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++; } public T mindre(T verdi) { // kode mangler - skal lages } public String nivåVerdier(int nivå) { // kode mangler - skal lages } } // class SBinTre