IF LK HT 2 (GG) Seite 5 von 11 Name: _______________________ c) Unter einem Pfad versteht man den Weg, den ein Paket von seiner derzeitigen Position im Verteilungszentrum aus bis zur Verladestation noch gehen wird. Dieser Pfad kann angegeben werden, indem man nacheinander die Band-IDs der Bandsegmente angibt, die das Paket noch besuchen wird. In Abbildung 1 hat das Paket D ab der aktuellen Position den Pfad B2 – B2, das Paket E hat den Pfad B2 – B5 – B5. Die Klasse Paketverteilungszentrum soll um eine Methode lieferePfad erweitert werden, die den Pfad desjenigen Pakets, das sich an einem beliebigen Bandsegment be- findet, ermittelt und als Schlange zurückgibt. Enthält das Bandsegment kein Paket, soll eine leere Schlange zurückgegeben werden. Der Weg-Code des betrachteten Pakets darf durch die Ausführung der Methode nicht verändert werden. Die Methode hat folgenden Methodenkopf: public Queue<String> lieferePfad(BinaryTree<Bandsegment> pBaum) Die Wurzel des durch den Parameter pBaum angegebenen Teilbaums des Transportbaums entspricht dabei der betrachteten Position. Entwickeln und erläutern Sie ein algorithmisches Verfahren für diese Methode. Implementieren Sie die Methode lieferePfad. (14 Punkte) Abiturprüfung 2019 – Nur für den Dienstgebrauch!

IF LK HT 2 (GG) Seite 6 von 11 Name: _______________________ d) Ein Kritikpunkt am Design des Paketverteilungszentrums ist, dass jeder Übergang von einem Förderband lediglich zum Anfangssegment eines anderen Bandes führen kann und nicht zu einem beliebigen Segment. Ein Mitarbeiter schlägt daher vor, die Spezifikation der Anlage in genau diesem Punkt zu ändern und solche Übergänge in Zukunft zuzulassen. ... B14 G H D F 1 ... B23 I V23 V14 Abbildung 5: Ausschnitt aus einem Paketverteilungszentrum nach geänderter Spezifikation Abbildung 5 zeigt einen Ausschnitt aus einer Beispiel-Anlage. Hier gibt es einen Übergang von B14 nach B23 (B23 läuft unter B14 durch), der nicht auf den Anfang von B23 führt. Begründen Sie, dass bei der Umsetzung der vorgeschlagenen Änderung die ursprünglich für die Modellierung verwendete Datenstruktur des Binärbaums nicht mehr geeignet ist, und geben Sie eine Alternative an. Begründen Sie, dass die vorgeschlagene Änderung grundlegende Konsequenzen für die Transport-Algorithmik nach sich zieht. (8 Punkte) Zugelassene Hilfsmittel: • GTR (grafikfähiger Taschenrechner) oder CAS (Computer-Algebra-System) • Wörterbuch zur deutschen Rechtschreibung Abiturprüfung 2019 – Nur für den Dienstgebrauch!

