l{x

a.
I

J

nrätusstetlaebe=

gn*ag8te=o!r

laanzeblr

HERBST
l9E9

tcnarorür
lrbeltapletz-f,r.

Ergte

Elarcl@

I

Startepnlnlag

ffs

sl.a tr€bragt

aa öf,felrtl:lchar

tiEcbr Informatik (nicht vertieft

L

studiert )
ElazclprAfunsr Betriebs/Datenbanksyst., Rechn.architektur
fazehl dsr guatellteq
Ebsnca (fufgpbea) I I
fazehl

de= lnret sel,to

d.lcrer

vorla6ur

66nl

6

bitte wenden!

8ohnlo

termin: Herbst I9g9

Seite 2

- i n z e l rüfun snummer:66'ill

Sämtliche Teilaufeaben sinä zu bearbeiten!

Teilaufgabe I
Für eiaeu endlicheu niüt-leeren Zeic.henvorratZ sei eine Binärcodierung

c zZ - { O , L I *
gegeben
1.1 Geben Sie eine Datensiruktur (durch Tlpdefinitioneu) *, mit dereu Hitfe ein
beliebiger Binärcode c im Hinblick auf die folgende Teilaufgabe L.2 geeignet
dargestellt werdgs ltann.
L.2 Schreibeu Sie eine F\rnktiousprozedur fano, mit deren Hitfe festgestellt werden
kanu, ob eiu Binärcode c der FanoBedi''gung geuügt. Die F\ruktionsprozedurfano
soll ddbei folgeuder Spezifikatiougeuügeu:
1.2.t Eingabeparameter: c vorn l)rp CODE

-

1.2.2 Der F\rnktioaswert ist von TJrp BOOLEAN und hat deu Wert
genau de'n, wenn c der Fano-Bedioguoggenügt.

TRUE

Hiuweise: - Der Typ CODE muß in Ihrer Antwort zu 1.1 definiert werden.
- Ein Code erfüllt die FaaeBedingung getrau dann, wenn in ihm kein
Codewort Anfaug einesvetr ihrn verschiedenenCodewortesist.
1.3.Der Zeicheuvorrat
Z - {o,b,c,d,e,f ,g,h,t, j} läßt sich durch Wörter aus {O,L}*
binäx codieren, öe höchstensdie Läage 3 habeu. Eiu Beispiel dafür ist durch
den folgeudenCode-Baum gegeben:

ZeigenSie,daß es keine &stelligeBinärcodierung(d.h. mit Codewortläuge
S 3)
fur Z grbt, die die Fano-Bediagung
erfüllt.

Fortsetzunq nächste Seite !

C

Ftüfun t e r m i n : H e r b s t 1 9 8 9

Seite 3

EinzeI rüf

snummer:66111

Teilaufgabe 2
Zeichenreihenüber dem endlichenAlphabet Ä = ('a','ö', . . .
,'"') sollen durch vorwärts
und rückwärts verkettete Listen dargestellt werden, für deren Anfang und Ende Anker
(Verweise) vorgesehensüd. Die Da^rstellnngder Zeicheureihe z!='obc' läßt sich aJso
beispielsweisefolgendermaßeugraphisch veraü;chaulicheu:

(:

2't Geben Sie eine Datenstruktru mit Hilfe geeigueterT!'pdefinitionen an durch
die
r
sich die o.a. Darstelluug von Zeichenreihenrealisislst läSt.
2-2 Wie kann die leere Zeichenreihee dargest,eltt urerden?
2'3 SchreibenSie eine F\rnktionsprözedurdstepsilon, die feststellt, ob eine Zeichenreihe
gleich e ist, dso folgender Speziflr"tion geuügt:
2-3.1 Eingabeparameter: s! vom $p LEICEENREIHE
Hinweis: ZEICHENREIHE muß als ryp in Ihrer Antwort N 2.1 definierr
sern.
2.3.2 Der F\rnktionsnrertist vom T).p BOOLEAN nnd ist genau da,,n
gleich
TRUE, wenn el = e ist.

Fortsetzunq nächste Seite !

rüfunqstermin: Herbst 1989

- Seite 4 -

56IJr'
Einzelprü funqsnummer:.

L

2.4 Scüreiben Sie zwei t\nttionsprozeduren azlazg uod ter'|, die feststellen, ob
z Ada.ugs- bzw. Teilzeicbenreiheeiner Zeicbeueibe y ist. Die entsprechenden
Spezif,Latioaenlauten:
.

(fir beide l\raktionsprozedurer): s,y vom TW ZEI'
2.4.1 Eingabepa,ra:creter
CEENREIEE
2.4.2 De.t F\alilionswert ist jeweils vom Tlp BOOLEAN. Er hat der \üerü
TRUE trt die [\nltion anlang bzw, üeil geaau dau, wenn c Anfangs
bzw. Teilzeichenreihevon y ist.
Hinvrise: - a ist genaudann lsfasgs2eichenreihevorr gr,werures ein g/ so
gibt, daß g=zl ist'
- z ist gelau da,ur TeilzeicheoreihevoD y, wenD es eia y' uud
'sr.
eia /' so dbt, daß y=g!x{
Es ist empfeblensbert,erst die F\n&tionsprozedur anfang nt
C
sch$iber uad dana ia der Funltiousprozedur teil die l\aktion
anlaag zu verwendeu.Dabei darf auö die in 2.3 spezifizierte
F\uktion istepsiloavrrwendet werden.
2.5 Ein Paliadrom ist eire Zeichenreihe,öe mit ihrer rüc.kwärtsgeleseneuidentisch
ist. Beispielesind
' dto','relie p eiler', e (leereZeicheueibe).
t f
Sc.hreibenSie ehe !\raltioasprozedur palin, öe feststellt, ob eiae Zeichenreiheein
Palhdrom ist, also folgenderSpezifrkatiorgeaü6:
2.5.1 Eingabepara,lreter:cl vom'typ ZEICHENREIHE
2.5,2 Det trhattionswert ist vom TW BOOLEAIY und ist geuau 6an" gleich
?BtlE,.weu cl ein Palhdron ist.
Hinweis:In der l\ütionsprozedur golin d,ttf die unter 2.3 spezifizierte
l\aktion ittepsiloa verwendetwerden.

-

Fortsetzunq nächste Seite !

I
l

'

J

J

a
t

Prüfu

termin: Herbst 1989

Seite 5

rü fun

Teilaufgabe 3
Ein endlichergerichteterGraph C = (V,^E) Eit der Kaotenmeuge V =
{rr tt)2,.. . , ür}
uurxd
der Menge gericbteterKanten E g V xV lc^nnu.a. durch seineaitelte graphische
Darstellung und druch seine Adiazenzmatrix dargestellt werden. Ein Beispiel:

Dieser direkt da.rgestellte
Graph mit v - {q, o2tn3,aaral} und E - {(rr, ,s); (rr , ,l
),
(oz,ot), (rg, az),(aq,u3),(rs, rl), (rl, os)) tagt sich auch durch seine
Adjazenzmatrix

A_

fülil)

