Aufgabe Vorschlag AJ - Aufgabe 3.2-3.4 - Dynamische Daten… · 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 }
3.2
Geben Sie eine mögliche Reihenfolge an, in der die 13 Teilnehmer gestartet sein könnten. (2 BE)
3.3
Comanche darf den zweiten Durchgang beginnen und erreicht in diesem 37 Ringe. Danach folgt Amazone mit 48 Ringen.
Beschreiben Sie, wie der Knoten „Comanche“ aus dem vorliegenden Baum gelöscht und danach an der korrekten Stelle wieder eingefügt wird. Zeichnen Sie den Ergebnisbaum, nachdem die Ergebnisse von Comanche und Amazone eingetragen sind. (5 BE)
3.4
Im Verlauf des Turniers erhöht sich die Anzahl der Ringe für die einzelnen Teilnehmer.
Beschreiben Sie, wie der Baum beim zweiten und dritten Durchgang seine Gestalt verändert und was das für die Laufzeit des Einfügens, Löschens und Suchens von Teilnehmern im Baum bedeutet. (3 BE)
Lösung
Nach den offiziellen Korrekturhinweisen
3.2 Geben Sie eine mögliche Reihenfolge an, in der die 13 Teilnehmer gestartet sein könnten.
Lösung: Slowhand 67 – Trapper 50 – Amor 86 – Freischütz 41 – Comanche 55 – Robin 82 – Liebespfeil 97 – Dorfjunge 52 – Waldmeister 60 – Listiger Lurch 79 – Herzbub 84 – Oberförster 88 – Amazone 57
3.3 Beschreiben Sie, wie der Knoten „Comanche“ aus dem vorliegenden Baum gelöscht und danach an der korrekten Stelle wieder eingefügt wird.
Lösung: Da der Knoten „Comanche“ kein Blatt des Baumes darstellt, müssen die Kindknoten verschoben werden. Der gelöschte Knoten wird nun entweder durch das größte Element des linken Teilbaumes (Dorfjunge) oder das kleinste Element des rechten Teilbaumes (Amazone) ersetzt. Da beide Knoten Blätter sind, entfallen weitere Verschiebungen. Comanche hat nun insgesamt 92 Punkte. Um einen Knoten in einen Binärbaum einzufügen, vergleicht man den Wert zuerst mit der Wurzel des Baumes. Da der Wert von Comanche größer ist als der von Slowhand, vergleicht man Comanches Ringzahl mit der von Slowhands rechtem Kindknoten. Dieser ebenso wie jeder weitere Vergleich der Punktzahl entscheidet, ob im linken oder rechten Teilbaum auf die gleiche Weise fortgefahren wird. Der Vorgang wird solange wiederholt, bis der entsprechende Kindknoten nicht existiert. An dieser Stelle wird Comanche zu einem neuen Blatt.
3.3 Zeichnen Sie den Ergebnisbaum, nachdem die Ergebnisse von Comanche und Amazone eingetragen sind.
Lösung: Der Ergebnisbaum zeigt: - Wurzel: Slowhand (67) - Linker Teilbaum von Slowhand: Trapper (50); linker Nachfolger Freischütz (41), rechter Nachfolger Waldmeister (60) (bzw. Dorfjunge 52 bei alternativer Ersetzung); Dorfjunge (52) als linker Nachfolger von Waldmeister. - Rechter Teilbaum von Slowhand: Amor (86); links Robin (82) mit Listiger Lurch (79) und Herzbub (84); rechts Liebespfeil (97) mit Oberförster (88) links und Amazone (105) rechts; Comanche (92) als rechter Nachfolger von Oberförster (88).
3.4 Beschreiben Sie, wie der Baum beim zweiten und dritten Durchgang seine Gestalt verändert und was das für die Laufzeit des Einfügens, Löschens und Suchens von Teilnehmern im Baum bedeutet.
Lösung: Da die Ringe der weiteren Durchläufe zu den schon vorhandenen addiert werden, erhöht sich die Anzahl der Ringe. Teilnehmer, die sich im linken Teilbaum befanden, werden dann nach dem zweiten und dritten Durchlauf in der Regel im rechten Teilbaum eingeordnet. Die Tiefe des Baumes nimmt also immer weiter zu. Für die genannten Operationen bedeutet das, dass ihre Laufzeit nicht mehr logarithmisch ist, sondern sich immer weiter einer linearen Laufzeit annähert.
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 4 · LK 2022 · Aufgabe Vorschlag AJ - Aufgabe 4 · LK 2021 ›