Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Herbst Kennwort: 46 1 1 4 2006 Arbeitsplatz-Nr.: Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen - Prüfungsaufgaben - Fach: Informatik (Unterrichtsfach) Einzelprüfung: Algorithmen/Datenstrukturen/Programmiermethodik Anzahl der gestellten Themen (Aufgaben: 2 Anzahl der Druckseiten dieser Vorlage: 5 Thema Nr. 1 Hinweis für die Aufgaben 1, 2 und 4: Verwenden Sie zur Formulierung von Algorithmen bzw. Datentypen eine gängige höhere Programmiersprache oder einen entsprechenden Pseudocode. Erläutern Sie Ihre Lösung ausgiebig durch Kommentare! Aufgabe 1 a) Realisieren Sie den Datentyp der Brüche als 3-Tupel bestehend aus dem Betrag des ganzzahligen Zählers, dem Betrag des ganzzahligen Nenners und einer Komponente, die die Zahl | für ein positives und die Zahl -I für ein negatives Vorzeichen des Bruches enthält. b) Geben Sie unter Verwendung einer gegebenen Operation für den größten gemeinsamen Teiler (ggT) eine Operation an, die für die so dargestellten Brüche die Addition zweier Brüche realisiert. Als Ergebnis dieser Operation soll wiederum ein Bruch (soweit wie möglich gekürzt) in der o. g. Darstellung zurückgeliefert werden. Fortsetzung nächste Seite! Herbst 2006 Einzelprüfungsnummer: 46114 Seite: 2 Aufgabe 2 Eine Prioritätswarteschlange (priority queue) ist eine Datenstruktur, in die Datensätze mittels einer Operation insert eingefügt werden können und aus der mittels einer Operation remove der Datensatz mit dem jeweils größten Schlüssel wieder ausgelesen werden kann. Vereinfachend kann davon ausgegangen werden, dass die Prioritätswarteschlange jeden Schlüssel nur genau einmal enthält. a) Geben Sie Implementierungen der genannten Operationen an, die folgende Eigenschaften erfüllen: Insert soll in konstanter Zeit erfolgen, remove in linearer Zeit (jeweils abhängig von der Zahl der Elemente in der Schlange). b) Geben Sie Implementierungen der genannten Operationen an, die folgende Eigenschaften erfüllen: Insert soll in linearer Zeit erfolgen, remove in konstanter Zeit (jeweils abhängig von der Zahl der Elemente in der Schlange). c) Geben Sie eine Operation changeMax an, mittels der die Priorität des Elements mit der höchsten Priorität auf einen anderen Wert gesetzt werden kann. d) Mittels der unter a) und b) realisierten Operationen lassen sich leicht zwei bekannte Sortierverfahren nachbilden. Erläutern Sie, um welche Verfahren es sich hierbei handelt. Aufgabe 3 Für den Gastronomiebereich soll ein Verwaltungssystem objektorientiert entworfen werden. Folgende Zusammenhänge sollen umgesetzt werden: In einem Gastronomiebetrieb arbeiten mehrere Kellner. Zu jedem Kellner werden dessen Personalnummer, Name und Vorname erfasst. Jeder Kellner ist während seiner Arbeitszeit für mehrere Tische zuständig. Jeder Tisch hat eine eindeutige Nummer und eine kurze Beschreibung seines Standortes (z.B. „Saall, hinten rechts‘). Bestellungen von Gästen an einem Tisch werden zu einem bestimmten Zeitpunkt aufgenommen und untergliedern sich in mehrere Bestellpositionen. Alle bestellbaren Speisen und Getränke haben eine eindeutige Nummer, eine Bezeichnung und einen Preis. Wenn Gäste an einem Tisch bezahlen möchten, wird eine Rechnung erstellt. Diese enthält Informationen über den Namen und die Adresse des Betriebs, das Datum und die Uhrzeit, den Tisch, die einzelnen Rechnungspositionen und den im Rechnungsbetrag enthaltenen MwSt-Anteil. a) Erstellen Sie für die beschriebenen Zusammenhänge ein Klassendiagramm. Jede Klasse soll mindestens zwei Attribute und zwei Methoden enthalten und die im Text beschriebenen Zusammenhänge berücksichtigen. Spezifizieren Sie alle Attribute, Methoden und Beziehungen durch Angabe von Datentypen, Beziehungsnamen und -typen und ggf. Kardinalitäten. b) Erläutern Sie textuell und präzise, wie folgende Aufgaben mittels Ihres Klassenmodells bearbeitet werden können. Geben Sie dazu auch Pseudocode an. Ergänzen Sie Ihr Modell, falls erforderlich. 1. Erstellung einer Rechnung 2. Berechnung des Tagesumsatzes eines Kellners Fortsetzung nächste Seite! Herbst 2006 Einzelprüfungsnummer: 46114 Seite: 3 Aufgabe 4 Stellen Sie sich eine stark vereinfachte Straßenkarte vor! Die Straßen seien mit der Entfernung zwischen ihrem jeweiligen Start- und Zielpunkt beschriftet. Vereinfachend können Sie davon ausgehen, dass Straßen immer in Orten beginnen und enden. a) Geben Sie einen geeigneten Datentyp zur Realisierung der Straßenkarte an. b) Geben Sie einen Algorithmus an, mit dem Sie unter Verwendung des Datentyps aus Teilaufgabe a) die kürzeste Verbindung zwischen zwei Orten bestimmen können. c) Gehen Sie im Folgenden vereinfachend davon aus, dass die Entfernung zwischen zwei über eine Straße miteinander verbundenen Orten überall den gleichen Wert a betrage. Beweisen Sie für diesen Fall mittels vollständiger Induktion, dass Ihr Algorithmus immer den kürzesten Weg findet. Thema Nr. 2 Aufgaben zu Algorithmen und Datenstrukturen Teilaufgabe 1 (Graphen Gegeben sei der folgende gerichtete Graph mit einer Kantenbewertung (Netzwerk): Bestimmen Sie mit Hilfe des Algorithmus von Dijkstra die kürzesten Wege vom Knoten A zu allen anderen Knoten. Geben Sie dabei nach jedem Verarbeitungsschritt den Zustand des Arbeitsfeldes an. Fortsetzung nächste Seite! Herbst 2006 Einzelprüfungsnummer: 46114 Seite: 4 Teilaufgabe 2 (Binäre Bäume) 1. Zeichnen Sie einen binären Suchbaum mit den natürlichen Zahlen von l bis 15 und der Höhe drei! Ist das Ergebnis eindeutig? Begründen Sie Ihre Behauptung. 2. Geben Sie jeweils die Reihenfolge der Knoten an, wenn obiger Baum in (1) Inorder, (2) Preorder, (3) Postorder und (4) Levelorder durchlaufen wird. 3. Zeichnen Sie für jeden der obigen vier Fälle den resultierenden binären Suchbaum, wenn er ausgehend vom leeren Baum durch sukzessive Einfügeoperationen in der jeweiligen Reihenfolge ohne Ausbalancieren aufgebaut wird. Teilaufgabe 3 (AVL-Bäume) Gegeben sei die folgende Zahlenfolge: 120, 50, 70, 100, 90, 30, 80 Fügen Sie die Ziffern nacheinander in einen AVL-Baum ein. Notieren Sie jeweils sämtliche dabei notwendigen Zwischenschritte und das Endergebnis. Teilaufgabe 4 (Bäume) Gegeben sei ein binärer Baum 7’ mit Wurzel v. Die Teilbäume von v seien balanciert und es sei |b(v)| (Balance von v). Beschreiben Sie die Situation, bei der nach einer Einfach- oder Doppelrotation von v die Gesamthöhe von T nicht reduziert wird (Grafik). Teilaufgabe 5 Das Newton-Verfahren ist ein numerisches Verfahren zur näherungsweisen Bestimmung von Nullstellen einer Funktion f : R— R. Zum Startwert xo wird der Punkt (xo,flxo)) berechnet und die Tangente dieses Punktes bestimmt. Der Schnittpunkt der Tangente mit der x-Achse (z,,0) liefert einen neuen Punkt: (x,,f{x7)). Zu diesem wird wieder die Tangente bestimmt und erneut der Schnittpunkt mit der x-Achse berechnet, etc. Allgemein lautet die Iterationsschrift wie folgt: Man bricht das Verfahren ab, wenn die Nullstelle hinreichend genau bestimmt ist oder wenn eine obere Grenze für die Anzahl der Iterationsschritte n erreicht wurde. Ferner wird abgebrochen, falls für ein n f'(x,) = 0 und zugleich f(x,) # 0 gilt. In den beiden letzten Fällen ist die Nullstelle mit dem Verfahren in dieser Form nicht bestimmbar. Beispiel: f(x) = x — cosz Fortsetzung nächste Seite! Herbst 2006 Einzelprüfungsnummer: 46114 Seite: 5 . . T, — COST, Iterationsvorschrift: x, ,, = x, —-—+~¥———* 1+sinz, Iteration: a, = 0,2, =1, 2, = 0,75, 2, = 0,74, 2, = 0,74 Es soll nun ein Programm zur Berechnung einer Nullstelle einer beliebigen Funktion mit Hilfe des Newton-Verfahrens erstellt werden. Verwenden Sie geeignete Abbruchkriterien unter Berücksichtigung von Rundungsfehlern und Schnittstellen (Unterprogrammaufrufe) zur Berechnung von f(x) und SO. a) Erstellen Sie ein Programmablaufdiagramm nach DIN 66001 zum obigen Programm. b) Erstellen Sie ein Blockdiagramm für das Programm und schreiben Sie das Programm in Pascal oder einer anderen Programmiersprache.