Gedächtnisprotokoll InfTech2 Klausur vom 21.07.14 ss14

Multiple-Choise-Fragen

(10 Fragen davon 2 Fragen aus Probeklausur)

• Was ist die Komplexizität der "binären Suche"
• minimale DNF bzw. KNF bilden:
  • KV-Tafeln
  • Binäre Wertetabellen
  • boolsche Axiome
  • Verfahren von Quine und McIrgendwas
• Welcher Spannbaum (Abbildungen) entspricht dem Graphen G (ist gegeben)

AVL-Baum

• Ein Element löschen und den neuen Baum zeichnen
• Ein Element hinzufügen und den neuen Baum zeichnen

• Nach Eingügen unausgegelichen Baum durch Rotation ausgleichen

  Schritte (Doppelrotation):

  • eine links Drehung
  • und eine rechts Drehung

Komplexizität

Code-Schnippsel war gegeben(ungefähr):

<?> comp(int n, int p); // besitzt die Komplexizität 2  

<?> func(int n, int p){
    [...]
    comp(n,p);
    for(int i = 0, i < n, i++){
        [...]
        if(n%p == 0){
            while([...]){
                [...]
                k=n;
                comp(n,p);
                [...]
                k = k - 2;
            }
        }
    }
}

• mögliche Werte für n und p für den worst case
• mögliche Werte für p für den Best-Case
• Was ist die Komplexizität? (Gleichungen aufstellen für beide Fälle)
• Was ist die Komplexizitätsklasse? (Klasse aufschreiben)

Handsimulationen

Quicksort

• Handsimulation des Quicksort-Algos auf ein gegebens unsortiertes Zahlen-Array
• Komplexität des Quicksort angeben (für best und für worst case)

KV-Tafel

• KV-Tafel für Funktion (DNF) erstellen
• DNF aus KV-Tafel ablesen

Java Programier Aufgaben

Packages/Interfaces welche benutzt werden sollen:

• Comparable
• Iterator

Binäre Baume

• Von einem gegebenen binären Baum die Knoten und ihre höhe Ausgeben

Heap-Sort

Klasse Heap und Hilfs-Methode heapify als Rumpf und im Text beschrieben gegben.

• buildHeap implementieren
• heapSort implementieren

verkette Liste

• add-Methode (addFirst()) implementieren (leere Liste muss beachtet werden)
• pop-Methode (popLast()) implementieren (Sonderfälle beachten!!)
• hoppLast-Methode implementieren

Iterator

vector T[] x soll iteriert werden(nur gerade Indizes).

• Der Iterator muss implemtiert werden(hasNext(), next()).
• Test Klasse schreiben (unter verwendung einer for-each-Schleife.

Beispiel:

for(Element e: x){
    System.out.println(e);
}

Letzte Änderung: 21.07.14 18:31:25 +02:00