Lineare Datenstrukturen und Binärbäume: Probe-Klassenarbeit – Informatik Leistungskurs

Name

Datum

Punkte0 / 60

Notenpunkte—

Bearbeitet0 / 0

Bearbeitungszeit90 Minuten

AFB I

Wissen und Reproduzieren

18 Punkte

Lineare Strukturen

AFB I 4 Punkte

Gegeben sind DynArray<Integer> l = [5, 1, 8], ein leerer Stapel s und eine leere Schlange q. Die Teilaufgaben a) und b) bauen aufeinander auf.

a) Nach l.append(3): Was liefert l.getItem(3)? 1 P

getItem(3) =

b) Danach l.insertAt(1, 6): Was liefert l.getItem(2)? 1 P

getItem(2) =

c) s.push(4); s.push(9); — was liefert s.pop()? 1 P

s.pop() =

d) q.enqueue(4); q.enqueue(9); — was liefert q.dequeue()? 1 P

q.dequeue() =

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) [5, 1, 8, 3] → 3 b) [5, 6, 1, 8, 3] → 1 c) 9 (LIFO) d) 4 (FIFO) — je 1 P.

BinTree-Operationen

AFB I 4 Punkte

Ordnen Sie jeder Operation der Klasse BinTree (Ergänzende Hinweise 2025) ihre Wirkung zu. Es stehen mehr Wirkungen zur Auswahl, als gebraucht werden.

Wirkung zuordnen. 4 P

isLeaf()

setItem(x)

getRight()

setEmpty()

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: isLeaf → beide Teilbäume leer · setItem → Inhalt der Wurzel setzen · getRight → rechter Teilbaum · setEmpty → leerer Baum (je 1 P). Eine Operation „Anzahl der Knoten“ gibt es nicht.

Den Baum beschreiben

AFB I 6 Punkte

Binärbaum p

Beantworten Sie die Fragen zum Binärbaum p (Höhe in Ebenen).

a) Anzahl der Knoten 1 P

Knoten =

b) Anzahl der Blätter 1 P

Blätter =

c) Höhe von p 1 P

Höhe =

d) Tiefe des Knotens G 1 P

Tiefe =

e) Was liefert p.getLeft().getRight().getItem()? 1 P

Ergebnis:

f) Anzahl der leeren Teilbäume 1 P

leere Teilbäume =

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) 9 b) 4 (B, G, P, Z) c) 4 (z. B. K – E – H – G) d) 3 e) H f) n + 1 = 10 — je 1 P.

Aussagen prüfen

AFB I 4 Punkte

Welche Aussagen sind richtig?

Wählen Sie alle richtigen Aussagen. (mehrere Antworten richtig) 4 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: Richtig: Inorder sortiert; Blatt = zwei leere Teilbäume. Falsch: Die Preorder beginnt mit der Wurzel; neue Werte werden Blätter. Je richtige Auswahl 2 P, je Fehlklick 2 P Abzug.

AFB II

Zusammenhänge herstellen

26 Punkte

Traversierungen

AFB II 8 Punkte

Betrachten Sie wieder den Binärbaum p aus A3. Geben Sie die Folgen ohne Trennzeichen oder mit Kommas an.

a) Preorder 2 P

Preorder:

b) Inorder 2 P

Inorder:

c) Postorder 2 P

Postorder:

d) Wie oft wird eine rekursive Traversierung für p insgesamt aufgerufen? 2 P

Aufrufe =

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) K E B H G S P X Z b) B E G H K P S X Z — p ist ein Suchbaum c) B G H E P Z X S K d) 9 Knoten + 10 leere Bäume = 19 (je 2 P).

Einen Suchbaum aufbauen

AFB II 8 Punkte

In einen leeren binären Suchbaum werden nacheinander eingefügt: 50, 20, 80, 10, 40, 60, 90, 30, 70, 35.

a) Welche Höhe hat der Baum? 2 P

Höhe =

b) In welcher Tiefe liegt der Knoten 35? 2 P

Tiefe =

c) Wie viele Vergleiche kostet der gesamte Aufbau? 2 P

Vergleiche =

d) Geben Sie die Preorder-Folge an (Werte mit Kommas getrennt). 2 P

Preorder:

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: Baum: 50(20(10, 40(30(∅, 35), ∅)), 80(60(∅, 70), 90)). a) 5 b) 4 (50 → 20 → 40 → 30 → 35) c) Summe der Tiefen: 1 + 1 + 2 + 2 + 2 + 2 + 3 + 3 + 4 = 20 d) 50, 20, 10, 40, 30, 35, 80, 60, 70, 90 (je 2 P).

Iterative Suche

AFB II 6 Punkte

Die Methode soll prüfen, ob x im Suchbaum b vorkommt:

static boolean enthaelt(BinTree<Integer> b, int x) {
    while (!b.isEmpty()) {                          // Zeile 2
        if (x == b.getItem()) return true;          // Zeile 3
        if (x < b.getItem()) b = b.getLeft();       // Zeile 4
        b = b.getRight();                           // Zeile 5
    }
    return false;                                   // Zeile 7
}

a) Welche Aussage beschreibt den Fehler? 3 P

