Informatik 3/Gedächtnisprotokoll Klausur SS07
Inhaltsverzeichnis
1. Aufgabe: Multiple Choice
- ..
- ..
- Die Höhe eines binären Suchbaumes ist immer um 1 größer, als das Maximum der Höhen seiner Teilbäume.
- Für jedes endliche Optimierungsproblem kann man einen Backtrackingalgorithmus finden der dieses löst.
- Für jedes endliche Optimierungsproblem kann man einen Greedy-algorithmus finden der dieses löst.
HashTables
Hashtabelle der Größe 4.
- Hashfunktion: h(k) = k mod 4
- Kollisonsauflösung"double hashing" a(k) = k+2
Vier Werte mit Schlüsseln einfügen und Kollisionen zählen.
(A,5) (B,11) (C,9) (D,14)
A -> 1
B -> 3
C -> 1, 3, 1 , 3 .. (kann nicht eingefügt werden)
D -> 2
0 blieb leer.
Ist die Anzahl der Kollisionen bei double hashing abhängig von der Reihenfolge in der die Elemente eingefügt werden? Begründung, ggf. Beispiel.
AVL-Bäume
- Einfügen in AVL-Baum
- Einfügen in AVL-Baum
- Löschen aus AVL-Baum
Rot-Schwaz-Bäume
- Einfügen in RS-Baum
- Java-Programm schreiben für Höhenberechnung eines Rot-Schwarz-Baumes getBlackHeight(Node root)
- Rot-Schwarz-Baum als gültig vorausgesetzt.
- Vorgegebene Implementation:
- isRed(Node node);
- isBlack(Node node);
- class Node{ int color; Node left; Node right; }
B-Baum
- Element in B-Baum einfügen.
Aufgabe 4: Graphen
Hab ich, trag ich gleich ein TomyLobo
Aufgabe 5: Übungsorganisation
Hab ich, trag ich gleich ein TomyLobo
Aufgabe 6: Dynamisches Programmieren
Hab ich, trag ich gleich ein TomyLobo
Aufgabe 7: Geld wechseln
Hab ich, trag ich gleich ein TomyLobo