Klausuraufgaben und Lernratschläge

In diesem Abschnitt finden Sie allgemeine Hinweise zur Klausurvorbereitung, typische Aufgabentypen und repräsentative Beispielaufgaben aus vorherigen Prüfungen. Diese Beispiele decken das gesamte Spektrum der in der Vorlesung behandelten Themen ab.

• 1. Allgemeine Lernratschläge
• 2. Anmerkungen zu den Beispielaufgaben
• 3. Anmerkungen zur Klausur
• 4. Big-O-Cheat-Sheet und Komplexitätsübersicht
• 5. Beispielaufgaben (Auswahl)
  • 5.1 Verständnisfragen
  • 5.2 Funktionsweise (Beispieldurchläufe)
  • 5.3 Java-Implementierung
  • 5.4 Komplexitätsanalyse
• Beispielaufgabensammlung (nach Aufgabentypen sortiert)
  • 5.1 Fragen nach Verständnis, Definitionen und Eigenschaften
  • 5.2 Funktionsweise (exemplarische Durchläufe)
  • 5.3 Java-Implementierung
  • 5.4 Komplexitätsanalyse

1. Allgemeine Lernratschläge

• Verwenden Sie die Lernhinweise aus den Vorlesungen
  Insbesondere in den ersten Vorlesungen wurden generelle Methoden und Tipps zum Lernen von Algorithmen und Datenstrukturen vorgestellt (z. B. wie man vorgeht, wenn man einen Algorithmus nicht sofort versteht, oder wie man Pseudocode in eigenen Worten skizziert).
• Nutzen Sie interaktive und visuelle Aufbereitungen
  Einige Algorithmen (z. B. Sortier- und Suchalgorithmen) lassen sich anhand visueller Simulationen sehr gut nachvollziehen.
  Links zu interaktiven Visualisierungen wurden im Kursverlauf bereitgestellt:
  • visalgo.net
  • bigocheatsheet.com

2. Anmerkungen zu den Beispielaufgaben

• Repräsentative Auswahl
  Die folgenden Beispielaufgaben sind repräsentativ für Fragen, wie sie in der Klausur gestellt werden könnten. Dabei sind spätere Vorlesungsthemen meist etwas stärker gewichtet als frühe.
• Veröffentlichte Lösungen
  Lösungen zu den Beispielaufgaben können im Repetitorium, über Moodle oder im Kursforum diskutiert werden. Üblicherweise ist es hilfreich, wenn Sie zuerst eigene Ansätze präsentieren – so lassen sich Verständnislücken am besten feststellen und beheben.

3. Anmerkungen zur Klausur

• Aufgabentypen
  Die Klausurfragen zielen auf verschiedene Kompetenzen ab:
  1. Verständnis- und Definitionsfragen
     • z. B. Multiple-Choice oder Freitext-Fragen zu Begriffen wie “Komplexität”, “ADT”, “Binärbaum”, “Totalordnung” etc.
  2. Funktionsweise (Beispieldurchläufe)
     • z. B. die Ausführung eines Sortieralgorithmus an einer konkreten Eingabe nachvollziehen (Quicksort, Heapsort, AVL-Operationen).
  3. Implementierungen
     • z. B. Java-Code für bestimmte Datenstruktur-Operationen (Stack, Queue, Binärbaum) oder Algorithmusteile (z. B. binarySearch, insert bei AVL-Bäumen).
  4. Komplexitätsanalyse
     • z. B. Ableitung von $O$-Notation bei Schleifen, rekursiven Methoden oder gegebenen Funktionen.
• Strategie zur Vorbereitung
  1. Schreiben Sie zu allen gängigen Datenstrukturen und Algorithmen selbst kleine Code-Beispiele.
  2. Üben Sie, die Laufzeitfunktionen abzuleiten (insbesondere bei rekursiven Algorithmen).
  3. Prüfen Sie Ihr Verständnis, indem Sie Algorithmen auf Beispiel-Eingaben per Hand anwenden.
• Wichtig
  • Prüfen Sie, ob Sie zu jedem Algorithmus (und jeder Datenstruktur) mindestens einen Rechenbeispiel-Durchlauf gelöst haben.

4. Big-O-Cheat-Sheet und Komplexitätsübersicht

• Externe Ressourcen:
  Eine fast vollständige Übersicht bietet beispielsweise Big O Cheat Sheet.
  Dort finden Sie Zusammenfassungen wichtiger Datenstrukturen, deren Operationen und typische Sortieralgorithmen samt Laufzeiten.
• Komplexitäten im Überblick:
  • Lineare Datenstrukturen (Arrays, verkettete Listen)
  • Abstrakte Datentypen (Stacks, Queues, PriorityQueues)
  • Bäume, insbesondere Suchbäume (BST, AVL, Heap)
  • Sortieralgorithmen (BubbleSort, SelectionSort, InsertionSort, MergeSort, Quicksort, Heapsort)
  • Hashing-Methoden (open addressing, chaining)

