Probeklausur 26 Juli, Fragen PDF

Preview

Summary

at zu oln Mathematisches Institut Prof. Dr. F. Vallentin Dr. A. Gundert der Informatik I Sommersemester 2019 Probeklausur Name: Vorname: Matrikelnummer: Studiengang: Hiermit are ich mich damit einverstanden, dass mein Klausurergebnis auf der Vorlesungsseite offentlicht wird. Hiermit are ich, dass ic...

Description

oln Universit¨ at zu K¨ Mathematisches Institut Prof. Dr. F. Vallentin Dr. A. Gundert

Grundz¨uge der Informatik I Sommersemester 2019 — Probeklausur —

Name: Vorname: Matrikelnummer: Studiengang:



Hiermit erkl¨are ich mich damit einverstanden, dass mein Klausurergebnis (Matrikelnummer/Punktezahl) auf der Vorlesungsseite ver¨ offentlicht wird.

andig und ohne unerlaubte HilfsHiermit erkl¨ are ich, dass ich diese Klausurleistung selbst¨ mittel erbracht habe. oln, den K¨

(Unterschrift des/der Studierenden)

Bitte beachten Sie, dass sich die Aufgaben auf die in der Vorlesung vorgestellten Algorithmen und Konzepte beziehen.

Viel Erfolg!

Aufgabe Punkte

1

2

3

4

1

5

6

Gesamt

Note

Aufgabe 1 1. Tragen Sie in die L¨ ucke ein passendes Landausymbol (O, Ω oder Θ) ein: 3n2 − 7

=

(n)

10n log(n) + 4n + 3 log(n)

=

(n)

2n + 5

=

(n2 )

10100

=

(n)

2n+4

=

(2n )

ur die folgende durch Rekursion gegebene 2. Finden Sie eine geschlossene Formel f¨ Funktion f und beweisen Sie diese mit vollst¨ andiger Induktion: f (n) = 3f (n/2) + 4,

f (1) = 1.

onnen Sie annehmen, dass n = 2k . Hierbei k¨ 3. Betrachten Sie folgenden Algorithmus f¨ ur einen bin¨ aren Baum T : function F(T) if T = empty then 3: return “ ” 4: else 5: return F(T.left)+T.root.key+F(T.right) 1: 2:

ur folgendes Beispiel aus? Welchen String gibt der beschriebenen Algorithmus f¨ + − ∗ 6

∗ 5

2

8

+ 3

3

2

5

Aufgabe 2 1. Beweisen Sie, dass die erwartete Gr¨ oße des rechten Arrays D im ersten rekursiven ist, wenn das Eingabearray keine Elemente mit gleichen Aufruf von Quicksort n−1 2 Schl¨ usseln enth¨ alt. 2. Wenden Sie die erste Phase des Algorithmus HeapSort (HeapCreation) auf folgendes Array an. Dokumentieren Sie Ihr Vorgehen. (2, 6, 25, 2, 7, 53, 18, 9, 35, 1, 10, 8, 1). 3. Beschreiben Sie die Funktionsweise der zweiten Phase des Algorithmus HeapSort (Selection).

7

9

Aufgabe 3 1. Was gibt der folgende Programmabschnitt aus? 1: 2: 3: 4: 5: 6: 7: 8: 9:

Q =leere Queue enqueue(Q,3) enqueue(Q,8) x=dequeue(Q) enqueue(Q,1) enqueue(Q,x) enqueue(Q,5) while Q nicht leer do Gebe dequeue(Q) aus.

2. Geben Sie die insert-Operation f¨ ur bin¨ are Suchb¨aume in Pseudocode an. Verwenden Sie die Notation der Vorlesung. unden Sie Ihre 3. Was ist die Laufzeit der insert-Operation f¨ ur bin¨ are Suchb¨aume? Begr¨ Antwort. 4. F¨uhren Sie die Operation delete(T,x) mit key(x)=7 an folgendem bin¨ aren Suchbaum aus. Dokumentieren und erkl¨aren Sie Ihr Vorgehen. 7 2

14

1

5 4

11 9 8

11

21

12 17 35 13 19

13

Aufgabe 4 1. F¨uhren Sie eine Doppelrotation (LR, d.h. erst L, dann R) an folgendem Baum aus: x1 x2

x3

x4

x5

x6

x7

T1

T2

T3

T4

2. Zeigen Sie, dass eine Doppelrotation die Suchbaumeigenschaft erh¨ alt. 3. L¨ oschen Sie in folgendem AVL-Baum den Knoten mit Schl¨ ussel 18. Dokumentieren Sie Ihr Vorgehen. 18 10 3 1

25 14

7

11 17

20

32 28

5

4. Geben Sie die Definition einer universellen Menge von Hash-Funktionen an.

15

17

Aufgabe 5 oglichkeiten, einen gerichteten 1. Beschreiben Sie zwei in der Vorlesung vorgestellte M¨ Graphen D = (V, A) im Computer darzustellen. 2. Geben Sie den in der Vorlesung vorgestellten Algorithmus zum topologischen Sortieren in Pseudocode an. 3. Wenden Sie den Algorithmus von Bellman-Ford mit Startknoten s auf den unten angenfunktion ist hierbei in den Adjaangegebenen gerichteten Graphen an. Die L¨ zenzlisten angegeben: Lv enth¨ alt Paare (w, ℓ((v, w))) mit (v, w) ∈ A. V = {s, a, b, c, d, e, f } Ls : (a, 2), (b, 5), (d, 7), La: (d, −2), (f, 4), Lb : (c, 3), (f, 2), Lc : (f, 2), Ld : (e, 5), Le : (a, 1), (c, 3), (f, −5). (Lf ist leer.)

19

21

Aufgabe 6 1. Geben Sie die Definition eines minimalen Spannbaums an. 2. Sei G der Abstandsgraph definiert durch die Tabelle Berlin Frankfurt/Main Hamburg oln K¨ M¨unchen

564 279 509 553 185 381 596 412 772 Be Fr Ha

578 K¨ o M¨u

Bestimmen Sie einen minimalen Spannbaum unter Verwendung des Algorithmus’ von Kruskal. 3. Gegeben ist der folgende Graph mit Kantenl¨angen: v1 4

v4 17

v8

8 11 14

13 3

v2 13

v5 5

7 9 10

6

v9

12

v3 12

v6 2

11 9

v7

10

v10

Folgender Wald (V, T ) ist ein guter Wald. v1

v2

v3

v4

v5

v6

v8

v9

v10

v7

unden Sie, warum (V, T ∪ {{v6 , v7 }}) auch ein guter Wald ist. Begr¨

23

25...