Vordiplom Praktische Informatik - Kurs 1663 Datenstrukturen Version 97

Vordiplom Praktische Informatik - Kurs 1663 Datenstrukturen

Prüfer:	Prof. Dr. Güting
Beisitzer:	Dr. Schneider
Prüfling:	Gast Fischer
Datum:	31.10.2001 – 11:00 Uhr
Dauer:	25 min.

Dictionaries :

Operationen (delete, insert, member)
Datentyp (Mengen)
Datenstrukturen
- Einfache Datenstrukturen
  - Geordnete Listen, Ungeordnete Listen, Bitvektor
Was ist denn ein Bitvektor ? (boolecher Array)
- Laufzeiten ? (O(1) für sämtliche Operationen)
  - Also optimal ? (Nein, denn Platzbedarf = O(N) wobei N die Länge des Arrays ist also die Darstellung des Universums und nicht der betrachteten Menge)
Jetzt zu den etwas ausgefeilteren Datestrukturen. Welche kennen Sie ? (Binäre Suchbäume, AVL-Bäume, B-Bäume, Hashing)
Nehmen wir mal binäre Suchbäume. Was ist denn das ? (Definition - Skript)
- Wie ist das denn mit der Höhe ? (O(n²) – worst case, O(logn) – best case )
  - Warum denn gerade O(logn) ? (Best case – Baum minimaler Höhe, beim Übergang zum jeweils nächsten Level wird die Höhe des Teilbaums halbiert und log₂ n ist gerade die Anzahl von Halbierungen einer Zahl bis man auf 1 kommt.).
  - Und wie kann man denn den worst-case verhindern ? (AVL-Bäume – Definition – Strukturinvariante – Balancieren)
  - Zeichnen Sie mir doch mal eine Rebalancierung auf!
  - Wie kann man denn beweisen dass der rebalancierte Baum wieder ein AVL-Baum ist ? (Hier kam ich nach einigem Zögern darauf, dass man diesen Beweis analog zu dem Richtigkeitsbeweis beim Einfügen und Löschen eines Knotens in einem Heap führen kann. Dies war dann auch das, was Professor Güting hören wollte.

So, dann kommen wir doch mal zu einem ganz anderen Thema,

Graphen:

Was ist denn ein Graph? (Definition aus dem Skript)
Wie kann man denn einen Graphen repräsentieren ? (Adjazenzmatrix, Adjazenzliste)
- Adjazenzmatrix, was ist denn das ? (Definition aus dem Skript)
  - Laufzeiten und Speicherplatz ? (feststellen ob eine Kante existiert – O(1), Speicherplatz - O(n²), Ausgabe aller Nachfolger eines Knotens – O(n).)
    - Wie kann man diese Laufzeit herleiten? (Man muss eine ganze Zeile der Matrix durchlaufen).

Nun zu den Adjazenzlisten. Wie sind diese aufgebaut? (Für jeden Knoten eine verkettete Liste mit seinen Nachfolgern, die Listen werden über ein Array mit Listenzeigern erreicht)
- Laufzeit? (O(k) wenn k die Länge der Liste ist)
  - Das heisst, wenn die Liste leer ist, haben wir eine Laufzeit von O(0)? (Nein , eigentlich ist die Laufzeit ja O(1+k) da man konstante Zeit braucht für den Zugriff auf die Liste.)

Fazit: Ich kann nur das bestätigen was in vorigen Prüfungsprotokollen über Professor Güting gesagt wurde. Ein sehr netter Mensch, der versucht beim Prüfling von Beginn an die Nervosität auf ein Minimum zu reduzieren. Auch ist er daran interessiert, dass der Prüfling die Prüfung in einem gewissen Sinne mitgestaltet, denn er hat keine vorbereiteten Fragen, sondern fragt dort weiter wo der Prüfling mit seinen Ausführungen aufgehört hat. Er hat die Tendenz nur einige Schwerpunktthemen zu prüfen (bei mir Dictionnaries und Graphen), diese dann aber bis in die Details. Er legt grossen Wert auf Laufzeit- und Platzbedarfbestimmung. Professor Güting ist meines Erachtens als Prüfer uneingeschränkt zu empfehlen.