IF GK HT 2 (GG) Seite 8 von 12 Name: _______________________ Die Klasse Nachricht Ein Objekt der Klasse Nachricht verwaltet die IDs des Senders und des Empfängers so- wie den eigentlichen Nachrichtentext. Ausschnitt aus der Dokumentation der Klasse Nachricht Konstruktor Nachricht(pSenderID: String, pEmpfaengerID: String, pText: String) Ein Objekt wird initialisiert. Die übergebenen Werte der Parameter werden gespeichert. Das Objekt ist als nicht gelesen markiert. Anfrage String gibSenderID() Die Methode liefert die ID des Senders. Anfrage String gibEmpfaengerID() Die Methode liefert die ID des Empfängers. Anfrage String gibText() Die Methode liefert den Text der Nachricht. Abiturprüfung 2019 – Nur für den Dienstgebrauch!

IF GK HT 2 (GG) Seite 9 von 12 Name: _______________________ Die generische Klasse List<ContentType> Objekte der generischen Klasse List verwalten beliebig viele, linear angeordnete Objekte vom Typ ContentType. Auf höchstens ein Listenobjekt, aktuelles Objekt genannt, kann je- weils zugegriffen werden. Wenn eine Liste leer ist, vollständig durchlaufen wurde oder das ak- tuelle Objekt am Ende der Liste gelöscht wurde, gibt es kein aktuelles Objekt. Das erste oder das letzte Objekt einer Liste können durch einen Auftrag zum aktuellen Objekt gemacht wer- den. Außerdem kann das dem aktuellen Objekt folgende Listenobjekt zum neuen aktuellen Ob- jekt werden. Das aktuelle Objekt kann gelesen, verändert oder gelöscht werden. Außerdem kann vor dem aktuellen Objekt ein Listenobjekt eingefügt werden. Dokumentation der Klasse List<ContentType> Konstruktor List() Eine leere Liste wird erzeugt. Objekte, die in dieser Liste verwaltet werden, müssen vom Typ ContentType sein. Anfrage boolean isEmpty() Die Anfrage liefert den Wert true, wenn die Liste keine Objekte enthält, sonst liefert sie den Wert false. Anfrage boolean hasAccess() Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie den Wert false. Auftrag void next() Falls die Liste nicht leer ist, es ein aktuelles Objekt gibt und dieses nicht das letzte Objekt der Liste ist, wird das dem aktuellen Objekt in der Liste folgen- de Objekt zum aktuellen Objekt, andernfalls gibt es nach Ausführung des Auftrags kein aktuelles Objekt, d. h., hasAccess() liefert den Wert false. Auftrag void toFirst() Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts. Auftrag void toLast() Falls die Liste nicht leer ist, wird das letzte Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts. Abiturprüfung 2019 – Nur für den Dienstgebrauch!

IF GK HT 2 (GG) Seite 10 von 12 Name: _______________________ Anfrage ContentType getContent() Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird das aktuelle Objekt zurückgegeben. Andernfalls (hasAccess() == false) gibt die Anfrage den Wert null zurück. Auftrag void setContent(ContentType pContent) Falls es ein aktuelles Objekt gibt (hasAccess() == true) und pContent ungleich null ist, wird das aktuelle Objekt durch pContent ersetzt. Sonst bleibt die Liste unverändert. Auftrag void append(ContentType pContent) Ein neues Objekt pContent wird am Ende der Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Wenn die Liste leer ist, wird das Objekt pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt (hasAccess() == false). Falls pContent gleich null ist, bleibt die Liste unverändert. Auftrag void insert(ContentType pContent) Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird ein neues Objekt pContent vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt gibt (hasAccess() == false), wird pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls es kein aktuelles Objekt gibt (hasAccess() == false) und die Liste nicht leer ist oder pContent == null ist, bleibt die Liste unverändert. Auftrag void concat(List<ContentType> pList) Die Liste pList wird an die Liste angehängt. Anschließend wird pList eine leere Liste. Das aktuelle Objekt bleibt unverändert. Falls es sich bei der Liste und pList um dasselbe Objekt handelt, pList == null oder eine leere Liste ist, bleibt die Liste unverändert. Auftrag void remove() Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird das aktuelle Objekt gelöscht und das Objekt hinter dem gelöschten Objekt wird zum aktuellen Objekt. Wird das Objekt, das am Ende der Liste steht, gelöscht, gibt es kein aktuelles Objekt mehr (hasAccess() == false). Wenn die Liste leer ist oder es kein aktuelles Objekt gibt (hasAccess() == false), bleibt die Liste unverändert. Abiturprüfung 2019 – Nur für den Dienstgebrauch!

