Gedächtnisprotokoll AD09-1

Die erste AD Klausur im WS 08/09 fand am 16.02.2009 statt. Bearbeitungszeit waren 2 Stunden (120 Minuten) und es gab 100Punkte. Die Klausur war eine gute Mischung aus Multiple-Choice-Fragen und Anwendungsaufgaben. Wenn man das Tutorium bei Frank Heitmann besucht hatte, war es gut möglich die Klausur zu bestehen.

Gliederung muss nicht unbedingt korrekt sein.

Inhaltsverzeichnis 1 O-Notation 2 Aufagbe 2 3 NP 4 Rekurrenzgleichung 5 Suchbäume 6 Aufgabe 6 7 Kurskal 8 Aufgabe 8 9 Heap 10 Aufgabe 10

[Bearbeiten] O-Notation

Jeweils Ja/Nein ankreuzen, ein Zusatzpunkt für kurze Begründung

• 2^{n + 3}
• Ω(
• Kann für zwei Funktionen f,g f gelten?
• Gilt o(n²) ?
• Gilt Fehler beim Parsen (Syntaxfehler): 7^{log_2 n} \in \Theta(n^3)

?

• Ist folgende Behauptung richtig? Schlechteste Laufzeit von QuickSort ist

[Bearbeiten] Aufagbe 2

• Zeigen sie durch ein Gegenbeispiel, dass der kürzeste Pfad zwischen zwei Punkten nicht zwingend eine Kante des minimalen Spannbaums des Graphen nutzen muss.
• Was bedeutet es, wenn ein NP-schweres Problem in P liegt?

[Bearbeiten] NP

• Formulieren sie das Problem des Eulerkreis (Euler) für einen Graphen G = (V, E) als formale Sprache.
• Welche Eigenschaften muss eine Abbildung f mit L und M besitzen, damit es eine polynominalle Reduktion ist?

[Bearbeiten] Rekurrenzgleichung

• Gegeben ist eine rekursive Gleichung T(n). Trages Sie die ersten 5 Werte in eine Tabelle ein, finden sie eine Formel in geschlossener Form (also ohne Summmenzeichen) und beweisen sie diese anschließend durch Induktion.

[Bearbeiten] Suchbäume

• Wenn sie in einem Suchbaum alle Elemente aufsteigend ausgeben wollen, in welcher Reihenfolge müssen sie dann suchen? Ankreuzmöglichkeiten: preorder inorder postorder
• Anzahl innerer Knoten eines Binärbaums der Höhe h

a) wenn der Baum minimal b) wenn der Baum maximal ist. Jeweils eine geschlossene Form(d.h. ohne Summenzeichen) angeben und begründen!

• Kann ein Rot-Schwarz-Baum ein AVL-Baum sein?
• Zeichnen sie alle binären Suchbäume der Menge {1,2,3}.
• Ist jeder Suchbaum eine spezielle Form des Heaps?

[Bearbeiten] Aufgabe 6

• Kreuzen sie in der Tabelle die Zugriffsmethoden auf die einzelnen Datenstrukturen an.

        | Schlange | Keller | Feld | stack | array | queue
--------+----------+--------+------+-------+-------+--------
fifo    |          |        |      |       |       |
--------+----------+--------+------+-------+-------+--------
lifo    |          |        |      |       |       |
--------+----------+--------+------+-------+-------+--------
random  |          |        |      |       |       |
access  |          |        |      |       |       |

• Wann wird ein Sortierverfahren als stabil bezeichnet?

[Bearbeiten] Kurskal

Gegeben ist ein Graph

• Bestimmen sie den minimalen Spannbaum und tragen sie in die Tabelle ein, wann sie welche Kante zum Spannbaum hinzugefügt haben, und welche ausgelassen wurden.
• Mit welcher Datenstruktur würden sie Kruskal implementieren, ohne groß Laufzeit zu verschenken?

[Bearbeiten] Aufgabe 8

• Gegeben sind 13 ganze Zahlen Geben sie an
  • den Median
  • den Mittelwert
• Geben sie in O-Notation die Laufzeit von X im schlechtesten Fall an.
  • Heapsort
  • Radixsort
  • Sortieren durch Einfügen

[Bearbeiten] Heap

Gegeben ist ein Heap in Array-Darstellung

• Zeichnen sie den Heap

[Bearbeiten] Aufgabe 10

• Geben sie die Komplexität an, imt dem der Median aus einer Teilmenge von N berechnet werden kann.
• Gegeben ist ein verletzer AVL-Baum. Führen sie die notwendigen Rotationen durch, um den AVL-Baum zu korrigieren.