Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer
Kennzahl:

Frühjahr
2013

Kennwort:

46115

Arbeitsplatz-Nr.:

Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen

— Prüfungsaufgaben —

Fach: Informatik (Unterrichtsfach)
Einzelprüfung: Th. Informatik, Algorith./Datenstr.
Anzahl der gestellten Themen (Aufgaben): 2

Anzahl der Druckseiten dieser Vorlage: 7

Bitte wenden!



Frühjahr 2013 | Einzelprüfungsnummer 46115 Seite 2
Thema Nr. 1

Aufgabe 1:
Reguläre Sprachen
Sei L die Menge aller Worte der Länge >2 über dem Alphabet (ab), bei denen das zweite und das
zweitletzte Zeichen identisch sind.
a) Geben Sie alle Worte der Länge <4 von L an.
b) Zeigen Sie, dass L regulär ist.
Aufgabe 2:
Pumping Lemma

a) F ormulieren Sie das Pumping Lemma für reguläre Sprachen.

b) Zeigen Sie mit Hilfe des Pumping Lemmas, dass die Sprache {a b! c! | i,j> 0} nicht
regular ist.

Aufgabe 3:

Kontextfreie Sprachen
Zeigen Sie, dass die Sprache L = {a! b? c'd! | i,j, p, q 20 und i= und p = q} kontextfrei ist.

Wenn Sie eine passende Grammatik G / einen passenden Automaten M angegeben haben,
brauchen Sie nicht zu beweisen, dass L=L(G) bzw. L=L(M) ist.

Aufgabe 4:
Turingmaschinen
SeiL={uvjue {a,b}*, ve {c,d}*, #,(u) = #.(v) und #,(u) = Halv)}

wobei #,(u) die Anzahl der in u vorkommenden a's ist.

a) Geben Sie eine Turingmaschine M an, die L erkennt.
Beschreiben Sie in Worten, wie Ihre Turingmaschine arbeitet.

b) Welche Laufzeit (Zeitkomplexität) hat Ihre Turingmaschine (in O-Notation).
Begründen Sie Ihre Angabe auf der Grundlage der Beschreibung.

Aufgabe 5:
O-Notation

Gegeben seien die Funktionen £N — Nundg:N — N, wobei f{n)=2n?+2 und g(n)}=3n(n2-1).
Geben Sie an, welche der folgenden Aussagen gelten. Beweisen Sie Ihre Angaben.

a) fin) eO(g(n))
b) g(n) € O(f(n)) _ Fortsetzung niichste Seite!


Frühjahr 2013 Einzelprüfungsnummer 46115 | Seite 3
Aufgabe 6: |
Sortieren |

a) Erläutern Sie, wie Bubblesort arbeitet.

b) Sortieren Sie die folgende Liste von Zahlen mit Bubblesort und geben Sie die
Zwischenergebnisse nach jeder Runde an.
2,10,3,8,1,9,5,4,6,7

c) Für welche Eingaben ist die Laufzeit von Bubblesort maximal (der worst case)?

- Aufgabe 7:

AVL-Bäume
Gegeben sei der folgende AVL-Baum T. Führen Sie auf T folgende Operationen durch:

Fügen Sie zunächst den Wert 1 inT ein. Fügen Sie anschließend den Wert 26 in T ein.
Balancieren Sie nach jeder Operation falls nötig und ‚geben Sie den entstandenen Baum (als
Zeichnung) an.

Aufgabe 8:

Minimaler Spannbaum

Gegeben sei der unten stehende ungerichtete Graph C G= (V, E) mit positiven Kantenlängen Äe)
für jede Kantee e E.

Berechnen Sie mit einem Algorithmus Ihrer Wahl einen minimalen Spannbaum von G.
Verwenden Sie den Knoten s als Startknoten.



Frühjahr 2013 - Einzelprüfungsnummer 46115 Seite 4

Thema Nr. 2

