Prüfungsprotokoll zur Prüfung Praktische Informatik

Kurs : 01663 Datenstrukturen

Datum : 09.12.98 11 Uhr

Prüfer : Prof. Dr. Güting

Note : 1,3

 

 

 

1 . Allgemeine Begriffe : Datenstruktur, Algebra, ADT, Datenstruktur. In diesem Zusammenhang wurde dann eben auch Semantik und Signatur abgefragt.
Algebra : Definition des Datentyps mit Hilfe mathematischer Funktionen. ADT : Definition mit Hilfe von Gesetzen; Axiomen und Eigenschaften der Operationen. Datenstruktur = Menge von Objekttypen und Operationen auf diese. Hier kam dann die Frage : was sind diese Objekttypen : atomare Strukturen oder andere Datenstrukturen, die bereits definiert sind oder noch zu definieren sind. Gemeinsamkeit zwischen ADT und Algebra : Signatur. Was wird da definiert : Die benutzen Objekttypen sowie die Operationen mit Input und Output. Was steht in der Semantik : bei der Algebra werden den Objekttypen Trägermengen zugeordnet und den Operationen werden mathematische Funktionen zugeordnet, beim ADT werden die Operationen axiomatische beschrieben. Und was ist nun die Datenstruktur : die Implementierung des Datentyps auf algorithmischer Ebene. Was bedeutet das? Den Objekttypen werden Repräsentationen zugeordnet und die Operationen werden durch Algorithmen ersetzt.

 

2. Graphen : Was sind Graphen ? Definition! Grad eines Graphen, Eingangsgrad und Ausgangsgrad. Wie kann man diese darstellen? Adjazenzmatrix und Adjazenzliste. Platzbedarf O(n²) bzw. O(n+e). Welche Durchlaufarten gibt es für Graphen : Breitendurchlauf und Tiefendurchlauf. Wie funktionieren diese? Wie kann man diese realisieren : Breitendurchlauf mit Hilfe einer Queue, Tiefendurchlauf mit Hilfe eines rekursiven Algorithmus , Abbruchkriterium ein schon besuchter Knoten.

  1. B-Bäume : Definition Vielweg-Suchbaum und B-Baum. Was passiert beim Einfügen? Kann zu einem Overflow führen. Was tut man dann : Splitten. Was kann beim Löschen passieren : Underflow. Was nu : Merge oder Rebalancieren. Warum sind B-Bäume zum Suchen geeignet : Pfadlänge zu allen Blättern gleich O(log(m+1)n). Wie kommt man auf diese Länge? Minimal gefüllter Baum hat m Schlüssel in jedem Knoten und m+1 Nachfolger. Mit der Ungleichung
    N(h) <= n < N(h+1).

 

  1. Praktisches Problem : Was passiert beim Löschen eines Schlüsselelementes : da sagte ich nur: den linken Schlüssel aus dem Nachfolgerknoten nehmen und als neuen Schlüssel definieren. Das ist aber nicht immer ganz richtig : es muß heißen : der nächstgrößte Schlüssel. Dieser liegt dann wohl im Blatt. Diesen löscht man aus dem Blatt und schreibt ihn als neuen Schlüssel. Dann kann man die restlichen Operationen im Blatt machen.

 

 

 

 

Kommentar:

Also die Prüfung war soweit okay. Prof. Dr. Güting ist von Natur aus sehr ruhig, läßt sich Zeit, um die Fragen zu stellen und läßt dem Prüfling auch Zeit, sich die Antwort zu überlegen. Ich mußte zwischendurch mal sagen : "Oh, wie war das noch mal". Da hat er mich überlegen lassen und als ich dann immer noch nicht auf die Antwort kam, hat er mir ein bißchen nachgeholfen. Zur Bewertung sagte er, die Prüfung hätte im gut gefallen, in den Details happerte es bei mit wohl ein bißchen, aber war in Ordnung. Daher auch eine 1,3. Hätte ich persönlich nicht mehr mit gerechnet.