IF GK HT 2 (GG) Seite 11 von 12 Name: _______________________ Die Klasse BinarySearchTree<ContentType extends ComparableContent<ContentType>> Mithilfe der generischen Klasse BinarySearchTree können beliebig viele Objekte des Typs ContentType in einem Binärbaum (binärer Suchbaum) entsprechend einer Ordnungs- relation verwaltet werden. Ein Objekt der Klasse BinarySearchTree stellt entweder einen leeren Baum dar oder verwaltet ein Inhaltsobjekt vom Typ ContentType sowie einen linken und einen rechten Teilbaum, die ebenfalls Objekte der Klasse BinarySearchTree sind. Die Klasse der Objekte, die in dem Suchbaum verwaltet werden sollen, muss das generische Interface ComparableContent implementieren. Dabei muss durch Überschreiben der drei Vergleichsmethoden isLess, isEqual, isGreater (siehe Dokumentation des Interfaces) eine eindeutige Ordnungsrelation festgelegt sein. Die Objekte der Klasse ContentType sind damit vollständig geordnet. Für je zwei Objekte c1 und c2 vom Typ ContentType gilt also insbesondere genau eine der drei Aussagen: • c1.isLess(c2) (Sprechweise: c1 ist kleiner als c2) • c1.isEqual(c2) (Sprechweise: c1 ist gleichgroß wie c2) • c1.isGreater(c2) (Sprechweise: c1 ist größer als c2) Alle Objekte im linken Teilbaum sind kleiner als das Inhaltsobjekt des Binärbaumes. Alle Objekte im rechten Teilbaum sind größer als das Inhaltsobjekt des Binärbaumes. Diese Bedingung gilt auch in beiden Teilbäumen. Dokumentation der generischen Klasse BinarySearchTree<ContentType extends ComparableContent<ContentType>> Konstruktor BinarySearchTree() Der Konstruktor erzeugt einen leeren Suchbaum. Anfrage boolean isEmpty() Diese Anfrage liefert den Wahrheitswert true, wenn der Suchbaum leer ist, sonst liefert sie den Wert false. Auftrag void insert(ContentType pContent) Falls bereits ein Objekt in dem Suchbaum vorhanden ist, das gleichgroß ist wie pContent, passiert nichts. Andernfalls wird das Objekt pContent entsprechend der Ordnungsrelation in den Baum eingeordnet. Falls der Parameter null ist, ändert sich nichts. Anfrage ContentType search(ContentType pContent) Falls ein Objekt im binären Suchbaum enthalten ist, das gleichgroß ist wie pContent, liefert die Anfrage dieses, ansonsten wird null zurückgegeben. Falls der Parameter null ist, wird null zurückgegeben. Abiturprüfung 2019 – Nur für den Dienstgebrauch!

IF GK HT 2 (GG) Seite 12 von 12 Name: _______________________ Auftrag void remove(ContentType pContent) Falls ein Objekt im binären Suchbaum enthalten ist, das gleichgroß ist wie pContent, wird dieses entfernt. Falls der Parameter null ist, ändert sich nichts. Anfrage ContentType getContent() Diese Anfrage liefert das Inhaltsobjekt des Suchbaumes. Wenn der Such- baum leer ist, wird null zurückgegeben. Anfrage BinarySearchTree<ContentType> getLeftTree() Diese Anfrage liefert den linken Teilbaum des binären Suchbaumes. Der binäre Suchbaum ändert sich nicht. Wenn er leer ist, wird null zurück- gegeben. Anfrage BinarySearchTree<ContentType> getRightTree() Diese Anfrage liefert den rechten Teilbaum des Suchbaumes. Der Such- baum ändert sich nicht. Wenn er leer ist, wird null zurückgegeben. Das generische Interface (Schnittstelle) ComparableContent<ContentType> Das generische Interface ComparableContent muss von Klassen implementiert werden, deren Objekte in einen Suchbaum (BinarySearchTree) eingefügt werden sollen. Die Ordnungsrelation wird in diesen Klassen durch Überschreiben der drei implizit abstrakten Methoden isGreater, isEqual und isLess festgelegt. Das Interface ComparableContent gibt folgende implizit abstrakte Methoden vor: Anfrage boolean isGreater(ContentType pComparableContent) Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gewünschten Ordnungsrelation größer als das Objekt pComparableContent ist, wird true geliefert. Sonst wird false geliefert. Anfrage boolean isEqual(ContentType pComparableContent) Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gewünschten Ordnungsrelation gleich dem Objekt pComparableContent ist, wird true geliefert. Sonst wird false geliefert. Anfrage boolean isLess(ContentType pComparableContent) Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gewünschten Ordnungsrelation kleiner als das Objekt pComparableContent ist, wird true geliefert. Sonst wird false geliefert. Abiturprüfung 2019 – Nur für den Dienstgebrauch!

