Prüfungsteilnehmer Prüfungstermin Einzel’ fungsnummer

Kennzahl:

Herbst
Kennwort: 46 1 1 2
1998

Arbeitsplatz-Nr.:

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

- Prüfungsaufgaben -
Fach: Informatik (nicht vertieft studiert)
Einzelprüfung: Grundlagen der Informatik

Anzahl der gestellten Themen (Aufgaben): 1

Anzahl der Druckseiten dieser Vorlage: 3

Bitte wenden!
Herbst 1998 Einzelprüfungsnummer: 46112 Seite: 2

Sämtliche Teilaufgaben sind zu bearbeiten!

Aufgabe 1

Für reelle Zahlen soll mit Hilfe von geordneten Binärbäumen eine Rechenstruktur aufgebaut werden, die das Einfügen und Löschen erlaubt. Die Programmierung soll in PASCAL

erfolgen.

1.1 Geben Sie eine Deklaration für die erforderliche Datenstruktur an!
1.2 Geben Sie Deklarationen für folgende Prozeduren an:

1.2.1 Eine Prozedur KRE mit folgender Spezifikation:
KRE hat den Namen eines Binärbaums als Parameter und erzeugt einen leeren
‚Binärbaum unter diesem Namen.
1.2.2 Eine Prozedur EIN mit folgender Spezifikation:
EIN hat 2 Parameter, und zwar den Namen eines Binärbaums sowie den Wert
einer reellen Zahl, und ordnet die reelle Zahl in diesen Binärbaum ein, falls sie
noch nicht in ihm enthalten ist.
1.2.3 Eine Prozedur AUS mit folgender Spezifikation:
AUS hat 2 Parameter wie bei 1.2.2 und löscht die reelle Zahl aus dem geordneten
Binärbaum, falls sie in ihm enthalten ist.

1.3 Skizzieren Sie den geordneten Binärbaurm mit dem Namen z, der entsteht, wenn ein
Programmlauf folgende Prozeduraufrufe in der angegebenen Reihenfolge ausführt:
KRE(z); EIN(z,3.1); EIN(z,5.7); EIN(z,3.1);

EIN(z,5.6); EIN(z,2.4); AUS(z,3.1); EIN(z,7.0); EIN(z,4.8);
EIN(z,3.0); EIN(z,3.2); EIN(z,1.7); EIN(z,2.6); AUS(r,4.8);

Aufgabe 2

Gegeben sei das binäre Alphabet B = (O,L). Die Menge P C B* sei die Menge aller
durch 5 teilbaren und H C B* die Menge aller durch 6 teilbaren Binärzahlen. Die leere Zeichenreihe & werde nicht als Binärzahl angesehen, ist also weder in P noch in H

enthalten.

2.1 Konstruieren Sie einen endlichen Automaten Ap, der genau die Binärzahlen aus P
akzeptiert!

Hinweis: Ein Automat Ap kann z.B. mit Hilfe des gewöhnlichen Divisionsalgorithmus für Binärzahlen gefunden werden.

2.2 Der folgende Graph stellt einen endlichen Automaten Ay über B dar, der mit so als
Anfangs- und f als Endzustand genau die Binärzahlen aus H akzeptiert. Konstruieren Sie mit Hilfe dieses Automaten Ayr die Menge H als reguläre Menge!

ı a Fortsetzung nächste Seite!
Herbst 1998 Einzelprüfungsnummer: 46112 Seite: 3

Aufgabe 3

Gegeben sei ein endlicher ungerichteter Graph G mit der Knotenmenge V = (v1,v2,...,Un),
nm > 1. G enthalte weder Schleifen noch Mehrfachkanten. Zur Darstellung des Graphen

werde die Adjazenzmatrix
A= (4:3 )ijot.2.-n
verwendet. Nach den oben genannten Festlegungen gilt:

a: 0, falls v; und v; nicht durch eine Kante verbunden sind
‘J | 1 sonst
ea; = 4 für 1,3 = 1,2,...n

.ea;,=0füri=1,2...n

Seien u und v zwei Knoten aus V. Dann heißt eine endliche Knotenfolge w = (wo, wi, wa, -.-, Wr)
aus V ein Weg der Länge r zwischen u und v genau dann, wenn w folgenden Bedingungen

genügt:
er>0

« Sei p(g) der eindeutige Index mit vu; = w, für o=0,1,2,...r.
Dann gilt apc), p(e41) = 1 fir 9 = 0,1,2,...,7—1.

@ ((wo =u) A (w, = v)) V ((wo = v) A (wr = u))

Als Matrix der kürzesten Weglängen von G wird die Matrix
We (wien...
bezeichnet, deren Komponenten folgendermaßen definiert sind:

£ die Länge eines kürzesten Weges zwischen v; und v; ist

Wi; =
0, falls es keinen Weg zwischen v; und v; gibt

| é, falls es einen Weg zwischen v; und v; gibt und

3.1 Geben Sie W für den folgenden Graphen an!

N

3.2 Nennen Sie Knotenpaare (v;,v;), für die w;; stets 0 ist, und begründen Sie Ihre
Antwort!

vy v2 U3 v4

UT Ug Us

3.3 Schreiben Sie eine Prozedur WEGE in PASCAL mit folgender Spezifikation:

WEGE hat 2 Eingabe- und 1 Ausgabeparameter. Die Eingabeparameter sind der
Wert von n und der Name von A. Der Ausgabeparameter ist der Name von W. Die
Prozedur berechnet die Matrix W aus n und A.

Hinweis: Es ist empfehlenswert, das Programm für die Prozedur WEGE mit Hilfe des
Warshall-Algorithmus zu entwickeln.