5. Beispielaufgaben (Auswahl)

5.1 Verständnisfragen

Beispielaufgabe:

Geben Sie die Definition eines “fast vollständigen binären Baumes” an.
Was ist die minimale und was die maximale Anzahl Elemente in einem fast vollständigen binären Baum der Höhe $h$? Begründen Sie kurz Ihre Antwort.

Typischer Inhalt/Ansatz:

• Definition eines fast vollständigen binären Baumes (Levelweise gefüllt, das letzte Level ggf. nicht vollständig).
• Minimum und Maximum der Knotenanzahl (Formeln wie $2^h-1$ bzw. $2^{h+1}-1$).

5.2 Funktionsweise (Beispieldurchläufe)

Hier wird die Vorgehensweise verschiedener Algorithmen an konkreten Eingaben abgefragt:

1. Quicksort
   Beispielaufgabe:

   Sortieren Sie das Array [7, 6, 5, 9, 4, 8, 2, 3] mit dem Quicksort-Algorithmus. Nehmen Sie das linke Element als Pivot. Geben Sie nach jeder partition()-Operation das entstehende Array an.

2. Heapsort
   Beispielaufgabe:

   Sortieren Sie das Array [30, 1, 26, 39, 7, 18, 31, 4, 43, 3, 11, 14] per Heapsort. Geben Sie den Inhalt des Arrays nach dem Heap-Aufbau sowie nach jeder durchgeführten delete-Operation an.

3. AVL-Bäume
   Beispielaufgabe:

   Fügen Sie die Schlüssel [1, 3, 5, 6, 4, 2] in einen initially leeren AVL-Baum ein. Geben Sie den Baum nach jeder Einfügeoperation und jeder ggf. notwendigen Rotation an.

4. Hashing
   Beispielaufgabe:

   Gegeben eine Hashtabelle der Länge $m=13$ mit Hashfunktion $h(x)=xmodm$. Fügen Sie die Elemente [14, 1, 19, 10, 6, 11, 42, 21, 8, 17] mittels linear probing bzw. double hashing ein. Geben Sie den belegten Index pro Schritt an.

5.3 Java-Implementierung

Fragen dieses Typs verlangen in der Regel einen kurzen, aber korrekten Java-Code. Häufig geht es darum, das in der Vorlesung vorgestellte Prinzip zu übertragen.

• Beispiel:

  public int doubles(int[] a, int[] b) {
      // Anzahl der Elemente, die in beiden Arrays vorkommen
  }

  Gesucht: ein effizienter Algorithmus (z. B. Sortieren beider Arrays + Binärsuche O(n log n), oder Merge-Verfahren O(n log n + m log m)).

• Beispiel:

  public int binSort(BinTreeNode node, int[] a, int pos) {
      // Inorder-Traversierung eines Binärsuchbaumes
      // Alle Knotenwerte sollen sortiert in das Array 'a' geschrieben werden
  }

  Gesucht: korrekte Inorder-Rekursion mit Rückgabewert = Anzahl verarbeiteter Knoten, Laufzeit linear in n.

5.4 Komplexitätsanalyse

Diese Aufgabengruppe ist meist formaler Natur und verlangt Ableitungen und/oder Beweise zur $O$, $\mathrm{\Omega }$, $\mathrm{\Theta }$-Notation. Typische Beispiele:

1. Funktionen mit Polynomen, Logarithmen, Exponentialfunktionen

   f1(n) = n^3 * log n + 0.03 * n^4 + 2 * n

   Bestimmen einer einfachen Funktion g1(n) mit f1(n) ∈ O(g1(n)).

2. Formale Beweise

   Zeigen Sie, dass f(n) = log(n^n) in O(n^2 * log n) liegt.
   Hinweis: Aufsplitten, Logarithmengesetze, Konstante c für hinreichend großes n finden.

3. Einparameterfunktionen und Induktion

   • Rekursionsgleichungen (z. B. T(n) = 2 * T(n/2) + cn),
   • Baum-Methoden oder Master-Theorem,
   • Direkte Induktionsbeweise für die obere Schranke.

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

Beispielaufgabensammlung (nach Aufgabentypen sortiert)

Diese Aufgabensammlung umfasst Fragen und Übungen, die sich an früheren Klausuren und Übungsaufgaben zum Thema Algorithmen und Datenstrukturen orientieren. Die Beispiele sind nach den im Kurs behandelten vier Aufgabentypen gruppiert:

1. Verständnis-, Definitions- und Eigenschaftenfragen
2. Funktionsweise (exemplarische Durchläufe)
3. Java-Implementierung
4. Komplexitätsanalyse

5.1 Fragen nach Verständnis, Definitionen und Eigenschaften