IF LK HT 2 (GG) Seite 7 von 11 Name: _______________________ Anhang Dokumentationen der verwendeten Klassen Alle in diesem Abschnitt nicht weiter dokumentierten gib...- bzw. setze...-Methoden ent- sprechen den üblichen Funktionsweisen. Die Klasse String Ein Objekt der Klasse String repräsentiert eine Zeichenkette. Ausschnitt aus der Dokumentation der Klasse String Anfrage char charAt(int index) Die Anfrage gibt das Zeichen am angegebenen Index zurück. Der Index hat einen Wertebereich von 0 bis length()-1. Das erste Zeichen dieser Zeichen- kette ist an Index 0, das nächste an Index 1 und so weiter, wie bei Array- Indizes. Anfrage String substring(int beginIndex) Gibt eine neue Zeichenkette zurück, die eine Unter-Zeichenkette dieser Zei- chenkette ist. Die Unter-Zeichenkette beginnt mit dem Zeichen, das sich am angegebenen Index befindet (beginnend bei Index 0) und reicht bis zum Ende dieser Zeichenkette. Beispiele: • "unschön".substring(2) gibt "schön" zurück • "Leere".substring(5) gibt "" zurück (eine leere Zeichenkette) Die Klasse Paketverteilungszentrum Die Klasse dient der Simulation eines Paketverteilungszentrums. Sie erzeugt einen Trans- portbaum und simuliert schrittweise den Transport der Pakete. Ausschnitt aus der Dokumentation der Klasse Paketverteilungszentrum Kontruktor Paketverteilungszentrum() Ein Paketverteilungszentrum mit dem durch die reale Anlage gegebenen Transportbaum wird initialisiert. Auftrag void transportiere() Die Methode rückt alle im Transportbaum enthaltenen Pakete um ein Band- segment (entsprechend ihres jeweiligen Weg-Codes) weiter oder aber ver- lädt sie (verladene Pakete werden vom Transportbaum nicht mehr verwaltet). Lässt ein Paket bei diesem Transportschritt einen Übergang hinter sich, wird das vorderste Zeichen seines Weg-Codes gelöscht. Abiturprüfung 2019 – Nur für den Dienstgebrauch!

IF LK HT 2 (GG) Seite 8 von 11 Name: _______________________ Die Klasse Paket Jedes Objekt dieser Klasse modelliert ein Paket auf einem bestimmten Segment eines För- derbands. Ausschnitt aus der Dokumentation der Klasse Paket Konstruktor Paket(String pPaketID, String pWegCode) Ein Paket wird initialisiert. Erläuterung der Parameter: • pPaketID gibt die eindeutige ID des Pakets an. • pWegCode codiert den Weg, den dieses Paket durch die Anlage nehmen muss. Das jeweils vorderste Zeichen im String markiert dabei, wie am nächsten Bandsegment der Anlage, das einen Übergang besitzt, zu ver- fahren ist: – 0 bedeutet, dass der Übergang nicht benutzt wird. – 1 bedeutet, dass der Übergang benutzt wird, also zum Anfang eines anderen Bands umgelenkt wird. Alle weiteren Zeichen stehen analog für die im weiteren Verlauf des Transports anstehenden Entscheidungen. Die Klasse Bandsegment Der Transportbaum verwaltet Objekte dieser Klasse. Ein Objekt dieser Klasse modelliert ein bestimmtes Segment eines Förderbands. Jedes Förderband besteht aus beliebig vielen Segmenten. Segmente sind gekennzeichnet durch die ID des Förderbandes, zu dem sie ge- hören, und verwalten ein Objekt der Klasse Paket, falls das Bandsegment ein Paket enthält (andernfalls ist die entsprechende Referenz null). Ausschnitt aus der Dokumentation der Klasse Bandsegment Konstruktor Bandsegment(String pBandID, Paket pInhalt) Ein Bandsegment, das zum Förderband mit der ID pBandID gehört und das Paket pInhalt als Inhalt besitzt, wird initialisiert. Hat pInhalt den Wert null, wird ein leeres Bandsegment initialisiert. Abiturprüfung 2019 – Nur für den Dienstgebrauch!