b) Wie viele Vergleiche mit Knoten braucht die korrigierte Methode, um 65 im Baum aus A6 zu suchen? 3 P

Vergleiche =

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) In Zeile 5 fehlt else: Ist x kleiner, wird erst nach links und im selben Durchlauf nach rechts gegangen — ganze Teilbäume werden übersprungen (3 P). b) 50 → 80 → 60 → 70, danach der leere linke Teilbaum von 70: 4 Vergleiche (3 P).

Rechenbaum und Stapel

AFB II 4 Punkte

Die Postorder eines Rechenbaums lautet 8 3 - 4 2 + *. Sie wird mit einem Stapel ausgewertet (Zahl → push; Operator → zweimal pop, rechnen, Ergebnis pushen).

a) Welches Ergebnis bleibt im Stapel? 2 P

Ergebnis =

b) Wie viele Werte liegen höchstens gleichzeitig im Stapel? 2 P

Maximum =

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) (8 − 3) · (4 + 2) = 30 b) Nach 8 3 − 4 2 liegen 5, 4, 2 im Stapel: 3 (je 2 P).

AFB III

Verallgemeinern und beurteilen

16 Punkte

Sortiert eingefügt

AFB III 8 Punkte

Ein Programm fügt 20 Messwerte in einen leeren Suchbaum ein. Die Werte kommen bereits aufsteigend sortiert an.

a) Wie viele Vergleiche kostet der Aufbau insgesamt? 3 P

Vergleiche =

b) Welche Höhe hätte ein Suchbaum mit diesen 20 Werten mindestens? 2 P

Mindesthöhe =

c) Welches Urteil über das Verfahren trägt? 3 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) 0 + 1 + … + 19 = 20 · 19 : 2 = 190 (3 P) b) 2⁴ − 1 = 15 < 20 ≤ 31 = 2⁵ − 1 → 5 (2 P) c) Die Kette hat Höhe 20; mit „Mitte zuerst, dann rekursiv die Hälften“ entsteht Höhe 5 (3 P).

A10

Preorder ohne Rekursion

AFB III 8 Punkte

Eine Preorder-Ausgabe soll ohne Rekursion arbeiten. Dazu wird ein Stack<BinTree<String>> verwendet: Zu Beginn wird der ganze Baum gepusht; solange der Stapel nicht leer ist, wird ein Teilbaum entnommen und — falls nicht leer — seine Wurzel ausgegeben; danach werden seine beiden Teilbäume gepusht.

a) In welcher Reihenfolge müssen die Teilbäume gepusht werden? 4 P

b) Welche Aussagen treffen zu? (mehrere Antworten richtig) 4 P

Lösung anzeigen (nach Auswerten freigeschaltet)

Erwartungshorizont: a) Wegen LIFO muss der rechte Teilbaum zuerst abgelegt werden, damit der linke oben liegt (4 P). b) Richtig: Stapel ersetzt den Aufrufstapel; mit einer Schlange (FIFO) entsteht die Ausgabe Ebene für Ebene. Falsch: keine Postorder; gepusht werden n Knoten-Teilbäume und n + 1 leere, also 2n + 1 (je richtige Auswahl 2 P, je Fehlklick 2 P Abzug).

Ergebnis

Erreicht

0 / 60

Prozent

0 %

Notenpunkte

—

Aufgabe	Thema	Punkte

Punkteverteilung

Aufgabe	Thema	AFB	Punkte
A1	Lineare Strukturen	AFB I	4
A2	BinTree-Operationen	AFB I	4
A3	Den Baum beschreiben	AFB I	6
A4	Aussagen prüfen	AFB I	4
A5	Traversierungen	AFB II	8
A6	Einen Suchbaum aufbauen	AFB II	8
A7	Iterative Suche	AFB II	6
A8	Rechenbaum und Stapel	AFB II	4
A9	Sortiert eingefügt	AFB III	8
A10	Preorder ohne Rekursion	AFB III	8
Summe (AFB I: 18 P · AFB II: 26 P · AFB III: 16 P)			60

Notenschema (Notenpunkte der Oberstufe)

Leistungskurs-Fassung: 60 P in 90 Minuten, Schwerpunkt Binärbäume. Die Prozentgrenzen entsprechen der Oberstufen-Tabelle (15 NP ab 95 %, 5 NP ab 45 %).

Punkte	Notenpunkte	Beurteilung
57 – 60 P	15	sehr gut +
54 – 56 P	14	sehr gut
51 – 53 P	13	sehr gut −
48 – 50 P	12	gut +
45 – 47 P	11	gut
42 – 44 P	10	gut −
39 – 41 P	9	befriedigend +
36 – 38 P	8	befriedigend
33 – 35 P	7	befriedigend −
30 – 32 P	6	ausreichend +
27 – 29 P	5	ausreichend
24 – 26 P	4	ausreichend −
20 – 23 P	3	mangelhaft +
16 – 19 P	2	mangelhaft
12 – 15 P	1	mangelhaft −
0 – 11 P	0	ungenügend

Probe-Klausur

Wissen und Reproduzieren

Zusammenhänge herstellen

Verallgemeinern und beurteilen

Ergebnis

Punkteverteilung

Notenschema (Notenpunkte der Oberstufe)