Aufgabe Vorschlag AJ - Aufgabe 4 · Abitur Hessen Informatik LK 2021
Thema: Dynamische Datenstrukturen und Rekursion · Aus der Prüfung LK (2021)
Aufgabenstellung
Als Alternative kann das Ranking in einem binären Suchbaum gespeichert werden (Material 2).
Material 2
Binärbaum mit Anzahl der Ringe als Sortierschlüssel nach dem ersten Durchgang
Material 3
Quellcode der Klassen Teilnehmerknoten und BinBaum
01 public class TeilnehmerKnoten {
02 // Die Klasse Teilnehmer ist wie in Aufgabenteil 1 definiert
03 private Teilnehmer derTeilnehmer;
04 private TeilnehmerKnoten Links, Rechts;
05
06 public TeilnehmerKnoten (Teilnehmer einTeilnehmer) {
07 derTeilnehmer = einTeilnehmer;
08 Links = null;
09 Rechts = null;
10 }
11... // die get- und set-Methoden können als gegeben angenommen werden
12 }
13
14 public class BinBaum {
15 private TeilnehmerKnoten Wurzel;
16 private int AnzahlTeilnehmer;
17 private Teilnehmer[] dieTeilnehmer;
18... // die verwendeten Methoden einfügen und löschen können als gegeben
19 // angenommen werden
20
21 public void optimiereBaum() {
22 überführeBaumNachFeld(Wurzel);
23 überführeFeldNachBaum(0, AnzahlTeilnehmer-1);
24 }
25
26 public void überführeBaumNachFeld(TeilnehmerKnoten einTeilnehmerKnoten) {
27 // siehe Aufgabe 4.1
28 }
29
30 public void überführeFeldNachBaum(int Anfang, int Ende) {
31 if (Anfang == Ende) {
32 einfügen(dieTeilnehmer[Anfang]);
33 } else if (Anfang < Ende) {
34 int pos = (Ende + Anfang) / 2;
35 einfügen(dieTeilnehmer[pos]);
36 überführeFeldNachBaum(Anfang, pos - 1);
37 überführeFeldNachBaum(pos + 1, Ende);
38 }
39 }
40 }
4 Um der Gestaltänderung des Baumes entgegenzuwirken, wird nach jedem Durchgang die Methode optimiereBaum() aufgerufen (Material 3).
4.1
Implementieren Sie die Methode überführeBaumNachFeld(...), die alle Teilnehmer aus dem Baum nach der Reihenfolge der erzielten Ringe in das Feld dieTeilnehmer überträgt und jeden Teilnehmer im Baum löscht, sobald er nicht mehr benötigt wird.
Hinweis: Die verwendeten Methoden einfügen(...) und löschen(...) können als gegeben angenommen werden.
[5 BE]
4.2
Analysieren Sie die Methode überführeFeldNachBaum(...) aus Material 3 und geben Sie an, welche Gestalt ein beliebiger Baum nach dem Aufruf von optimiereBaum() hat.
[4 BE]
Lösung
Nach den offiziellen Korrekturhinweisen
4.1 Implementieren Sie die Methode überführeBaumNachFeld(...), die alle Teilnehmer aus dem Baum nach der Reihenfolge der erzielten Ringe in das Feld dieTeilnehmer überträgt und jeden Teilnehmer im Baum löscht, sobald er nicht mehr benötigt wird.
Lösung: ```java public void überführeBaumNachFeld(TeilnehmerKnoten einTeilnehmerKnoten) { if (einTeilnehmerKnoten != null) { überführeBaumNachFeld(einTeilnehmerKnoten.getLinks()); int Index = 0; while (dieTeilnehmer[Index] != null) { Index++; } dieTeilnehmer[Index] = einTeilnehmerKnoten.getTeilnehmer(); überführeBaumNachFeld(einTeilnehmerKnoten.getRechts()); löschen(einTeilnehmerKnoten); } } ```
4.2 Analysieren Sie die Methode überführeFeldNachBaum(...) aus Material 3 und geben Sie an, welche Gestalt ein beliebiger Baum nach dem Aufruf von optimiereBaum() hat.
Lösung: Die Methode überführeFeldNachBaum(...) besitzt zwei int-Werte als Parameter und hat keine Rückgabe. Die Sichtbarkeit ist public. Wenn die Parameter Anfang und Ende den gleichen Wert haben, dann wird das entsprechende Feldelement in den Baum eingefügt. Sonst wird das ganzzahlige arithmetische Mittel der beiden Werte in pos gespeichert und dementsprechend das mittlere Element des Feldes in den Baum eingefügt. Danach wird durch die folgenden rekursiven Aufrufe mit dem Teilfeld mit kleineren Indizes und dem Teilfeld mit größeren Indizes als pos analog verfahren. Nach Aufruf der Methode optimiereBaum() besitzen alle Blätter im Baum nahezu die gleiche Tiefe (der Baum ist balanciert/ausgeglichen).
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 Vorschlag AJ - Aufgabe 3.2-3.4 - Dynamische Daten… · LK 2021