TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Mögliche Theoriefragen 2.Übungstest SS08

Theoriefragen der folgenden Tests:

20070111_UE-Test2.pdf (11. Jänner 2006/07):

• AVL-Bäume
• Hashing (DH, DH+VnB)
• Graphen (Pseudocode -> rekursiver Algorithmus)

20070606-Test2.pdf (6. Juni 2007):

• AVL-Bäume
• Hashtabellen (Lineares Sondieren)
• Graphen (Pseudocode)

20080111-Test2.pdf (11. Jänner 2008):

• Lineare Listen (Pseudocode)
• Hash-Verfahren (DH+VnB)
• Suchbäume (Binäre Suchbäume, AVL-Bäume, B-Baum)

Vorbereitung für 2. Übungstest SS08

• (4 Punkte) Welche Durchmusterungsreihenfolgen für binäre Suchbäume sind Ihnen bekannt? In welcher Reihenfolge werden dabei jeweils die Wurzel eines Baumes sowie deren linker/rechter Unterbaum besucht? Welche Durchmusterungsreihenfolge(n) führt bzw. führen zu einer aufsteigend sortierten Ausgabe der gespeicherten Schlüssel?

Inorder: linker Unterbaum, Wurzel, rechter Unterbaum (aufsteigend sortierte Ausgabe)

Preorder: Wurzel, linker Unterbaum, rechter Unterbaum

Postorder: linker Unterbaum, rechter Unterbaum, Wurzel

• (3 Punkte) Wie viele Schlüssel kann ein B-Baum der Ordnung 3 und Höhe 2 minimal bzw. maximal in seinen Knoten – mit Ausnahme der Blätter (Vorsicht: Blätter zählen aber zur Höhe des Baumes) – aufnehmen? Begründen Sie Ihre Antwort kurz!

bla

• (3 Punkte) Welchen Nachteil haben Offene Hashverfahren gegenüber der Methode mit Verkettung der Uberläufer?

aus dem Skriptum: (1) Stößt man bei der Suche auf einen unbelegten Platz, so kann die Suche erfolglos abgebrochen werden.

(2) wegen (1) wird nicht wirklich entfernt, sondern nur als "entfernt" markiert. Beim Einfügen wird ein solches Element als nicht vorhanden, beim Suchen als "entfernt vorhanden" betrachtet.

(3)NACHTEIL: Wegen (2) ist die Suchzeit nicht mehr proportional zu (1+alpha), deshalb sollte man, sofern man viele Entfernungen vorhehmen muss, die Methode der Verkettung der Überläufer vorziehen.

• (3 Punkte) Erläutern Sie die Begriffe Primäre Häufungen und Sekundäre Häufungen.

bla

• (1 Punkt) Geben Sie die maximale Höhe eines AVL-Baums mit n Knoten in Theta-Notation in Abhängigkeit von n an.

bla

• (1 Punkt) Geben Sie die maximale Höhe eines natürlichen binären Suchbaums mit n Knoten in Theta-Notation in Abhängigkeit von n an.

bla

• (3 Punkte) Angenommen die Knoten eines AVL-Baumes speichern selbst keine Information uber die Balancierung. Welche Worst-Case-Laufzeit (in Theta-Notation in Abhängigkeit von n) hätte in diesem Fall ein Algorithmus zum Einfügen eines beliebigen Knotens in diesen AVL-Baum mit n Knoten? Begründen Sie Ihre Antwort in wenigen Sätzen!

bla

• (4 Punkte) Was ist die maximale Anzahl an Blättern pro Endknoten in einem B-Baum der Ordnung 3? Wie viele Kinder besitzt ein Knoten mit l Schlüsseln in einem B-Baum?

bla

• (2 Punkte) Sie möchten einen relativ dünnen Graphen (|E| ≈ |V |) möglichst kompakt speichern. Welche Datenstruktur würden Sie bevorzugen, die Adjazenzmatrix oder die Adjazenzlisten? Begründen Sie Ihre Antwort mit Hilfe einer Abschätzung in Theta-Notation (maximal 1-2 Sätze).

Adjazenzliste da sie weniger Speicherplatz braucht

• (2 Punkte) Würden Sie eine Adjazenzmatrix oder Adjazenzlisten einsetzen, wenn fast ausschließlich Anfragen der Art "Existiert eine Kante zwischen den Knoten i und j?” beantwortet werden müssen? Begründen Sie Ihre Antwort mit Hilfe einer Abschätzung in Theta-Notation (maximal 1-2 Sätze)

Adjazenzmatrix weil dafür ein Aufruf genügt anstatt in der Adjazenzliste nach dem Nachbarknoten zu suchen.

• (4 Punkte) Was ist die maximale Anzahl an Blättern pro Endknoten in einem B-Baum der Ordnung 4? Wie viele Kinder besitzt ein Knoten mit l Schlüsseln in einem B-Baum?

bla

• (2 Punkte) Ist beim Einfügen mittels Double Hashing in eine Hashtabelle die Anzahl der auftretenden Kollisionen abhängig von der Reihenfolge der eingefügten Datensätze? Begründen Sie Ihre Antwort (gegebenfalls mit einem kurzen Beispiel).

Ja! Die Reihenfolge hat Einfluss auf die Anzahl der Kollisionen. Bsp(Danke Yrucrem): Elemente: <a, b, c> Hashfunktionen: h1(a) = h1(b) = 1, h1(c) = 2, h2(a) = h2(c) = 1, h2(b) = 2

Angaben ohne Gewähr!