Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer I Kennzahl: FRÜHJAHR 46112 Kennwort: 1990 Arbeitsplatz-Nr.: Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen - Prüfungsaufgaben - Fach; Informatik (nicht vertieft studiert) Einzeiprüfungs Grundlagen der Informatik Anzahl der gestellten Themen (Aufgaben): 1 Anzahl der Druckseiten dieser VYorlage: 4 Bitte wenden! i Prüfungstermin: Frühjahr 1990 - Seite 2 - Einrelprüfungsnummer: 46112 Sämtliche Teilaufgaben sind zu bearbeiten! Teilaufgabe 1 Er Gegeben sei die folgende Funktionsprozedur in PASCAL-Notation: \ oe u so . Ki < SEN u” FUNCTION f(n: NAT): NAT; EN BEGIN IF n<=1 THEN f:=1 . I ELSE f:= f{in-1)+2*f(n-2) , ! . END; - Dabei sei die Art NAT durch TYPE NAT = {INTEGER 2:2 >= 0} definiert. ¢ 1.1 Zeigen Sie, daß fürn >=0 gilt: “sf nti _ (-1)1 fed ~ f(ay= Hh Las $ veo 1.2 5 a) Schreiben Sie eine rekursive Funktionsprozedur für eine Funktion a:NAT- NAT, die folgender Spezifikation genügt: a(n) gibt die Gesamtzahl der Aufrufe von f für f(n) an! b) Vergleichen Sie die Folge A= {a(n}},_,12,... mit der Fibonaccifolge F= {1,1,2,3,5,...} und beweisen Sie, daß A eine Majorante von F ist! 1.3 Schreiben Sie eine rekursive Funktionsprozedur q:NAT— NAT ‘ für die Funktion q(n) = 2". Die Aufrufkomplexität von q soll O(log n) sein! 24 Schreiben Sie unter Verwendung der Funktion g (aus Teilaufgabe 1.3) eine Funktionsprozedur für eine Funktion / g9;NAT— NAT, die sich nicht selbst aufruft und den gleichen Wertverlauf wie f hat! Fortsetzung nächste Seite! - Prüfungstermin: Fri hr 1990 - Seite 3 - Einzelprüfungsnumner: 46112 Teilaufgabe 2 Gegeben seien die folgenden Arten (in PASCAL-Notation): TYPE name = ARRAY(1..20] OF CHAR; \. datum = 18000101..19991231; os ch a liste =1 eintrag; ie \av ou eintrag= RECORD n: name; , gebtag: datum; nert: liste END; Hierbei stellt ein Objekt der Art datum als 8-stellige Zahl jijojajamimotit, das Datum tite.mym2jijojsjs dar; z.B. steht 19880917 für das Datum 17.9.1988. Zu beachten ist allerdings, daß nicht jedes Objekt der Art datum sinnvoll interpretiert werden kann; z.B. sind en 18771405, 19010547 und 19890229 nicht interpretierbar, weil es die entsprechenden Daten u nicht als Tagesdatum gibt. Sei nun personal eine Variable der Art liste. Die Variable personal verweise als Anker auf eirenicht-zyklische, einfach verkettete Liste von Objekten der Art eintrag. Entwickeln Sie eine geschlossene Rechenstruktur, die es erlaubt, einen sortierten Binarbaum als Zugriffsindex, nach Geburtsdaten geordnet, auf die mit personal bezeichnete Liste aufzubauen! Die _Personalliste soll dabei unverändert bleiben, und es darf nicht angenommen werden, daß So Personaldatei enthalten. Im einzelnen ist für diese Aufgabe folgendes zu leisten: sie geordnet wäre. Der sortierte Binärbaum als Zugriffsindex soll keinen Namen aus der 2.1 Legen Sie die Datenstruktur für den aufzubauenden sortierten Binärbaum fest! nn en 2.2 Schreiben Sie eine Prozedur einf, die ein Element in den sortierten Binärbaum so einträgt, daß die Zugriffsbedingung (geordnet nach Geburtsdaten) auf personal beachtet wird! a 2.3 Schreiben Sie eine Prozedur aufbau, die unter Verwendung von einf (aus Teilaufgabe 2.2) einen sortierten Binärbaum aufbaut. Dieser Baum soll der Aufgabe entsprechend als Zugriffsindex für die gegebene, mit personal bezeichnete Liste verwendet werden! 2.4 Schreiben Sie eine Prozedur gibaus, die mit Hilfe des aufgebauten Binärbaums alle Einträge aus der Personalliste zu einem vorgegebenen Geburtsdatum heraussucht und die zugehörigen Namen ausdruckt! Falls die Liste keinen Eintrag mit dem gegebenen Geburtsdatum enthält, soll der Hinweis ‘kein Eintrag’ ausgedruckt werden. 7 / A SE Cue Früfungstermin: Frühjahr 1990 - Seite 4 - Einzelprüfungsnummer: 46112 } Teilaufgabe 3 Gegeben sei das Alphabet A= (a,b,c,z,y). Für eine Sprache $ über A seien die relativen Haufigkeiten, mit denen die Zeichen aus A auftreten, durch folgende Tabelle gegeben: ° 41% 19% 10% 23% 7% fe Ra SA Betrachtet wird die folgende Binarcodierung C; für A: & oO „jb: LOL a= x 120 Lo > € y : LLL Fu 2.1 Bestimmen Sie die mittlere Codewortlänge von C, für die oben angegebenen relativen Häufigkeiten! 3.2 C, erfüllt die Fano 0-Bedingung "und ist daher eindeutig decodierbar. Geben Sie unter Verzicht auf die eindeutige Decodierbarkeit eine Binärcodierung C, für A an, die hinsichtlich der mittleren Codewortlänge optimal ist! 3.3 Bestimmen Sie die mittlere Codewortlänge von GC; ! 2 sent I 3.4 Die Codierung soll hinsichtlich der mittleren Codewortlänge gegenüber C, durch folgende Maßnahme weiter verbessert werden: . Das Buchstabenpaar aa soll durch ein eigenes Codewort dargestellt werden, d.h. betrachtet wird das Alphabet 4’ = (a1,a,,b,c,z,y) mit folgender Maßgabe: c a, steht für a und a, für ein Paar aa in unmittelbarer Folge. Jede Zeichenreihe x über A läßt sich dann offenbar (wenn auch nicht eindeutig) durch eine Zeichenreihe z’ über A‘ so darstellen, daß die ursprüngliche Zeichenreihe z eindeutig wiedergewonnen werden kasr und in z’ kein Paar a,a, in unmittelbarer Folge auftritt. z.B. istz = zabbaaaaae durch zı = zaıbbara;a,c, aber auch durch 2; = za,bbaza,a,c und durch Z5 = 2a,bba,420.¢ darstellbar. 3.4.1 Bestimmen Sie die relativen Häufigkeiten für die Zeichen von A’ entsprechend der oben angegebenen Tabelle! - 2.4.2 Geben Sie eine hinsichtlich der mittleren Codewortlänge optimale Binärcodierung für A' unter Verzicht auf eindeutige Decodierbarkeit an! 2.4.3. Bestimmen Sie die mittlere Codeworzlänge von A’ sowie die mittlere Codewortlänge für die dadurch gegebeze Binärcodierung von A!