\ Prifungstsilnskauer Prüfungstermin Einzuiprüfungsnunner nn HERBST = 1987 Arbeitszlatz-Nr.: 46111 Erste Staatsprüfung für ein Lehraat an Sffantlichen Schulen ‘« Prüfungsaufgaben - te Informatik (nicht vertieft studiert) ch; EBinzelprafme: Programmentw./Systempr./Datenbanksys. - a Anzahl de> gestellten Thamen (Anfgaben): 1 © Anzahl der Druckseiten dieser Vorlage: 5 bitte wenden! i” Prüfungstermin: Herhst 1987 - Seite 2 - Einzelprüfungsnummer: 46111 Sämtliche Teilaufgaben sind zu beantworten! Teilaufeabe 1: Programmentwicklung Ein bekanntes Verfahren fir die Verteilung der Sitze nach einer Parlamentswahl ist das D'Hondtsche Höchstzahlverfahren. Dabei werden die erzielten Stimmenzahlen der Reihe nach durch die natürlichen Zahlen dividiert: Divisor Stimmenzahlen 1 14173 x .173147:.x . 1829 x 2 . 73586,5 x 86373,5 x 9149,5 @ @ 3 49057,7x ° 5715,7x 4 36793,3 x 43286,8 x 5 29434,6 x 34629,4 x 6 24528,8 x 28857,7 x 7 21024,7 x 24735,3 x - a 19396,6 x 21643,4 x 9 16352,6 x 19238,6 x 10 14717,3 17314,7 x 15740,6 Sind N Parlamentssitze zu vergeben, so werden diese den N höchsten Zahlen dieser Matrix zugeordnet. Sind beispielsweise 20 Sitze zu vergeben, so sind also die „ größten Zahlen herauszufinden. Im Beispiel sind diese mit x markiert. Dort ent- @ @ 1. auf die Partei der ersten Spalte 9, auf die der zweiten 10 und auf die der dritten 1 Sitz(e). | Die Abbildung zeigt ein Diagram zur Gliederung des Programms. Schreiben Sie das Programm in einer beliebigen Programmiersprache! (Geben Sie an, welche!) Schreiben Sie dabei für jede der vier Teilaufgaben eine selbständige Prozedur, wo‚bei die im Diagramm eingetragenen Daten als Parameter auftreten und - außer diesen keine Größen gemeinsam benutzt werden sollen! Fortsetzung nächste Sera! Fortsetzung nächsis Seit ‚Do ©” Auswertung eines Wahlergebnisses Am m m Input Stimmen je Partei i > | PS Gesamtzahl der Sitze N Tg, Errungene Direkt mandate je Partei Process Output Stimmen summieren \ Prozentanteile bestimmen AN Sitze äuf die Parteien verteilen Direktmandate Z| subtrahieren IN GUItige Stinmen - Prozentuale Stimmenvertei lung Sitzverteilung Sitzverteilung nach. Direkt- Und ListenMandaten Einzelprüfungsnummer Prüfungstermin: Herbst 1987 - Seite 3 - 46111 Prüfungstermin: Herbst 1987 ~ Seite 4 - Einzelprüfungsnummer: 46111 Hinweis: a) Zur Vereinfachung sei angenommen, daß in der Matrix keine Zahl doppelt, - auftrete und keine sog. Qberhangmandate entstehen (mehr Direktmandate als die Sitzverteilung ergibt). b) Eine elegante Lösung umgeht die Speicherung der Matrix. Teilaufgabe 2: Systemprogremmieruna INS Seit ALGOL 50 verlangen die meistan Programmiersprachen vom Betriebssysten einer Rechenanlage eine dynamische Speicherverwaltung. Dabei sind verschiedene @ Gesichtspunkta zu unterscheiden: eae g x - Die Blockstruktur führt zu einer pulsierenden Speicherverwaltung. — - Zeiger-Konzeste (Beispiel: PASCAL) Führen zu einer sog. Halde. Pen Während sich dies auf die Verwaltung des Speicherbereichs eines Programmes bezieht, entstehen für das Batriebssystem weitere Aufgaben aus der Tatsache, daß sich im Rechner mehrere Programme (Prozesse) gleichzeitig befinden. Um bei der Pragrammierung der Einzelprogramme darauf keine Riicksicht nehmen zu müssen, verwendet man einen virtuetlen.Speicherraum, dessen Adressen vom Betriebssystam (mit Hardware-Unterstützung) in reale Adressan umgesatzt werden. Beschreiben Sie ! un ans ® “pes armen ie A u Ms fe a) die auf ein Programm bezagene Speicherverwaltung, die auftretenden Probleme und möglichen Lösungen! Vergessen Sie insbesondere nicht den Fall von Sprunganweisungen, die aus Blöcken hinausführen, ee AN b) die Speicherverwaltung auf der Basis einer Seiten-Kachel-Tabelle! woe Tee 1 Fortsetzuna nächste Seite! Prüfungstermin: Herbst 1987 - Seite 5 - Einzelprüfungsnummer: 46111 fu. ' f POLL rad In Te ri gel, Nun i / de: Teilaufcabe 3: Datenbanksysteme N un.) Lot Das Verwalten eines dynamischen Datenbestandes, d.h. einer Ansammlung vonN. , BE I N . Informationen, die durch Einfügen neuer Daten wachsen und durch Löschen : . . \ , schrumpfen kann,und in der bestimmte Informationen gesucht werden, steht und fällt mit einer möglichst optimalen Struktur des Datenbestandes. Definieren und erläutern Sie Vor- und Na teile bzgl. der oben unterstri chenen Operationen bei Verwendung folgender Strukturen: a) binärer Baum, : ses N i My b) balancierter bingrer Baum, Deft. 7 “ . c) Bayer-Baum. o Die zuletzt genannte Struktur hat eine besondere Bedeutung, wenn der Datenbestand so groß ist, daß er nicht mehr im Arbeitsspeicher gehaltan werden kann. Erläutern Sie die Organisation eines Datenbestandes als Bayer-Baum bei Verwendung heute üblicher peripherer Speicher! \ 1 “2 \ ' m 5 a Pr ” N On 2, Alte. ad COTS en, fa} u ’ , = r en > , = a a ‘ NS RG \ _ j ose Cyt lat INN Tay coe i nn Bi \ _ . F , 4 f BART wo pos “Ek _. - = - S ~ nee , _ a \ fa \ . & 1 ve) _ a Tyre - ur par = | r Din so ~ a ° ~ = vote eh ODE _ on ride a I. il \ \ As a N Ul ; Ilse‘ , pou SOTO . ne . Fr WSs ue bo rare Poot elle 3 Alta Ami hos you coy DI > . ce Love eu i aga Sd oe In ıla wi Vy i aay, N) mi aS te ANA RAS - Vea AMS a i ‘ ! N _—- ’ ! oa _— - } - \ ysis