Informatik 3/Gedächtnisprotokoll Klausur SS05

Dies ist ein Gedächtnisprotokoll von der Klausur vom 20. Juli 2005.

1. Aufgabe: Multiple Choice (4 mal wahr/falsch)

• Eine perfekte Skipliste hat immer Höhe O(log n).
• Ein binärer Baum hat immer Höhe O(log n).
• Ein AVL-Baum, in den 2^n - 1 Knoten eingefügt wurden, ist immer vollständig. (Vorsicht!)
• Noch eine Frage

2. AVL-Baeume.

• Mit wievielen Knoten kann ein AVL-Baum die Schicht 2 vollständig haben?
• Wieviele Knoten muss man in einen AVL-Baum einfuegen, sodass er garantiert vollständig ist?

• Löschen eines Knotens in einem max. unausgewogenen Baum (eine Doppel, eine Einzelrotation).

• Simulation Prim.

3. Rot-Schwarz-Baeume

• Einfügen eines Knotens in einen RB-Baum mit 2 Rotationen (4 Knoten Ausgangsgröße).
• Welche Pfadlänge hat der kürzeste Pfad Wurzel -> Blatt in einem Baum der Höhe 7 minimal?

4. Eichhornaufgabe

• Gegeben ein "Netzwerk" (Matrix) von Bäumen, Darstellung als Graph mit Kantenbewertung.

• Implementierung eines Hashs mit Double Hashing: Konstruktoren & Klassen, Insert, Search.
• KW-Baum-Beschreibung ("Wie findet man aus dem Graphen die Wege mit geringstem Risiko. Welcher Algorithmus ist geeignet?)

5. Greedy

• n Mitarbeiter, n Bueros.

Gegeben:

• Kosten fuer "Weg" von Buero_x -> Buero_y = | x - y | (Indizes).
• Besuchsfrequenz eines Mitarbeiters i bei einem Mitarbeiter j: f(i, j)

Gesucht:

• Darstellung fuer Loesung
• Kostenberechnung fuer _einen_ Weg.
• Kostenberechnug fuer Mitarbeiter i (Summe aus (Distanzen mal Frequenzen))
• Kosten fuer alle Mitarbeiter.

• Geben Sie einen Algorithmus an, der die minimalen Kosten von einem Mitarbeiter zu allen anderen berechnet.

6. Aufgabe

Überlegen Sie sich eine (Verkettung von) Datenstrukturen, mit der man möglichst effizient:

• Einfuegen
• Suchen
• Loeschen
• Remove_oldest

machen kann, geben Sie O(x) Abschätzung an.