Prüfungsteilnehmer Prüfungstermin Einze \lifungsnummer
—_ FRÜHJAHR 46111

1990

Arbeitsplatz-Nr.:

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

- Prüfungsaufgaben -

Pach: Informatik (nicht vertieft studiert)
ZBinzelprüfung: Programmentv./Systempr./Datenbanksys.
a Anzahl der gestellten Thanen (Aufgaben): 1
Anzahl der Druckseiten dieser Vorlage: 2

Aufgabe

(Oe x - 4 Z eo

Es soll eine "geschlossene Rechenstrukrur far "geardnete Binärbäume über den ganzen
Zahlen Z entwickelt werden. Dabei soll die Ordnung in einem Binärbaum B
folgendermaßen festgelegt sein: Sei k ein Knoten von B, L(k) bzw. R(k) der linke
bzw. rechte Unterbaum von k in B und I(k) die zu k gehörige Zahl aus Z; dann gilt:

(Vice BY((Wkye L())(1(q) <T(k)) a (Wk, RKC) <1k,))). Dual 27
Aus dieser Festlegung folgt zugleich, daß die I(k) in B paarweise verschieden sind.
Schließlich ordnen wir jedem Binärbaum B in der üblichen Weise seine Höhe b(B)
durch folgende rekursive Definition zu: Ein leerer Binärbaum hat die Höhe 0, und die
iGhe h(B) eines nichtlleeren Binärbaums B mit der Wurzel w ist
h(B):=Max{h(L(w)),b(R(w)) +1.
Als Höhe h(k) eines Knotens k von B bezeichnen wir (wieder wie üblich) die Höhe des
Unterbaums von B, dessen Wurzel k ist.

a”

& Geben Sie in PASCAL-Notation eine geeignete Datenswukrur (durch entsprechende Deklarationen) an, mit der geordnete Binärbäurme mir den oben angegebenen Festlegungen dargestellt werden können! Die Knoten sollen dabei sowohl
ihre zugeordnete Zahl aus Z als auch ihre Höhe enthalten. Als Anker eines
nichtleeren Baums soll ein Verweis (pointer) auf dessen Wurzel dienen; ein leerer
Baum soll durch einen mit nil besetzten Verweis als Anker dargestellt werden.

Bevor Sie mit Teilaufgabe b) beginnen, überprüfen Sie, ob die angegebene
Datenstruktur für eine möglichst effiziente Durchführung aller in b) geforderten
Operationen geeignet ist, und begründen Sie Ihre schließliche Wahl der Datenstrukrur im Hinblick auf die in b) vorgesehenen Operationen i) - ni).

Fortseizuna nächste 5
Prüfungstermin: Frühjahr 1990 - Seite 2- ° Einzelprüfungsnummer: 46111 3

b)

i _ EN 4 “
InsTo Ag ~ yokes.

Entwickeln Sie systematisch PASCAL-Prozeduren (bzw. -Funktionen) für die folgenden 6 Operationen an geordneten Binärbäumen! Dabei darf für die OperaGonen unter ii) ~ vi) vorausgesetzt werden, daß der jeweilige Binärbaum durch
kreiere eingerichtet wurde, und daß er bei Aufruf der jeweiligen Operation die
oben angegebenen Integritätsbedingungen (Festlegungen) erfüllt, d.h. daß.er in
der festgelegten Weise geordnet ist, und daß die Kiöker in den Knoten entsprechend der Definition korrekt eingetragen sind. . :
i) = kreiere(t)
Diese Operation richtet einen leeren Binärbaum ein und weist dessen Anker
der Variablen t zu.
ii) leer(t)
Diese Operation ist als eine Funktion darzustellen; sie liefert den Wahrheits“wert tue, wenn der Binärbaum mit dem Anker t leer ist; anderr gen: liefert
die Funktion den Wert false. 1
iii) enthalren(z,t)
Diese Operation ist als eine Funktion darzustellen; sie Hiefert den Wahrheitswert true, wenn der Binärbaum mit dem Anker t einen Knoten mit der Zahl
zeZ enthält; andernfalls liefert die Funktion den Wert false.

iv) speichere(z,t)
Diese Operation fügt in den Binärbaum mit dem Anker t einen Knoten mit
der Zahl zeZ ein, falls der Binärbaum noch keinen Knoten mit z enthält;
andernfalls bleibt der Binärbaum unverändert. Der resultierende Binärbaum
muß wieder die Integritätsbedingungen erfüllen; sein Anker muß an t zugewiesen sein.

v)  loesche(z,;t)

- Diese Operation entfernt den Knoten mit der Zahl ze?" aus dem Binärbaum
mit dem Anker t, falls der Binärbaum einen solchen Knoten enthalt; andernfalls bleibt der Binärbaum unverändert. Der resultierende Binärbaum
muß wieder die Fategritätsbedingungen erfüllen; sein Anker muß an t

zugewiesen sein. vo het os,

vi) avi(t)

Diese Operation ist als eine Funktion darzustellen; sie liefert den Wahrheies.
wert true, wenn der Binärbaum mit dem Anker t ein AVL-Baum ist; andernfalls liefert die Funktion den Wert false. es

Migr sf

“

Come
c=
ss

®8