Prüfungsteilnehmer

Prüfungstermin

Einzelprüfungsnummer

Kennzahl:

Frühjahr
Kennwort:

2000

46114

Arbeitsplatz-Nr.:

Erste Staatsprüfungfür ein Lehramt an öffentlichen Schulen
- Prüfungsaufgaben -

Fach:

Informatik (nicht vertieft studiert)

Einzelprüfung:

Algorithmen/Datenstrukt./Progr.-meth.

Anzahlder gestelltenThemen(Aufgaben): z
Anzahlder DruckseitendieserVorlage:

5

Bitte wenden!

Frtihjahr 2000

Einzelprüfun-esnumm
er: 46L14

Seite:2

Thema N-r. L
Sämtliche Teilaufgaben sind zu bearbeiten!

Teilaufgabe1:
ReaiisierenSiein einerimperativenSprachetrrer Wahl denTyp der gr','s11Zahlenals 2-Tupel
die das
ihresabsoiutenBetrages(Typ CARDINAL für INo) und einerBOOLEAN-Komponente,
Vorzeichenangibt!
Addition,
GebenSie für die so dargesteiltenganzenZahlen Prozedurenfür die Grundrechenarten
Operationenauf CARDINAL verwenden!
Subtraltion und Multiplikation an, die die entsprechenden
Teilaufgabe2:
Jemandgibt nachfolgendenAlgorithmus vor.
AnalysierenSie dessengenaue,teilweise ,,unerwartete"Wirkung !
1 Y P t sL r S E e = r u t N l t j 1 l U l t e & ;
: CAF,DINAL;
Elen = REC0RDobj
END;
nachf : Liste
UBbekamt (1: Liste; a:CARDINAL);
PRoCEDURE
VAR y : Liste;
BEGlN
I F I = N I L T H E NN E I i ( y ) ; y . , o b j : = a ;
Y-.!.acb.f := NIL;
1 := Y
(
a
<
l
.
o
b
j
)
N
i= ai
THEN E!l(y); y-.obj
ELSE IF
'
D
a
c
h
f
;= 1;
Yy
1 ;=
END
END
END Urbeka!-st

