Datenstrukturen und Algorithmen - Klausur 2.pdf mit Lösungen PDF

Preview

Summary

Alte Klausur mit Lösungen...

Description

RWTH Aachen Lehrgebiet Theoretische Informatik Rossmanith–Reidl–S´anchez

SS 2015 Klausur 4. August 2015

¨ Ubung zur Vorlesung Algorithmen und Datenstrukturen

Aufgabe 1 (4+3+3 Punkte) Wir beginnen mit einem leeren Splay-Baum. a) Es werden die Schl¨ussel 1, 2, 3, 4, 5 in dieser Reihenfolge eingef¨ugt. Wie sieht der Baum am Ende aus und wieviele Rotationen wurden durchgef¨ uhrt? b) Jetzt wird nach den Schl¨ usseln 5, 4, 3, 2, 1 in dieser Reihenfolge gesucht. Wie sieht der Baum am Ende aus und wieviele Rotationen werden durchgef¨uhrt? c) Wir l¨oschen jetzt den Schl¨ ussel 5. Beschreiben Sie was passiert und zeichnen Sie den entstehenden Splay-Baum. Aufgabe 2 (4+2+2+2 Punkte) F¨ ugen Sie die Zahlen 23, 12, 5, 17, 28, 10 und 5 in einen anfangs leeren Min-Heap ein (die kleineren Zahlen sind oben). Wie sieht dieser aus? Entfernen Sie jetzt nacheinander dreimal die kleinste Zahl aus dem Heap. Wie sieht er nach jeder der drei Operationen aus? Aufgabe 3 (2+3+3+3 Punkte) Gegeben sei das folgende Flußnetzwerk G zusammen mit einem Fluß f . a) b) c) d)

12/12

v1

v3 15/20

11/16 s

8/13 Wie groß ist |f |? Geben Sie das zugeh¨ orige Residualnetzwerk an. Welchen Wert v hat ein maximaler Fluß in G? Wie beweisen Sie, daß v tats¨achlich maximal ist?

1/4

10

7/7

4/9

t 4/4

v2

11/14

v4

Aufgabe 4 (2+2+2+2 Punkte) Sie haben ein Array mit n Elementen, welche Bin¨arzahlen mit je b Bits sind. Das Array soll sortiert werden, und Sie m¨ ussen sich entscheiden, ob sie Heapsort oder Radixsort verwenden wollen. √ Welches Verfahren ist jeweils asymptotisch schneller, wenn b = 10, allen die b = log n, b = n und b = n? Welche Laufzeiten haben in diesen vier Spezialf¨ beiden Algorithmen ausgedr¨uckt als Funktion von n? Aufgabe 5 (4+4 Punkte) Erl¨ autern Sie, wie man in einem ungerichteten Graphen G in linearer Zeit herausfinden kann, ob G kreisfrei ist. Begr¨ unden Sie die Korrektheit des Verfahrens.

RWTH Aachen Lehrgebiet Theoretische Informatik Rossmanith–Reidl–S´anchez

SS 2015 L¨osungsvorschlag der Klausur ?. August 2015

¨ Ubung zur Vorlesung Algorithmen und Datenstrukturen

Aufgabe 1 (4+3+3 Punkte) a) Es werden vier Rotationen ausgef¨uhrt. Der Baum sieht dann so aus:

b) Wieder werden vier Rotationen ausgef¨uhrt und wir erhalten diesen Baum:

c) Nachdem das Blatt 5 entfernt wurde, wird eine Splay-Operation auf 4 ausgef¨uhrt. Mit einem Zag-zag gefolgt von einem Zag wird sie dabei in die Wurzel hochrotiert. Der resultierende Baum ist dieser:

Aufgabe 2 (4+2+2+2 Punkte) Der entstehende Heap sieht so aus:

Die weiteren Heaps nach jeweiligem Entfernen des kleinsten Elements sind:

Aufgabe 3 (2+3+3+3 Punkte) (a) Der eingezeichnete Fluß f hat offenbar den Wert 19, weil aus dem Startknoten ein Fluß von 11 + 8 austritt. (b) Das Residualnetzwerk ist unten abgebildet. (c) 23, wie der minimale Schnitt uber den mit 12/12, 7/7 und 4/4 beschrifteten Kanten ¨ zeigt. Wir werden das aber anders beweisen: (d) Im Residualnetzwerk kann man einen augmentierenden Pfad der Kapazit¨ at 4 finden (s, v2 , v3 , t) – und danach keinen weiteren mehr, wie das (hier nicht abgebildete) zugeh¨orige Residualnetzwerk zeigt. 12

v1

v3 15

11 5 11 8

s

5

5 3

7

t

4

5

4

11 v4

v2 3

Aufgabe 4 (2+2+2+2 Punkte) Zun¨ achst zu Heapsort: Die Laufzeit ist hier stets Θ(n log n) unabhangig von b, da ja ¨ Worte der L¨ange b in einem Schritt verarbeitet werden. Jetzt Radixsort: Die Laufzeit ist Θ(bn), also in den vier F¨ allen Θ(n), Θ(n log n), Θ(n3/2 ) 2 und Θ(n ). Man sieht, daß im ersten Fall Radixsort schneller ist und in den letzten beiden F¨ allen Heapsort. Im zweiten Fall sind die Laufzeiten bis auf einen konstanten Faktor gleich.

Aufgabe 5 (4+4 Punkte) Wir k¨ onnen einfach eine Tiefensuche durchf¨ uhren und dann sehen, ob eine R¨uckw¨artskante existiert. Der Graph ist genau dann kreisfrei, wenn es keine R¨ uckw¨artskante gibt. Wenn es tats¨ achlich eine R¨uckw¨ artskante gibt, dann gibt es auch einen Kreis, da die beiden Endknoten der R¨ uckw¨artskante durch einen aus Baumkanten bestehenden Pfad verbunden sind. Umgekehrt kann es ohne R¨uckw¨ artskanten keinen Kreis geben, denn bei einem ungerichteten Graphen gibt es nur Baum- und R¨ uckw¨ artskanten. Ohne R¨ uckw¨artskanten gibt es also nur Baumkanten und der ganze Graph ist ein Wald und damit kreisfrei....