Aufgabe 1 (2+2+2 Punkte)

1. Rekonstruieren sie auf folgenden inorder und postorder Durchläufen den binären Baum.
   • Inorder: F, A, D, E, K, H, B, I, G, J, L
   • Postorder: F, D, A, K, H, I, L, J, G, B, E
2. Können sie auch aus einem Preorder und Postorder Durchlauf einen binären Baum rekonstruieren? Begründung.
3. Gegeben sei ein binärer Baum. Welche Schlüsselfolge kann bei der Suche nach der 42 nicht auftreten?
   • 50, 25, 37, 43, 42
   • 5, 66, 21, 22, 67, 30
   • 53, 10, 15, 52, 24
   • 60, 49, 30, 34, 41, 46
   • 1, 100, 2, 3, 99, 42

Aufgabe 2 (5 Punkte)

Erweitern sie die Implementierung eines Stacks (Pascal) asu dem Skript, sodass bei einem „overflow“ das älteste Element aus dem Stack geköscht wird, damit das hinzugefügte Element auf den Stack passt.

Aufgabe 3 (? Punkte)

Gegeben sei ein B-Baum der Ordnung eins. Fügen sie zunächst den Schlüssel 17 ein. Löschen sie anschließend den Schlüssel 30.

(… B-Baum muss noch migriert werden …)

Aufgabe 4 (3+1+3 Punkte)

Gegeben sei ein Graph mit 9 Knoten und 10 Kanten. Mittels des Algorithmus von Kruskal ist der minimale Spannbaum zu bestimmen.

1. Schreiben sie der Reihe nach auf (die Kosten sind eindeutig)
2. Welches Gewicht hat der minimale Spannbaum?
3. Zeichnen sie den Wurzelgraph mit Hilfe des Union-Find-Algorithmus und Pfadkompression.

Aufgabe 5 (? Punkte)

Zeichnen sie den AVL-Baum zu den Knoten

7, 4, 3, 10, 6, 5, 2.

Aufgabe 6 (2+2+2+? Punkte)

1. Erläutern sie die Vorteile von Quicksort, Mergesort und Bucketsort.
2. Ist das Array A = {17, 15, 13, 10, 7, 9, 12, 11) ein Heap? Begründung!

Aufgabe 7 (8 Punkte)

Gegeben sei eine Codierung von natürlichen Zahlen in einem Binärcode, in dem jedoch keine aufeinanderfolgende Einsen (11) sind.

Daraus ergibt sich: 1, 10, 100, 101, 1000, …

Welche natürliche Zahl wird durch 100100001001000 dargestellt?