Sitzung: Jeden Freitag in der Vorlesungszeit ab 16 Uhr c. t. im MAR 0.005. In der vorlesungsfreien Zeit unregelmäßig (Jemensch da?). Macht mit!

Informatik 3/Gedächtnisprotokoll Klausur SS07

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

a) Baue eine Adjazenzmatrix zu folgendem Graphen: Info3-ss2007-4a.png


b) Dijkstra (Graph folgt)

c) Definiere (formal oder als Text) einen aufspannenden Baum.

d) Führe union(D,F) auf folgender, als Wald realisierter disjunkter Menge aus: (Graph folgt)

e) Erstelle den Restflussgraphen zu folgendem Flussgraphen: (Graph folgt)

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