Prüfer: Prof. Dr. Schlageter

Datum: 26.06.2000, 15 min

Note: 1,0
 
 

• Sie sollen ein Unternehmen hinsichtlich des Einsatzes einer Datenstruktur zur Speicherung des Kundenstammes beraten. Welche Informationen benötigen Sie?

Information, ob fester oder dynamischer Kundenstamm, voraussichtliche Größe, ob eine Sortierung benötigt wird, ob hauptsächlich Such-Operationen benötigt werden.
• Wann sollte man Hashing einsetzen und warum?

Wenn möglichst wenig Update-Operationen zu erwarten sind und Daten v. A. gesucht werden sollen, wenn die voraussichtliche Größe des Kundenstammes bekannt ist, wenn nicht sortiert ausgegeben werden soll.
• Welches Problem kann auftreten?

Kollisionen, Primär- und Sekundärkollisionen -> Kollisionsbehandlung: lineares, quadratsiches Sondieren.
• Wo bringt quadratisches Sondieren eine Verbesserung und warum?
• Welche Datenstruktur kann man verwenden, wenn kein Hashing eingesetzt wird?

Binäre Suchbäume, AVL-Bäume, B-Bäume
• Wann werden B-Bäume eingesetzt und warum?

Bei sehr großen Datenmengen, weil mehrere Schlüssel in einem Knoten gespeichert werden.
• Wann und wie wächst ein B-Baum?

Overflow erklärt -> B-Baum wächst an der Wurzel.
• Wo wachsen Bäume normalerweise?

An den Blättern.
• Sortieralgorithmen Quicksort und Heapsort, wie unterscheiden sie sich?

Quicksort ist DAC-Algorithmus, Heapsort verfeinertes Auswählen.
Heapsort -> Heap wird aufgebaut, Minimum entnommen, Heap wiederhergestellt.
• Laufzeiten?

Average case bei Quicksort O(n log n), worst case O(n²) bei Entartung, wenn array geteilt wird in Folgen von 1 und n-1 Elementen.
Heapsort garantiert O(n log n) auch im worst case.