IF LK HT 2 (GG) Seite 9 von 11 Name: _______________________ Die generische Klasse Queue<ContentType> Objekte der generischen Klasse Queue (Warteschlange) verwalten beliebige Objekte vom Typ ContentType nach dem First-In-First-Out-Prinzip, d. h., das zuerst abgelegte Objekt wird als erstes wieder entnommen. Alle Methoden haben eine konstante Laufzeit, unabhängig von der Anzahl der verwalteten Objekte. Dokumentation der generischen Klasse Queue<ContentType> Konstruktor Queue() Eine leere Schlange wird erzeugt. Objekte, die in dieser Schlange verwaltet werden, müssen vom Typ ContentType sein. Anfrage boolean isEmpty() Die Anfrage liefert den Wert true, wenn die Schlange keine Objekte ent- hält, sonst liefert sie den Wert false. Auftrag void enqueue(ContentType pContent) Das Objekt pContent wird an die Schlange angehängt. Falls pContent gleich null ist, bleibt die Schlange unverändert. Auftrag void dequeue() Das erste Objekt wird aus der Schlange entfernt. Falls die Schlange leer ist, wird sie nicht verändert. Anfrage ContentType front() Die Anfrage liefert das erste Objekt der Schlange. Die Schlange bleibt unverändert. Falls die Schlange leer ist, wird null zurückgegeben. Abiturprüfung 2019 – Nur für den Dienstgebrauch!

IF LK HT 2 (GG) Seite 10 von 11 Name: _______________________ Die Klasse BinaryTree<ContentType> Mithilfe der generischen Klasse BinaryTree können beliebig viele Objekte vom Typ ContentType in einem Binärbaum verwaltet werden. Ein Objekt der Klasse stellt entweder einen leeren Baum dar oder verwaltet ein Inhaltsobjekt sowie einen linken und einen rechten Teilbaum, die ebenfalls Objekte der generischen Klasse BinaryTree sind. Dokumentation der Klasse BinaryTree<ContentType> Konstruktor BinaryTree() Nach dem Aufruf des Konstruktors existiert ein leerer Binärbaum. Objekte, die in diesem Binärbaum verwaltet werden, müssen vom Typ ContentType sein. Konstruktor BinaryTree(ContentType pContent) Wenn der Parameter pContent ungleich null ist, existiert nach dem Auf- ruf des Konstruktors der Binärbaum und hat pContent als Inhaltsobjekt und zwei leere Teilbäume. Falls der Parameter null ist, wird ein leerer Binär- baum erzeugt. Konstruktor BinaryTree(ContentType pContent, BinaryTree<ContentType> pLeftTree, BinaryTree<ContentType> pRightTree) Wenn der Parameter pContent ungleich null ist, wird ein Binärbaum mit pContent als Inhaltsobjekt und den beiden Teilbäumen pLeftTree und pRightTree erzeugt. Sind pLeftTree oder pRightTree gleich null, wird der entsprechende Teilbaum als leerer Binärbaum eingefügt. Wenn der Parameter pContent gleich null ist, wird ein leerer Binärbaum erzeugt. Anfrage boolean isEmpty() Diese Anfrage liefert den Wahrheitswert true, wenn der Binärbaum leer ist, sonst liefert sie den Wert false. Auftrag void setContent(ContentType pContent) Wenn der Binärbaum leer ist, wird der Parameter pContent als Inhalts- objekt sowie ein leerer linker und rechter Teilbaum eingefügt. Ist der Binär- baum nicht leer, wird das Inhaltsobjekt durch pContent ersetzt. Die Teil- bäume werden nicht geändert. Wenn pContent null ist, bleibt der Binär- baum unverändert. Abiturprüfung 2019 – Nur für den Dienstgebrauch!

IF LK HT 2 (GG) Seite 11 von 11 Name: _______________________ Anfrage ContentType getContent() Diese Anfrage liefert das Inhaltsobjekt des Binärbaums. Wenn der Binär- baum leer ist, wird null zurückgegeben. Auftrag void setLeftTree(BinaryTree<ContentType> pTree) Wenn der Binärbaum leer ist, wird pTree nicht angehängt. Andernfalls erhält der Binärbaum den übergebenen Baum als linken Teilbaum. Falls der Parameter null ist, ändert sich nichts. Auftrag void setRightTree(BinaryTree<ContentType> pTree) Wenn der Binärbaum leer ist, wird pTree nicht angehängt. Andernfalls er- hält der Binärbaum den übergebenen Baum als rechten Teilbaum. Falls der Parameter null ist, ändert sich nichts. Anfrage BinaryTree<ContentType> getLeftTree() Diese Anfrage liefert den linken Teilbaum des Binärbaumes. Der Binärbaum ändert sich nicht. Wenn der Binärbaum leer ist, wird null zurückgegeben. Anfrage BinaryTree<ContentType> getRightTree() Diese Anfrage liefert den rechten Teilbaum des Binärbaumes. Der Binär- baum ändert sich nicht. Wenn der Binärbaum leer ist, wird null zurück- gegeben. Abiturprüfung 2019 – Nur für den Dienstgebrauch!

