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 SS05

< Informatik 3
Version vom 22. Juli 2007, 22:54 Uhr von 212.202.170.193 (Diskussion) (4. Eichhornaufgabe: typo)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

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.