Aufgabe 2 - Binärbäume und binäre Suchbäume · Abitur NRW Informatik LK · Nachtermin 2021

Thema: Binärbäume und binäre Suchbäume · Aus der Prüfung LK · Nachtermin (2021)

Aufgabenstellung

Aufgabenstellung:

Damit sich das Verkehrsaufkommen auf Fernstraßen genauer abschätzen lässt, finden regelmäßig Verkehrszählungen statt. Im Zuge der Digitalisierung soll dieser Vorgang automatisiert ablaufen. Eine Kamera und eine passende Bilderkennungssoftware sollen dazu die Ortskürzel (auch Ortskennzeichen genannt) der vorbeifahrenden Kraftfahrzeuge (Kfz) selbstständig erfassen und zählen. Die Daten werden in einem binären Suchbaum abgelegt, dessen Ordnung auf der alphabetischen Reihenfolge der Ortskürzel beruht.

Die Zählsoftware soll um weitere Merkmale ergänzt werden. Für jede Messung sollen der exakte Zeitpunkt sowie die Fahrzeugklasse des Fahrzeugs, das die Zählstelle durchfuhr, festgehalten werden. Dabei wird bei der Fahrzeugklasse zwischen dem üblichen Personenverkehr mit Pkw auf der einen Seite und allen übrigen, vor allem größeren Kraftfahrzeugen auf der anderen Seite (z. B. Bussen, Traktoren und Lastkraftwagen) unterschieden.

Grundlage der Software ist das Implementationsdiagramm, von dem die folgende Abbildung 2 einen Ausschnitt zeigt. Die Dokumentation der verwendeten Klassen befindet sich im Anhang.

Teilaufgabe a) [8 Punkte]

Bisher haben Kraftfahrzeuge mit den Ortskürzeln AC, MS, MS und PB eine Zählstelle passiert. Der folgende binäre Suchbaum stellt diese Messungen dar:

a.1

a.2

Erweitern Sie den binären Suchbaum aus Abbildung 1 um weitere Messungen: Die Kamera erfasst nun nacheinander die Ortskürzel ST, MS, BI, RS, SO, MS, OB, HSK, PB, DO (stellen Sie den dabei jeweils entstehenden Suchbaum nach dem Einfügen der dritten und der letzten dieser Messungen dar).

Teilaufgabe c) [14 Punkte]

Für die Statistik sollen die erfassten Daten nach bestimmten Kriterien ausgewertet werden. Zunächst soll bestimmt werden, wie viele Kraftfahrzeuge die Zählstelle innerhalb eines gegebenen Zeitraums passiert haben. Dafür erhält eine noch zu implementierende Methode ermittleAnzahl zwei Objekte der Klasse Zeitstempel, die Beginn und Ende des Zeitraums festlegen. Ihr Methodenkopf lautet:

public int ermittleAnzahl(Zeitstempel pVon, Zeitstempel pBis) c.1

c.2

Aufgabenstellung: Aufgabe 2 - Binärbäume und binäre Suchbäume · Abitur NRW Informatik LK · Nachtermin 2021

Lösung

Nach den offiziellen Korrekturhinweisen

Geben Sie eine Abfolge von Ortskürzeln an, die, in einen zunächst leeren Binärbaum eingefügt, den Binärbaum aus Abbildung 1 ergibt.

Lösung: MS - PB - AC - MS / MS - AC - PB - MS / MS - MS - AC - PB / MS - MS - PB - AC / MS - AC - MS - PB / MS - PB - MS - AC

Erweitern Sie den binären Suchbaum aus Abbildung 1 um weitere Messungen: Die Kamera erfasst nun nacheinander die Ortskürzel ST, MS, BI, RS, SO, MS, OB, HSK, PB, DO (stellen Sie den dabei jeweils entstehenden Suchbaum nach dem Einfügen der dritten und der letzten dieser Messungen dar).

Lösung: Nach dem Einfügen der ersten drei weiteren Messungen (ST, MS, BI): Nach dem Einfügen aller weiteren Messungen:

Entwickeln Sie für diese Methode eine algorithmische Strategie.

Lösung: Die Methode muss den Baum komplett traversieren, um für jeden Knoten alle vorhandenen Messungen auf den angegebenen Zeitraum hin untersuchen zu können. Beim rekursiven Besuch des jeweils aktuellen Knotens muss dazu die Liste von Messungen, die von diesem Knoten verwaltet wird, durchlaufen werden und dabei auf Messungen hin untersucht werden, die innerhalb des angegebenen Zeitraums liegen. Wird so eine kriteriengemäße Messung gefunden, wird ein Zähler um 1 erhöht.

Implementieren Sie die Methode, einschließlich eventuell erforderlicher weiterer Methoden.

Lösung: ```java public int ermittleAnzahl(Zeitstempel pVon, Zeitstempel pBis) { return ermittleAnzahl(verkehrszaehlung, pVon, pBis); } private int ermittleAnzahl(BinarySearchTree<OrtsDaten> pBaum, Zeitstempel pZ1, Zeitstempel pZ2) { int ret = 0; if (!pBaum.isEmpty()) { OrtsDaten aktuell = pBaum.getContent(); List<Messung> lmAktuell = aktuell.gibMessungen(); lmAktuell.toFirst(); while (lmAktuell.hasAccess()) { Zeitstempel zs = lmAktuell.getContent().gibZeitstempel(); if (zs.liegtInnerhalb(pZ1, pZ2)) { ret = ret + 1; } lmAktuell.next(); } ret = ret + ermittleAnzahl(pBaum.getLeftTree(), pZ1, pZ2); ret = ret + ermittleAnzahl(pBaum.getRightTree(), pZ1, pZ2); } return ret; } ```

Die ausführliche Erklärung Schritt für Schritt (mit KI) gibt es mit Premium. Premium

Löse sie direkt hier: automatische Korrektur, Hinweise und Lösung Schritt für Schritt.

‹ Aufgabe 2 - Binäre Suchbäume · LK · Haupttermin 2021

Mehr Aufgaben zu Binärbäume und binäre Suchbäume