Ministerium für Schule und Bildung NRW IF GK HT 2 (GG) Seite 1 von 9 Unterlagen für die Lehrkraft Abiturprüfung 2019 Informatik, Grundkurs 1. Aufgabenart Analyse, Modellierung und Implementation von kontextbezogenen Problemstellungen mit Schwerpunkt auf den Inhaltsfeldern Daten und ihre Strukturierung und 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 – Entwurfsdigramme und Implementationsdiagramme – Lineare Strukturen Lineare Liste – Nicht-lineare Strukturen Binärer Suchbaum Algorithmen • Analyse, Entwurf und Implementierung von Algorithmen Formale Sprachen und Automaten • Syntax und Semantik einer Programmiersprache – Java 2. Medien/Materialien • entfällt 1 Die Aufgabenstellung deckt inhaltlich alle drei Anforderungsbereiche ab. Abiturprüfung 2019 – Nur für den Dienstgebrauch!

IF GK HT 2 (GG) Ministerium für Schule und Bildung NRW Seite 2 von 9 5. Zugelassene Hilfsmittel • GTR (grafikfähiger Taschenrechner) oder CAS (Computer-Algebra-System) • Wörterbuch zur deutschen Rechtschreibung 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) Ein binärer Suchbaum ist eine besondere Art eines Binärbaums. Die Elemente, die in dem Suchbaum gespeichert werden, werden in einer Ordnung abgespeichert, die einer Ordnungs- relation auf den Elementen folgt. Ist der Binärbaum leer, wird das Element als Wurzelelement eingefügt. Andernfalls wird es zunächst mit dem Wurzelelement verglichen. Ist es bezüglich des Sortierkriteriums kleiner als das Wurzelelement, so wird das Verfahren im linken Teilbaum fortgesetzt, da alle Elemente im linken Teilbaum kleiner als das aktuelle Element sind. Ist es größer, so wird das Verfahren im rechten Teilbaum fortgesetzt, da im rechten Teilbaum alle Elemente größer als das aktuelle Element sind. Ist es gleich, hängt die Entscheidung vom konkreten Entwurf ab, ob das Element überhaupt eingefügt wird oder das Verfahren im linken oder im rechten Teilbaum fortgeführt wird. Beispielsweise wird in der Klasse BinarySearchTree bei Gleichheit nicht eingefügt. Gamelie <iqrz> Chefchecker <giyf> Ada23 <adai> Gig <tgif> Hacktor <oloy> Fehler451 <asap> Die entstehende Ordnung eines binären Suchbaums ermöglicht in der Regel eine schnellere Suche nach einem Element als in einer vergleichbaren linearen Struktur – sofern der Such- baum durch eine ungünstige Einfügekonstellation nicht sehr unausgeglichen aufgebaut ist. In diesem Kontext werden häufig die Profile anhand ihres Identifikators gesucht, z. B., um eine Nachricht zu speichern. Deswegen ist es wichtig, dass das Suchen eines Profils eine geringe Laufzeit benötigt. Genau diesen Vorteil bietet ein Suchbaum gegenüber einer sortierten Liste. Abiturprüfung 2019 – Nur für den Dienstgebrauch!