Teilaufgabe 3:
SchreibenSie ein hogramm in einer imperativenSpracheIhrer Wahl, dasdie Inverseeiner (einzulesenden)2x2-Matrtx reeller Zahlenberechnet(und ausgibt), falls die Matrix invertierbar ist und
:rnsonsteneine Fehlermeldungausgibtt Eine Matrix der r"tm ( i ! ) ist lnvertiertar, falls
'gilt:
ad.- bc +0 und die lnverselautetO.oo (
{n ), *otel *lt O = ad'- bc Qeterrruswrte)
\ I

l '

o e= *
.I=_ti

. s=i
c h= *

-3: 461L4
Eirzelprüfungsnufirmer

Frühjahr 2000

Seite:3

Thema Nr. 2
Sämtliche Teilaufgaben sind zu bearbeiten!

Teilaufgabe1: Programmiermethodik
(1a) Ein typischesStrukturierungsmodellbei der Programmentwicklungist
die schrittweiseVerfeinelung.li/as verstehtman darunter?
(1b) Eine Form, die schrittweiseVerfeinerungil der Praxis auszunutzen,besteht in der
Aus welchen
Verwendungder Struktogramme (Nassi-Shneidermann-Diagramme).
Elementensind diesezusammengesetzt?
uqterscheidendrei Tlpen von Schleifen:
(1c) Die gängigenProgrammiersprachen
- die indizierende
Schleife: for Var := Exprl to Expr2 do ...
- die abweisende
iterative Schleife: vhile LogExpr do . ' .
- die nichtabweisende
iterative Schleife: repeat ... uatil LogExPr
Wie unterscheidensich diese Schleifentypen?(Erläutern Sie die Abarbeitungsweise und gebenSie typische Randbedingungenfür den Einsatz der unterschiedlichen
Typen an.)
iterativen Schleifedurch
(1d) In der Hoare-Semantikkann die Wirkung der abweisenden
folgendeFormel beschriebenwerden:
B^P

{S}

@

P

Formel
Erläutern SiedieseFormeianschauiich,und entwickelnSieeineentsprechende
iterative Schleife!
für die nichiabweisende

Teilaufg abe 2 z Systementwurf
Softwaresystemenist
Ein aktueiles Thema in der Diskussion um die Strukturierung von
die Objektorientierung.
Erläutern Sie die Begriffe Klasse, Objekt und Methode unter Zutrilfenatrme des folgenOa\
\ /
den (in einer Phantasiesplacheformulierten) Beispiels:
class konto 1s
(kr:nde) ;
eroeffne-konio
einzahlen (betrag);
auszahlen (betrag);
kontostand
end konto;
(uetrag

O returns

betrag;

man unter Inund kunde seien geeignet definierte Klassen.) Was versteht

stanzenvariabien?

Fortsetzung nächste Seite!

Frühjahr 2000

Einzelpruftrngsnummer
: 46IL4

Seite:4

(2b) Das Beispielwerde durch die folgendenDefinitionen ersänzt:
class girokonto inherits fronr konto
setze_dispo_lirnit (betrag);
dispo-limit O returns betrag;
^-

l

eIIlJ

+.i

5rr

+al.^-l

a

.

U5.UI1 t/Lr,

class sparkonto inherits from konto
setze_zinssatz (real) ;
schreibe_zinsen_gut O ;
end sparkonto;
Eriäutern Sie den Begriff der Vererbung, und geben Sie die vollständigeListe der
Methoden an, die für Objekte der Klassen Girokonto und Sparkonto definiert sindl
(2c) Was versteht man unter einer virtuelien Ftrnktion? (Hinweis: In unserem Beispiel
könnte man auszahlen als solcheauffassen,da sie bei Girokontenzu einemnegativen
Saldo führen darf, bei Sparkontennicht.)
was man unter,,dynamischem
(2d) Erläutern Sie an Hand. der virtuellen F-\-rnktionen,
Binden" versteht, und dessenVorteil bei der Systementr,vicklung!

Teilaufgabe 3: Ngorithmen und Datenstrukturen
Beim Heapsort-Verfahrenstellt man sich vor, die in einer Reihung (array) gespeicherten
Daten seienals Baum organisiert. Beispielsweisedenkt man sich die Reihrrno

7 A , ,79 ,5 ,6 ,B ,3 , 7 , 24,
in der folgendenForm gegeben:

/ \

2

4

(3.) Wann nennt man einen Baum einen ,,Heap"?
(3b) BeschreibenSie das Einfügen eines neuen Eiementes in den Heap!
(3c) Wie ist der Heap zu reorganisieren,wenn das größte Eiement (d.h. das Element an
der Wurzel) entfernt wird?

FortsetzunenächsteSeite!

Frütrjatr2000

461t4
Einzelprüfungsnufirmer:

Seite:5

Teilaufg abe 4: Anwendungen
VerwendenSiedie dem HeapsortzugrundeliegendeIdee, um eineListe von einzuhalienden
Fristen (Terminen) effi.zientzu verwalten:
Der Zugriff auf den ais nächsteszu bearbeitendenVorgang (d h. die nächsteabiaufende
Frist) soil in konstanter Zeit mög1ichsein.
Das Streicheneiner abgeiaufenen(bearbeiteten) Frist und das Neueintragen sollen
in logarithmischerZeit möglich sein, also nicht das Durchsuchender gesamtenListe
erfordern.
(ar) Begründen Sie, warum die Heap-Struktur diese Anforderungen erfüilt, wobei als
Sortierkriterium das Datum des Fristablaufs verwandt wirdl
(4b) Es kann vorkommen, dass sich eine Frist vorzeitig erledigt. Welchen Aufwand erfordert es, eine solcheFrist zu streichen?(Beachten Sie, dass Sie sie zuerst suchen
müssen,wobei Sie selbstverständlichnur das Aktenzeichenkennen!)
(ac) BeschreibenSie eine andere Datenstruktur, bei der das Suchenund Eintragen von
Vorgängen(Sortierkriterium: Aktenzeichen)in logarithmischerZeir möglich ist! (Es
gibt verschiedeneLösr'''oPn)