Prüfungsverlauf:

• Welche, möglichst einfach zu implementierende, Datenstruktur würden Sie wählen, wenn Sie Objekte einfügen, löschen und suchen wollen? ungeordnete Liste, geordnete Liste im Array (mit Aufwandsangaben für Einfügen usw.)
• Was wäre die nächste Stufe (bezogen auf den Programmieraufwand)? Bäume (Def. Binärer Suchbaum), Hashing (auf Hashing wurde nicht eingegangen)

• Fügen Sie diese Zahlen in einen binären Suchbaum ein. Es entstand ein fast zur Liste degenerierter Baum.
• Wie ist die Höhe im best-, worst-, und average case? worst case O(n), sonst O(log n).
• Was kann man gegen den worst case tun? balancieren (z.B.: AVL-Baum, B-Baum)
• Definieren Sie den AVL-Baum (mit Erläuterung der Rotation und Doppelrotation)
• Wie sieht es mit der Höhe im AVL-Baum aus? (Wie wird sie hergeleitet?) max. 44 % höher als ein vollständig ausgeglichener Baum; Herleitung über Fibanacci-Zahlen.
• Warum benutzt man bei externen Strukturen keine AVL-Bäume, so daß jeweils ein Teilbaum auf einer Seite ist? beim balancieren (umhängen von Teilbäumen) entstehen hohe Zugriffskosten
• Erklären Sie den B-Baum (kurz)

• Kennen Sie einen Algorithmus, der die günstigste Verbindung von einem Knoten zu allen Anderen ermittelt? Dijkstra
• Erklären Sie an diesem Graphen den Algorithmus von Dijkstra und wie ist die Laufzeit? Ich habe es mit den Farben, analog zur Kurseinheit, erklärt. Ich denke jedoch eine "technische" Erklärung wäre Prof. Klein lieber gewesen (priority queues usw.)
• Gibt es eine untere Schranke für Sortierverfahren und wie wird sie hergeleitet ? W(n log n), Herleitung über die Höhe eines Entscheidungsbaum mit n! Blättern.
• Stelle Sie ein Sortierverfahren mit O(n log n) im worst case vor. Ich wählte mergesort.
• Was ist der Unterschied zwischen mergesort und quicksort?
• Wie ist es mit dem worst case?

• Wie könnte man die Schnittpunkte diese Elemente herausfinden? Alle Linien (jede mit jeder) prüfen O(n²), oder mittels "plane sweep".
• Erklären Sie plane sweep anhand dieses Beispiel?
• Welche Laufzeit hat dieser Algorithmus?
• Wie kann man die sweep-event-Stuktur und die status-line implementieren ? heap und Binären Suchbaum.

Allgemeiner Eindruck:

Prof. Klein ist ein sehr angenehmer und sympathischer Prüfer. Die Benotung ist ausgesprochen fair. Man sollte sich gut auf Bäume, Graphen Algorithmen (Dijkstra) und Geometrische Algorithmen (plane sweep) vorbereiten, denn einige Fragen gehen tief.

Ich kann Herrn Prof. Klein als Prüfer sehr empfehlen, und wünsche allen, die diese Prüfung noch vor sich haben, viel Erfolg.