Hallihallo!

weiss hier jemand ob es von der Fachschaft oder so Altklausuren für GDB oder AD gibt?
finde da auf der Seite nur diese Gedächnisprotokolle, aber da gibts beispielsweise AD gar nicht…

Danke schon mal!

1. multiple Choice: hauptsächlich Laufzeitkomplexität von bekannten Algorithmen und Anzahlen von
bekannten Graphen/Bäumen
2. Laufzeit berechnen: Drei Laufzeiten mit Hilfe des Master-Theorems ausrechnen
3. Laufzeitabschätzung: Einen rekursiven divide-and-conquer Algorithmus untersuchen und die
asymptotische Laufzeit abschätzen. Ferner die Korrektheit des Algorithmus beweisen. Der Algorithmus
sollte das maximale Element eines Arrays finden.
zu 4., genauere Aufgabe:
Hashfunktion: g(k) = k mod 11
Quadratisches Sondieren: h(k, i) = (g(k) + 1/2(i + i^2)) mod 11
1. Begründen Sie, warum die Sondierungsfolge nicht von der Einfügereihenfolge der Elemente abhängt.
2. Gefüllte Hashtabelle mit 11 Werten: Bestimmen Sie die Sondierungsfolge für die einzelnen Werte bis zu
der Position, an der sie eingefügt worden. Für 4 Zahlen haben wir das schonmal eingetragen. Hier ist
nochmal die Hashfunktion, damit sie nicht umblättern müssen.
3. Geben Sie eine Einfügereihenfolge für die Elemente an, die zur angegebenen Füllung der Hashtabelle
führen würde. Begründen Sie dies für die ersten 3 Elemente.
zu 5., genaue Aufgabe:
1. Wie können Sie die Datenstruktur eines balancierten, binären Suchbaums so verändern, dass sich die Frage
"Wie viele Elemente haben einen Wert kleiner als x" in O(log n) beantworten lässt? Begründen Sie Ihre
Lösung.
2. Schreiben Sie einen Algorithmus, der das tut. (Stand da natürlich ein bisschen anders…)
3. Verändern Sie folgende Algorithmen zum Einfügen eines Elementes und für die Linksrotation, damit das
mit der veränderten Datenstruktur auch passt. (So sinngemäß.)
6. Schreiben sie einen Algorithmus in kommentiertem Pseudocode, der für einen Knoten aus einem
gerichteten Graphen bestimmt, ob er in 2 Kantendisjunkten Zyklen vorkommt.
und dann noch die Frage: Wie können Sie in …. Zeit für einen gerichteten Graphen entscheiden, ob er Zyklen
enthält?
7. minimale Spannbäume: minimalen Spannbaum anhand eines (beliebigen) Algorithmusses erstellen und
diesen benennen können. Beweisen, ob eine Kante e mit minimalem Kantengewicht in a) einem Spannbaum
drin ist und b) in allen Spannbaum drin ist.
Es war also ein kantengewichteter Graph gegeben und man sollte den Spannbaum einzeichnen sowie
beschreiben, wie man vorgegangen ist. Und den Namen des Algorithmus angeben, wenn Newton das richtig
erinnert… kann ich mich gar nicht dran erinnern, aber gemacht hab ich's auch.

Hier ins Forum werden öfter Protokolle eingestellt, die Suchfunktion könnte dir helfen.