Ministerium für Schule und Bildung NRW IF GK HT 2 (GG) Seite 3 von 9 Teilaufgabe b) Ein Objekt der Klasse InstantMessagingSystem verwaltet mehrere Objekte der Klasse Profil. Für die Verwaltung dieser Objekte wird ein Objekt der Klasse BinarySearchTree mit dem Inhaltstyp Profil verwendet. Das Objekt hat den Bezeichner profile. Der Daten- typ der in diesem Objekt der generischen Klasse BinarySearchTree verwalteten Objekte wird als Profil festgelegt. Damit Objekte der Klasse Profil mit anderen Objekten dieser Klasse (oder einer Unter- klasse) verglichen und somit in einem binären Suchbaum verwaltet werden können, muss die Klasse Profil die Schnittstelle ComparableContent<Profil> implementieren. Dadurch werden die Methoden isLess, isEqual und isGreater in Bezug auf Profil implementiert. Der generische Datentyp des Interface ComparableContent wird als Datentyp Profil festgelegt. Teilaufgabe c) public void speichereNachricht(String pSenderID, String pEmpfaengerID, String pText) { //Ermitteln der Profile anhand ihrer IDs Profil sender = ermittleProfil(pSenderID); Profil empfaenger = ermittleProfil(pEmpfaengerID); //Die Nachricht wird nur genau dann gespeichert, //wenn beide Profile existieren. if (sender != null && empfaenger != null) { //Erzeugen eines Nachrichten-Objekts Nachricht neu = new Nachricht(pSenderID, pEmpfaengerID, pText); } //Hinzufügen in beiden Profilen sender.fuegeHinzu(neu); empfaenger.fuegeHinzu(neu); } Abiturprüfung 2019 – Nur für den Dienstgebrauch!

Ministerium für Schule und Bildung NRW IF GK HT 2 (GG) Seite 4 von 9 Teilaufgabe d) Es werden alle Knoten des Baums in In-Order-Reihenfolge durchlaufen, also in der folgenden Reihenfolge: "AGakRöte", "Perseus", "Gar10", "Gamelie", "KillerBee", "BänX", "GarGonzoLa". Die öffentliche Methode ruft die private Methode suche mit der Zeichenkette "Ga" und dem gesamten Suchbaum als Parameter auf. Sie gibt das Ergebnis der privaten Methode zurück. In der privaten Methode wird zunächst wird im linken Teilbaum gesucht. Ist die Suche dort abgeschlossen, wird das aktuelle Element betrachtet, danach wird im rechten Teilbaum weiter- gesucht. Der Profilname "AGakRöte" beginnt nicht mit "Ga", deswegen wird dort, wie beim Profil mit Namen "Perseus", eine leere Liste zurückgegeben. Da der Profilname "Gar10" mit "Ga" beginnt, wird das Profil in eine Ergebnisliste aufgenommen. Der rechte Teilbaum vom Profil mit Namen "Gar10", der linke vom Profil mit Namen "AGakRöte" und der linke und rechte Teilbaum vom Profil mit Namen "Perseus" sind leer, dort wird also jeweils eine leere Liste zurückgegeben. Die Rückgabe des Rekursionsschritts mit "Gar10" als Wurzel liefert eine nicht leere Liste an den ersten Rekursionsaufruf zurück. Diese Liste wird mit der Ergebnisliste konkateniert und enthält also zunächst das Profil mit Namen "Gar10", dann das Profil mit Namen "Gamelie". Nun wird der rechte Teilbaum vom Profil mit Namen "Gamelie" durchlaufen, wo auf die gleiche Art nur das Profil mit Namen "GarGonzoLa" ermittelt wird. Es ergibt sich also als Rückgabe eine Liste, die die drei Profile mit den Namen "Gar10", "Gamelie" und "GarGonzoLa" in dieser Reihenfolge enthält. Die Methode ermittelt alle Profile, deren Name mit dem Wert des Parameters pP beginnt. Abiturprüfung 2019 – Nur für den Dienstgebrauch!

Ministerium für Schule und Bildung NRW IF GK HT 2 (GG) Seite 5 von 9 Teilaufgabe e) Sämtliche Nachrichten, die mit einem Kommunikationspartner ausgetauscht werden, werden in einem Objekt der Klasse Konversation gesammelt. Der Kommunikationspartner ist bei jeder Nachricht anhand der ID zu identifizieren. In einem Profil werden nicht die Nach- richten selbst, sondern die Konversationen in einer Liste verwaltet. Wird bei einem Profil eine neue Nachricht hinzugefügt, so wird diese an die entsprechende Konversation weiter- gereicht. Existiert noch keine Konversation, wird eine neue Konversation mit der in der Nachricht enthaltenen ID und gegebenenfalls dem Namen des Partners hinzugefügt. Abiturprüfung 2019 – Nur für den Dienstgebrauch!