Aufgabe 1: |
Sei © = {0,1,$} und sei Ny = {0,1,2,...}.
a) Sei |
= {0"$I"|ne No} U {0"$1"| nENg }.
Beispiele: 00$1111 eL,,$ e L}000$1 e Lı.

(al) Zeigen Sie, dass L; kontextfrei ist, indem Sie eine kontextfreie Grammatik G angeben mit
L(G) = Lı, und

(a2) begründen Sie, warum Ihre Grammatik genau die Sprache L, erzeugt.
b) F ormulieren Sie das Pumping-Lemma für kontextfreie Sprachen:

„Sei L eine kontextfreie Sprache über dem Alphabet x. Dann
gibt es.

.c) Zeigen Sie, dass die Sprache L; die Eigenschaften des Pumping-Lemmas für kontextfreie
Sprachen erfüllt.

Aufgabe 2:
a) _ Geben Sie einen deterministischen endlichen Automaten an (Zeichnung), der die Sprache
Ly = {a'| ie N,i ist durch 3, aber nicht durch 2 teilbar}
akzeptiert. (N = {1,2,...}) |

b) Beweisen oder widerlegen Sie die folgende Behauptung:
Beh.: Ist die Sprache Z regulär, dann ist auch jede echte Teilmenge von L regular.

c) Zu einem Wort w = ayaz ... Ap Sei
spiegelung(w) = fa,...aı? .
Außerdem sei spiegelung(E)= fe}.
Beweisen oder widerlegen Sie die folgende Behauptung:
Beh.: Ist die Sprache Z regulär, dann ist auch

spiegelung(L) = U spiegelung(w)

‚wel

regulär.

Fortsetzung nächste Seite!



Frühjahr 2013 Einzelprüfungsnummer 46115 Seite 5

Aufgabe 3: „Binärer Suchbaum“

Ein Suchbaum ist ein binärer Baum mit der Eigenschaft, dass für jeden Knoten n alle Datenelemente
im linken Teilbaum kleiner und alle Elemente im rechten Teilbaum größer sind als das Element des

Knotens n.

a) Fügen Sie in einen anfangs leeren binären Suchbaum der Reihe nach die Datenelemente 7, 0, 9,
11, 18, 4, 5, 3, 13, 24, 2 ein. Zeichnen Sie nur den Endzustand.

b) Geben Sie eine Einfügereihenfolge (keinen Baum) für obige Zahlen an, bei der die Höhe
minimal wird.

c) Geben Sie eine weitere Einfügereihenfolge dieser Datenelemente an, bei der die Höhe des
entstehenden Baums maximal wird.

d) Fügen Sie die Zahlen aus Teilaufgabe a) in der gegebenen Reihenfolge in einen anfangs leeren
AVL-Baum ein. Zeichnen Sie dazu nur den jeweils entstandenen Baum zu folgenden
„Zeitpunkten“:

a. Unmittelbar vor dem Einfügen der Zahl 18
b. Nach dem Einfügen der Zahl 18 jeweils vor und nach der Rotation
c. Nach dem Einfügen aller Zahlen (also den vollständigen AVL-Baum)

e) Fügen Sie nun Ihrem vollständigen AVL-Baum aus der letzten Teilaufgabe noch die Zahl 30.

hinzu und geben Sie den schließlich entstandenen AVL-Baum an.

Aufgabe 4: „Streuspeicherung“

Die Werte 7, 0, 9,11, 18,4, 5, 3, 13, 24, 2 sollen in eine Hashtabelle der Größe 11 (Fächer 0 bis
10) eingetragen werden. Die zur Hashfunktion h(x) = (7 : x)%11 gehörenden Schlüssel sind in der
folgenden Tabelle bereits ausgerechnet:

x 7 |, 0 9 11 18 | 4 5 3 13 24 2

h(x) 5 0 8 0 5 | 6 2 | 10 | 3 3 3

a) Fügen Sie die oben genannten Schlüssel in der vorgegebenen Reihenfolge in einen
Streuspeicher ein, welcher zur Kollisionsauflésung verkettete Listen verwendet, und stellen Sie
die endgülttige Streutabelle dar.