Ministerium für Schule und Bildung NRW IF LK HT 2 (GG) Seite 1 von 9 Unterlagen für die Lehrkraft Abiturprüfung 2019 Informatik, Leistungskurs 1. Aufgabenart Analyse, Modellierung und Implementation von kontextbezogenen Problemstellungen mit Schwer- punkt auf den Inhaltsfeldern Daten und ihre Strukturierung, Algorithmen und Informatiksysteme 2. 1 Aufgabenstellung siehe Prüfungsaufgabe 3. Materialgrundlage entfällt 4. Bezüge zum Kernlehrplan und zu den Vorgaben 2019 Die Aufgaben weisen vielfältige Bezüge zu den Kompetenzerwartungen und Inhaltsfeldern des Kernlehrplans bzw. zu den in den Vorgaben ausgewiesenen Fokussierungen auf. Im Folgenden wird auf Bezüge von zentraler Bedeutung hingewiesen. 1. Inhaltsfelder und inhaltliche Schwerpunkte Daten und ihre Strukturierung • Objekte und Klassen – Entwurfsdiagramme und Implementationsdiagramme – Nicht-lineare Strukturen (Binärbaum) – Lineare Strukturen (Schlange) Algorithmen • Analyse, Entwurf und Implementierung von Algorithmen Formale Sprachen und Automaten • Syntax und Semantik einer Programmiersprache – Java 2. Medien/Materialien • entfällt 5. Zugelassene Hilfsmittel • GTR (grafikfähiger Taschenrechner) oder CAS (Computer-Algebra-System) • Wörterbuch zur deutschen Rechtschreibung 1 Die Aufgabenstellung deckt inhaltlich alle drei Anforderungsbereiche ab. Abiturprüfung 2019 – Nur für den Dienstgebrauch!

IF LK HT 2 (GG) Ministerium für Schule und Bildung NRW Seite 2 von 9 6. Modelllösungen Die jeweilige Modelllösung stellt eine mögliche Lösung bzw. Lösungsskizze dar. Der gewählte Lösungsansatz und -weg der Schülerinnen und Schüler muss nicht identisch mit dem der Modelllösung sein. Sachlich richtige Alternativen werden mit entsprechender Punktzahl bewertet (Bewertungsbogen: Zeile „Sachlich richtige Lösungsalternative zur Modelllösung“). Teilaufgabe a) Der Binärbaum ist eine rekursive Datenstruktur, die sich durch folgende Eigenschaften aus- zeichnet: • Jeder Binärbaum ist entweder leer oder besteht aus einem Wurzelelement, das zwei Binärbäume als Nachfolger besitzt. • Jedes Element eines nicht-leeren Binärbaums verwaltet ein Inhaltsobjekt. Der sich aus dem gegebenen Paketverteilungszentrum ergebende Transportbaum hat die rechtsste- hende Form. B1 A 011 B1 B 00 B1 Paket A muss laut seiner Weg- Codierung 011 den ersten sich auf seinem Pfad durch die Anlage an- bietenden Übergang auslassen und die danach folgenden zwei nutzen. Vom Segment des Pakets A aus führt der nächste verfügbare Über- gang zu Band B2, dieser wird aus- gelassen. Der nächste Übergang führt zu B3 und der dortige nächste schließlich zu B4. Paket A wird also auf Verladestation V4 verladen, die am Ende von Band B4 steht. null B1 null B1 B2 null D B1 0 B2 C 10 E 1 B2 B3 null F 1 B3 B5 null null B5 H B4 null B4 Paket B wird laut seiner Weg- G Codierung 00 noch an 2 möglichen Übergängen vorbeigeführt, die beide ohne Umlenkung passiert werden. Paket B bleibt also auf dem Band, auf dem es sich momen- tan befindet und wird folglich bei Station V1 verladen. Paket C wird laut seiner Weg-Codierung 10 noch auf 2 Übergänge stoßen, von denen der erste zu nehmen ist und der zweite auszulassen ist. Paket C steht gerade an diesem zu nehmenden Übergang und wird daher auf Band B3 umgeleitet und bei Station V3 verladen. Paket G ist von B1 nach B4 gelangt. Unterwegs wurde der Übergang B1 – B2 ausgelassen und die Übergange B1 – B3 und B3 – B4 genommen. Als ursprüngliche Weg-Codierung ergibt sich also 011. Abiturprüfung 2019 – Nur für den Dienstgebrauch!

