Prüfungsteilnehmer Prüfungstermin Einz jüfungsnummer

Kennzahl:

Frühjahr
Kennwort: 461 1 1
1999

Arbeitsplatz-Nr.:

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

- Prüfungsaufgaben -

Fach: Informatik (nicht vertieft studiert)
Einzelprüfung: Programmentw./Systempr./Datenbanksys.
Anzahl der gestellten Themen (Aufgaben): 1

y

Anzahl der Druckseiten dieser Vorlage: 3

Bitte wenden!
Frühjahr 1999 Einzelprüfungsnummer: 46111 Seite: 2

Sämtliche Teilaufgaben sind zu bearbeiten!

Teilaufgabe 1: Programmentwicklung

Mit folgender Datenstruktur können in C doppelt verkettete Listen dargestellt werden:

struct Node {

hi

struct Node *left, *right; /* linker und rechter Nachbarknoten */
int prior; /* Prioritaet des Knotens */
info data; /* Knoteninhalt */

oder in PASCAL:

TYPE nodepointer = “node;

node = RECORD left, right: nodepointer;
prior: integer;
data: info
END;

(Der Datentyp in£o sei geeignet definiert.)

a)

b)

c)

d)

Der Zeiger currptr zeige auf ein Element dieser Liste, der Zeiger actitem auf ein neues
Element. Erläutern Sie mit Hilfe einer Zeichnung, wie die Zeiger umzusetzen sind, damit das
neue Element hinter bzw. vor dem durch currptr definierten eingefügt wird!

Schreiben Sie in der Programmiersprache Ihrer Wahl die entsprechenden Prozeduren
insertbefore und insertafter!

Sie wollen mit der angegebenen Datenstruktur eine prioritätengesteuerte Warteschlange implementieren. Bei einer einfachen Implementierung fügt insert das neue Element hinten (oder
vorne) an, und getnext durchsucht die gesamte Liste nach dem Element mit der höchsten Priorität und liefert dieses zurück. Führen Sie die Implementierung unter Verwendung der zuvor definierten Prozeduren aus!

Welche besseren Lösungsmöglichkeiten fallen Ihnen ein? Skizzieren Sie eine solche (ohne Implementierung!) und begründen Sie durch grobe Abschätzung der durchschnittlichen Laufzeit,
warum diese Lösung besser ist als die in der vorhergehenden Teilaufgabe beschriebene!

Fortsetzung nächste Seite!
Frühjahr 1999 Einzelprüfungsnummer: 46111 Seite: 3

Teilaufgabe 2: Datenbanksysteme

Das derzeit am weitesten verbreitete Datenmodell ist das Relationenmodell. Ein Miniaturbeispiel
könnte folgendes Aussehen haben:

|Name |Geb.dat. | Matr.nr. | Fachrichtung | Prüf.fach | Prüfer |Note |
Maier 12.03.74 | 234567 | Informatik Datenbanken Wedekind 1,7
Huber 11.02.75 123456 | Informatik Prog.sprachen Eickel 2,3
| Miller 14.04.76 | 345678 Elektrotechn. | Prozessrechner Färber 1,7
Huber 11.02.75 1123456 Informatik Theoret. Inf. Noltemeier {1,0

234567 Informatik Prozessrechner Farber 2,7

Maier | 12.03.74

a) Erläutern Sie die Grundstruktur! (Was versteht man unter Tupeln, Attributwerten, Schlüsseln?)

b) In eine Datenbank müssen häufig neue Tupel eingefügt bzw. aus ihr Tupel entfernt werden. AuRerdem können sich Arttributwerte in Tupeln ändern. Dabei sind Konsistenzbedingungen zu beachten. Was versteht man unter Domänenbeschränkungen, Schlüsselbeschränkungen und referenzieller Integrität?

c) Was versteht man unter Normalformen? Durch welche Bedingungen unterscheiden sich die erste, zweite, dritte Normalform vom allgemeinen Fall?

d) Transformieren Sie das Miniaturbeispiel so, dass es mindestens die Kriterien der zweiten Normalform erfüllt!