Aufgabe 1.1: Fast vollständige Binärbäume und Heaps

• a) Geben Sie die Definition eines fast vollständigen binären Baumes an.

• b) Was ist die minimale und was die maximale Anzahl Elemente in einem fast vollständigen binären Baum der Höhe $h$?
  Begründen Sie kurz Ihre Antwort.

• c) Geben Sie die Definition eines Heaps an.

• d) Bestimmen Sie für jede der folgenden Operationen die Zeitkomplexität bei der Implementierung
  der abstrakten Datenstruktur PriorityQueue durch einen Heap:

  • $\text{min}\mathcal{O}()$
  • $\text{isEmpty}\mathcal{O}()$
  • $\text{insert}\mathcal{O}()$
  • $\text{delete}\mathcal{O}()$

• e) Kreuzen Sie die auf Heapsort zutreffenden Aussagen an (Mehrfachauswahl möglich):
  [ ] Heapsort sortiert in (O(n \log n)) Zeit im besten Fall.
  [ ] Heapsort sortiert in (\Theta(n^2)) Zeit im schlimmsten Fall.
  [ ] Heapsort sortiert in (O(n \log n)) Zeit im schlimmsten Fall.
  [ ] Heapsort ist ein stabiler Sortieralgorithmus.
  [ ] Heapsort ist ein in-place Sortieralgorithmus.
  [ ] Heapsort ist ein asymptotisch optimaler Sortieralgorithmus.
  [ ] Heapsort ist asymptotisch effizienter als Mergesort.
  [ ] Heapsort ist asymptotisch effizienter als Insertionsort.

5.2 Funktionsweise (exemplarische Durchläufe)

In diesem Aufgabentyp sollen Sie einen konkreten Algorithmus an einer konkreten Eingabe ausführen und alle Zwischenschritte (bzw. Kernschritte) angeben, z. B. Partitionierungs-Ergebnisse bei Quicksort, Heap-Aufbau bei Heapsort oder Rotationen in AVL-Bäumen.

Aufgabe 2.1: Quicksort (Pivot = linkes Element)

Aufgabe

Sortieren Sie das Array $[7,6,5,9,4,8,2,3]$ mittels Quicksort:

• Pivot-Element ist jeweils das linke Element des aktuellen Teilarrays.
• Geben Sie das Array nach jeder Partition-Operation an.
• Beschreiben Sie, wie sich die Teilarrays aufspalten, bis das gesamte Array sortiert ist.

Aufgabe 2.2: Heapsort (Aufbau + delete)

Sortieren Sie das Array ([30, 1, 26, 39, 7, 18, 31, 4, 43, 3, 11, 14]) mittels Heapsort.
1. Zeigen Sie zunächst den Inhalt des Arrays nach Abschluss der Heap-Aufbauphase (z. B. per buildHeap).
2. Geben Sie nach jeder delete-Operation (d. h. nach dem Entfernen und Neuaufbau des Heaps) den Zustand des Arrays an, bis die Sortierung vollständig ist (alle Elemente in aufsteigender Reihenfolge).

Aufgabe 2.3: Heap-Aufbau-Varianten

Heaps:

• a) Illustrieren Sie die Operationen und Zwischenschritte von HeapSort für das Eingabefeld $[5,13,2,25,7,17,20,8,4]$.
• b) Verwenden Sie nicht das buildHeap-Verfahren, sondern bauen Sie den Heap sukzessive durch iterative Anwendung von insert() auf.
  Geben Sie nach jedem Insert die Struktur des Heaps an.

Aufgabe 2.4: AVL-Bäume

Typische Aufgaben:

1. Fügen Sie die Schlüssel $[1,3,5,6,4,2]$ in dieser Reihenfolge in einen initial leeren AVL-Baum ein.
   Geben Sie den Baum nach jeder Einfügeoperation und jeder ggf. durchgeführten Rotation an.
2. Löschen Sie das Element mit Schlüssel 3 aus einem gegebenen AVL-Baum (Skizze vorgegeben).
   Geben Sie den Baum nach jedem Löschschritt und jeder Rotation an.
3. Sequentielle Einfügungen und Löschungen (insert/delete) in vorgegebener Reihenfolge.
   Notieren Sie nach jeder Veränderung die Struktur des Baumes und sämtliche durchgeführten Rotationen $(LL,LR,RL,RR)$.

Aufgabe 2.5: Hashing (open addressing)

Gegeben eine Hashtabelle der Länge $m=13$ mit Hashfunktion $h(x)=xmodm$.
Fügen Sie die Elemente $[14,1,19,10,6,11,42,21,8,17]$ mittels

• a) Linear Probing und
• b) Double Hashing - zweite Hashfunktion: $g(x)=1+(xmod(m+1))$ ein.