Ministerium für Schule und Bildung NRW IF LK HT 2 (GG) Seite 3 von 9 Teilaufgabe b) Der von der Methode zurückgegebene String lautet: B1:[A][B][C][_][E]#B2:[_][D][_]#B4:[_][_]#B3:[_][F] Die Methode gibt einen String zurück, der den Inhalt des Transportbaums in linearisierter Form repräsentiert. Die Paket-IDs werden darin in der Reihenfolge, in der die Pakete auf den Bändern liegen, jeweils blockweise ausgegeben. Jeder Block wird eingeleitet mit der Band-ID, gefolgt von einem Doppelpunkt. Die einzelnen Paket-IDs werden jeweils in einem eckigen Klammerpaar ausgegeben; bei leeren Paketen wird die Paket-ID durch einen Unter- strich ersetzt. Die Abgrenzung eines Blocks zum jeweils nächsten erfolgt durch ein Doppel- kreuz. Die Methode hat also den Zweck, den Beladungszustand des Paketverteilungszentrums nach Bändern gruppiert auszugeben. Ausgehend vom Startband werden die Bänder dabei in der Reihenfolge rekursiv ausgegeben, in der die zugehörigen Übergänge in Transportrichtung auftauchen. Algorithmisch wird dies dadurch erreicht, dass der Ausgabestring r zunächst mit der aktuellen Band-ID und dem Doppelpunkt initialisiert wird (Z. 5). In den Zeilen 8 bis 19 erfolgt dann eine Iteration über alle rechten Nachfolger (Z. 18), was im Sachkontext bedeutet, dass durch die Schleife alle Bandsegmente des aktuellen Bandes der Reihe nach besucht werden. Für jeden zugehörigen Knoten wird zunächst überprüft, ob er auch einen linken Nachfolger besitzt; in diesem Fall wird der Knoten in der Queue q abgelegt (Z. 9 – 11). Enthält das Band- segment des aktuellen Knotens ein Paket, wird dessen ID an den Rückgabe-String angehängt bzw. andernfalls das leere Bandsegment durch den Unterstrich angedeutet (Z. 13 – 17). Beim Durchlaufen des entsprechenden Astes dient die Queue q also dazu, alle Knoten mit Übergängen zwischenzuspeichern, die unterwegs vorkommen. Nach der kompletten Iteration des Astes wird die Queue q abgebaut, indem für jeden ihrer Einträge wasLiefereIch rekursiv aufgerufen wird und damit die Ausgabe des Förderbands, das am entsprechenden Übergang beginnt, durch das Doppelkreuz von der bisher erzeugten Ausgabe getrennt, rekursiv an die Ausgabe angehängt wird (Z. 20 – 23). Abiturprüfung 2019 – Nur für den Dienstgebrauch!