Aufgaben: Datenstrukturen, Rekursion und Effizienz

Auf einem anfangs leeren Stack werden nacheinander push(3), push(7), pop(), push(5), pop() ausgeführt.

1. a) Geben Sie nach jeder Operation den Inhalt des Stacks an.

1. b) Welches Element liefert das nächste pop()?

Eine Queue enthält (Kopf zuerst) 4, 9, 2.

1. a) Geben Sie den Zustand nach dequeue(), enqueue(6) an.

1. b) Vergleichen Sie kurz das Prinzip einer Queue (FIFO) mit dem eines Stacks (LIFO) und nennen Sie je ein Anwendungsbeispiel.

Gegeben ist die rekursive Methode

int f(int n){ if (n == 0) return 0; return n + f(n - 1); }

1. a) Berechnen Sie f(4).

1. b) Nennen Sie Abbruchbedingung und rekursiven Aufruf.

Die Zahlenfolge 8, 3, 10, 1, 6, 14 wird in dieser Reihenfolge in einen anfangs leeren binären Suchbaum eingefügt.

1. a) Zeichnen Sie den Baum (Beschreibung der Knoten mit linkem und rechtem Kind).

1. b) Geben Sie die In-order-, Pre-order- und Post-order-Ausgabe an.

1. c) Wie viele Vergleiche braucht die Suche nach 6?

Das Feld {2, 5, 8, 12, 16, 23, 38, 56} ist sortiert.

1. a) Führen Sie die binäre Suche nach 23 durch und geben Sie die verglichenen Elemente an.

1. b) Wie viele Vergleiche braucht die lineare Suche nach 56? Wie viele die binäre?

1. c) Begründen Sie, warum die binäre Suche bei $n = 1.024$ höchstens etwa 11 Vergleiche benötigt.

Das Feld {7, 3, 9, 1, 5} wird mit Selectionsort aufsteigend sortiert.

1. a) Geben Sie das Feld nach jedem Durchlauf der äußeren Schleife an.

1. b) Bestimmen Sie die Anzahl der Vergleiche für $n = 5$ und allgemein für $n$.

Gegeben ist

int g(int n){ if (n <= 1) return 1; return g(n - 1) + g(n - 2); }

1. a) Zeichnen Sie den Aufrufbaum für g(5) und bestimmen Sie die Anzahl der Aufrufe.

1. b) Erklären Sie, warum die Laufzeit exponentiell wächst, und schlagen Sie eine effizientere Lösung vor.

1. c) Vergleichen Sie den Speicherbedarf von rekursiver und iterativer Lösung.

Mergesort teilt ein Feld der Länge $n$ in zwei Hälften, sortiert sie rekursiv und mischt sie.

1. a) Führen Sie Mergesort für {6, 2, 9, 4, 1, 7, 3, 8} bis zum Ende aus und geben Sie die Teilungs- und Mischschritte an.

1. b) Begründen Sie, dass bei $n = 2^k$ etwa $k$ Ebenen mit je höchstens $n$ Vergleichen entstehen.

1. c) Vergleichen Sie für $n = 1.000.000$ die Größenordnung der Vergleiche mit Selectionsort ($\approx n^2/2$).

Ein Ausdruck mit Klammern (, ), [, ] soll auf korrekte Klammerung geprüft werden.

1. a) Beschreiben Sie einen Algorithmus mit einem Stack.

1. b) Führen Sie ihn für ([)] und ([()]) durch und begründen Sie die Ergebnisse.

1. c) Beschreiben Sie vier Testfälle zur systematischen Prüfung Ihrer Implementierung (leerer Ausdruck, nur schließende Klammer usw.).