Aufgabe 1 (8+5 Punkte)

1. Schreiben sie ein Programm in PASCAL, das die Zahlen in einem File
   f: file of integer
   in umgekehrter Reihenfolge ausgibt. (Bemerkung: Das File ist groß, d.h. sie können den Fileinhalt nicht in den Hauptspeicher einlesen)
2. Bestimmen sie die Ordnung der Laufzeit ihres Programms im schlimmsten Fall.

Aufgabe 2 (4 Punkte)

Für die Schlüssefolge

A, B, C, D, E, F, G

konstruiere man einen AVL-Suchbaum (mit maximaler Höhe), dessen Knoten nur die Balancen 0 und +1 besitzen. Anschließend entferne man den Schlüssel A aus diesem AVL-Baume (bitte Zwischenschritte angeben).

Aufgabe 3 (2+2+2+2 Punkte)

Beantworten sie die folgenden Fragen und begründen sie ihre Antwort jeweils mit ein/zwei Sätzen. Ohne Begründung gibt es keine Punkte.

1. Wahr oder falsch? Mit einer einfach verketteten Liste kann man einen Stack nicht so realisieren, dass die Operationen push und pop in konstanter Zeit laufen.
2. Wahr oder falsch? Beim Löschen eines Elements v – wobei als Eingabe nur ein Zeiger auf v gegeben ist – in einer linearen Liste ist die Verwendung von doppelt verketteten Listen gegenüber der Verwendung von einfach verketteten Listen von Vorteil.
3. Wahr oder falsch? Das Maximum eines binären Suchbaums kann keinen linken Sohn haben.
4. Wahr oder falsch? Bei einem binären Suchbaum steht in der Wurzel immer der Median der Elemente, die in dem Baum gespeichert sind.

Aufgabe 4 (2+2+2+2 Punkte)

Welche Aussagen sind richtig, welche falsch? Es ist jeweils eine Begründung anzugeben.

1. 5 n log n = O(n)
2. 5n + 2n2+7n3 = O(n3 log n)
3. n * 2n = O(3n * log n)
4. 4n log n - 3n + 17 sqrt(n) = O(n log n)

Aufgabe 5 (8 Punkte)

Gegeben sei folgender Graph:

(… Graph ist noch zu migrieren … )

Bestimmen sie mit dem Algorithmus von Dijkstra alle kürzesten Wege von A zu allen anderen Knoten.

Aufgabe 6 (3+3+3 Punkte)

Verwenden sie das Master-Theorem zur Lösung der folgenden Rekursionsgleichungen. Geben sie dabei jeweils an, welcher Fall des Master-Theorems angewendet werden kann und weisen sie nach, dass die Voraussetzungen zur Anwendung dieses Falls erfüllt sind.

1. T(n) = 3 T(n/2)+n2
2. T(n) = 4 T(n/3)+n
3. T(n) = 8 T(n/2)+n3