b) Fügen Sie die gleichen Schlüssel mit linearem Sondieren bei Schrittweite +1 zur
Kollisionsauflösung in eine neue Hash-Tabelle ein. Geben Sie für jeden Schlüssel an, auf
welche Felder beim Einfügen zugegriffen wird und ob Kollisionen auftreten. Geben Sie die
gefüllte Streutabelle an.

c) Wie hoch ist der “Load”-Faktor (die Belegung) der Hashtabelle aus a) bzw. b) in Prozent?
Können Sie weitere Schlüssel einfügen?

d) Würden Sie sich bei dieser Zahlensequenz für das Hashing-Verfahren nach a) oder nach b)
entscheiden? Begründen Sie kurz Ihre Entscheidung.

Fortsetzung nächste Seite!



Frühjahr 2013 Einzelprüfungsnummer 46115 00 Seite6

Aufgabe 5: „Graphen“

. Gegeben seien folgende ungerichtete Graphen in textueller Notation, wobei die erste Menge die
Menge. der Knoten und die zweite Menge die Menge der Kanten ist:

=(11,2,3,4,5,6}, {[12], 11.41, 1231, 13,41, [4,5], [4,61, [5,613 )
G = ( {1,2,3,4,5,6}, {[11,2],[1131,[12,31,14,51.[14,61,15,61} )
G=((123,4,5,6), £11,21,01,6,.12,31,2,51,23,41.14,51.15,613 )

a) Zeichnen Sie die obigen Graphen.
.b) Erstellen Sie zu jedem Graphen die zugehörige Adjazenzmatrix mit X als Symbol für eine

eingetragene Kante.

c) Für welche(n) der drei Graphen existiert ein Eulerzyklus? Begründen Sie kurz, wieso es bei dem
bzw. den anderen Graphen keinen Eulerzyklus gibt.

d) Betrachten Sie nun folgenden gerichteten Graphen G;:

Bestimmen Sie die kürzeste Entfernung vom Knoten A zu jedem anderen Knoten des Graphen.
Verwenden Sie dazu den Algorithmus von Dijkstra und tragen Sie Ihre einzelnen Rechenschritte in
eine Tabelle folgender Form ein (schreiben Sie neben jede Zeile die Prioritätswarteschlange der.
noch zu bearbeitenden Knoten, priorisiert nach ihren Wegkosten):

AIB;]C]D|E]F Warteschlange

(Io ho wo | A

e) Nennen Sie einen geeigneten Algorithmus, um einen minimalen Spannbaum für den obigen
Graphen G4 zu ermitteln und wenden Sie diesen schrittweise (z.B. tabellarisch) an.

Fortsetzung nächste Seite!

Frühjahr 2013 Einzelprüfungsnummer 46115 Seite 7
Aufgabe 6: Sortierverfahren“

a) Vervollständigen Sie die folgende Sortierung mit MergeSort (Sortieren durch Mischen) —
beginnen Sie dabei Ihren „rekursiven Abstieg“ immer im linken Teilfeld:

D|40 5 89 95 #8 u|u 320 52 7 al

Notation: Markieren Sie Zeilen mit D(ivide), in denen das Array zerlegt wird, und mit M(erge), in
denen Teilarrays zusammengeführt werden. Beispiel:

D|82|89 44
D 82|89| 44
M 82|44 89

M|44 8 89

b) Sortieren Sie mittels HeapSort (Haldensortierung) die folgende Liste weiter:

A 99 | 63 91 _ 4 36 81 76
‘R | 76 a | | 99

Notation: Markieren Sie die Zeilen wie folgt:
I: Initiale Heap-Eigenschaft hergestellt (größtes Element am Anfang der Liste).
R: Erstes und letztes Element getauscht und letztes „gedanklich entfernt“.

S: Erstes Element nach unten „versickert” (Heap-Eigenschaft wiederhergestellt).