Führen Sie Schritt für Schritt aus, in welcher Reihenfolge die Slots belegt werden.

5.3 Java-Implementierung

Hier geht es darum, dass Sie kurze Codeausschnitte in Java schreiben oder das in der Vorlesung vorgestellte Prinzip in Java übertragen.
Häufig kann dabei die Nutzung bereits bekannter Hilfsmethoden (z. B. sort(), binSearch()) vorausgesetzt werden.

Aufgabe 3.1: Schnittmenge zweier Arrays (doubles)

Gegeben sind zwei Arrays int[] a und int[] b.
Das Array a enthält $m$, das Array $b$ enthält $n$ verschiedene ganze Zahlen in beliebiger Reihenfolge.

1. (2 Punkte) Welche Laufzeit benötigt der naive Algorithmus, der jede Zahl in einem Array mit allen Zahlen im anderen Array vergleicht?
2. (10 Punkte) Geben Sie eine möglichst effiziente Java-Methode public int doubles(int[] a, int[] b)
   an, die bestimmt, wie viele Elemente in beiden Arrays vorkommen
   (Stichwort: sortieren + verschmelzen oder sortieren + binäre Suche).
3. (2 Punkte) Welche Gesamtlaufzeit hat Ihr verbesserter Algorithmus?

Aufgabe 3.2: Binärbäume (Inorder-Traversierung)

Definieren Sie einen binären Suchbaum (BST) und geben Sie eine Java-Methode public int binSort(BinTreeNode node, int[] a, int pos)
an, die eine Inorder-Traversierung durchführt und die sortierte Folge der Knotenwerte in das Array a (beginnend an Index pos) einträgt.

• Ihre Methode soll die Anzahl der im Teilbaum befindlichen Knoten zurückgeben.
• Legen Sie dar, wie hoch die asymptotische Laufzeit (in Abhängigkeit der Knotenanzahl) ist.
• Zusatz: Geben Sie an, unter welchen Bedingungen binäre Suchbäume als balancierte Bäume bezeichnet werden können
  (Stichwort: Ausgewogenheits- und Restrukturierungsbedingung).

5.4 Komplexitätsanalyse

In diesen Aufgaben sollen Sie entweder Induktionsbeweise, Rekursionsbäume oder logarithmische Gesetze anwenden, um Laufzeiten oder Wachstumsordnungen zu bestimmen. Häufige Formen sind:

Aufgabe 4.1: Funktionen und obere Schranken (Big-O)

(Beispiel mit 4 Teilfunktionen)
Geben Sie zu jeder der folgenden Funktionen $f_i:\mathbb{N}\to \mathbb{R},1\le i\le 4$, eine möglichst einfache Funktion $g_i$ an, so dass $f_i\in O(g_i)$ gilt:

1. $f_1(n)=n^3\cdot \log n+0.03\cdot n^4+2\cdot n$
2. $f_2(n)=n\cdot \log n+n\cdot (\log n{)}^2+1234\cdot n$
3. $f_3(n)=5\cdot n\cdot \log (\log n)+n^2$
4. $f_4(n)=2\cdot (\log n{)}^2+34\cdot \log (\log n)+0.3\cdot \log n$

(Hierbei ist kein Beweis gefordert; es geht vorrangig um das Erkennen der dominanten Terme.)

Aufgabe 4.2: Formale Beweise (O, Ω)

1. Zeigen Sie formal, dass $f(n)=\log (n^n)$ in $O(n^2\log n)$ liegt.
2. Zeigen Sie formal, dass $f(n)=n\cdot {\log }_4(n)$ in $\mathrm{\Omega }(n\cdot {\log }_2(n))$ liegt.

Aufgabe 4.3: Mischeingaben (Fakultät und Exponential)

Eine Funktion $f$ sei definiert als

$$f(n)=\{\begin{array}{ll}n!& \text{für }1\le n\le 17\\ 2^{2n}& \text{für }18\le n\le 42\\ {\log }_2(n)& \text{für }n\ge 43\end{array}$$

Geben Sie eine möglichst langsam wachsende (aber zutreffende) obere Schranke $g$, sodass $f(n)\in O(g(n))$.
Begründen Sie, weshalb die Definition$\mathrm{\forall }n\ge N:f(n)\le c\cdot g(n)$ für geeignete Konstanten $c$ und $N$ erfüllt ist.

Aufgabe 4.4: Sortierte Funktionen

Ordnen Sie die folgenden Funktionen nach aufsteigender Wachstumsordnung:

$$f_1(n)=4223,f_2(n)=n^2\cdot \lfloor {\log }_2(n)\rfloor ,f_3(n)=2^n,f_4(n)=200\cdot n^3+0.02\cdot n^5,f_5(n)=n\cdot \sqrt{n/3},f_6(n)=n!$$

Beginnen Sie mit der kleinsten Komplexität.