darstellen. Allgemein gilt ffir die. Komponentea aij der Adj azerwnatrix
A:
"dt =

( 1 fallc es eine Kante von
ü; ''*'r
nach ai glbt
''r
t;
sonst

Hat ein gerichteter Graph die Eigenschaft, daß von wenigstens
einem Knoten zwei
gerichtete Kanten und rrcn keinem Knoten mehr als zwei gerichtete
Kanten ausgeheu,
so sagt tDan, daß er den Verzweigungsgrad
2 hat. Der angegebeueBeispiel-Graphhat
also den Verzweiguugsgrad2. SotcUeöraphen könuen in d,irekter
Darstellung durch
eioen Verweis auf ein Geflecht von Verbunden der Art knoten
eutsprecheudfolgeuder
TlpVereiubanurg aufgebaut werden:
TYPEgt'aph=Thnoten;
kzoten = RECORD
hholt: INTEGER;
nachfl, nochfZ: groph
EITD;
Mit
g:
YAR gnapä sei DuD eine Variable gegeben,die aui eiaen endlichen gerichteten
Graphen mit n Ksoten usd mit verzweig,-gtgr aÄ 2 vtrrreist.

Fortsetzunq nächste Seite !

Prüfungstermin: Herbst 1989

Seite 6

c -

$

.

Einzelprüfungsnummer
: 66Lll

3.1 Geben Sie einen termiaierenden Algorithmus tn, der die .F'djazewmatrix von g
berechnet.
Hinweis: Es wird nicht verlangt, dd dafür ein Progra'r,'r, geschriebeuwird; der
Algorithmus soll aber kla^rund korrekt beschriebeuwerdeu.
3.2 Als Wegematrix W zu einem endlichen gerichteten Graphen G bezeichnet man
die Matrix, die dnrch ihre Komponente ur;1 argibt, ob es in G einen gerichteten
Kantenzug von u; nach.ul gibt. W - (r;i)rSi;S" ist also folgendermaßendefiniert:

,r, =

t ä ffir.t

gerichteter
vonu; nachai existierü
Kantenzug

Zu dem o.a Graphen ist beispielsweise

W=

( ir l l 3 )

Lililri

C

die zugehörige\üegematrix.
Schreiben Sie eine Prozedur ucg, die zur Adjazeuzmatrix A eines endlichen
gerichteten Graphen mit n Kuoten uud m.it ei"em beliebigeu Verzweiguugsgrad
(S n) die Wegematrix W berechnet. Die Prozedur ueg soU also folgeuder
Spezifikation geuügen:
3.2.1 Eingabeparameter:Adjazeuzmatrixo vorn T).p ARRAY[I
..n,7...nlOfO..t
3.2.2 Ausgabepareyneter:
lVegematrixur von Tlrp ARRAY[I
..n,l..n]Of O..f
Dabei soll u, die Wegematrix zu dem durch a dargestellten gerichteten endlichen Grapheu sein"

t

.t