MINT lernen

Übung — AFB II (Zusammenhänge herstellen)

Zehn Aufgaben zum Nachverfolgen — von der Löschschleife bis zum Suchbaum.

Dein Fortschritt:
0 / 0 Aufgaben
2

Aufgabenblock — AFB II

Zehn Aufgaben aus dem ganzen Kapitel: Abläufe nachverfolgen, Bäume rekonstruieren, Aufwand bestimmen — mit gestuften Tipps, wenn du nicht weiterkommst.

A1
Rückwärts löschen
AFB II

Aus l = [7, 2, 9, 1, 5] werden mit einer Rückwärts-Schleife und delete(i) alle Werte kleiner als 5 entfernt.

a) Welche Länge hat l danach? b) Was liefert danach getItem(1)?

Ansatz: Von Index 4 bis 0 prüfen; beim Löschen rücken nur schon geprüfte Elemente nach.
Weg: i = 3 löscht die 1, i = 1 löscht die 2 → [7, 9, 5].
Lösung: a) 3 b) 9
Vollständige Lösung
Rückwärts wird kein Element übersprungen: [7, 9, 5] hat die Länge 3, an Index 1 steht 9.
A2
Schlange umdrehen
AFB II

Die Schlange q = [3, 8, 5] (vorn links) wird mit einem leeren Stapel umgedreht: Erst werden alle Elemente mit dequeue entnommen und auf den Stapel gelegt, dann alle mit pop entnommen und mit enqueue angestellt.

a) Was liefert danach q.head()? b) Wie viele Elemente liegen höchstens gleichzeitig im Stapel?

Ansatz: Der Stapel kehrt die Reihenfolge um.
Weg: Stapel von unten: 3, 8, 5 → pop liefert 5, 8, 3 → q = [5, 8, 3].
Lösung: a) 5 b) 3
Vollständige Lösung
Alle drei Elemente liegen zwischendurch im Stapel; danach steht die 5 vorn. Stapel + Schlange ergeben eine Umkehrung.
A3
Inorder und Einzelkinder
AFB II
Binärbaum t
ADFHMRTW

Betrachte den Binärbaum t.

a) Gib die Inorder-Folge an (ohne Trennzeichen oder mit Kommas). b) Wie viele Knoten haben genau ein Kind?

Ansatz: Inorder: links – Wurzel – rechts, in jedem Teilbaum.
Weg: Linker Teilbaum ergibt A D F H, dann M, rechts R T W. Einzelkinder haben H, R und W.
Lösung: a) A D F H M R T W b) 3
Vollständige Lösung
Die Inorder ist alphabetisch — t ist ein Suchbaum. Genau ein Kind haben H (nur links F), R (nur rechts W) und W (nur links T).
A4
Baum rekonstruieren
AFB II

Von einem Binärbaum kennt man die Preorder 6 2 1 4 9 8 und die Inorder 1 2 4 6 8 9.

a) Welcher Wert ist Wurzel des rechten Teilbaums? b) Gib die Postorder an.

Ansatz: Die Preorder beginnt mit der Wurzel; in der Inorder teilt sie links und rechts.
Weg: Wurzel 6; links {1, 2, 4} mit Wurzel 2, rechts {8, 9} mit Wurzel 9 und linkem Kind 8.
Lösung: a) 9 b) 1 4 2 8 9 6
Vollständige Lösung
Baum: 6(2(1, 4), 9(8, ∅)). Postorder: 1 4 2 8 9 6.
A5
Suchbaum aufbauen
AFB II

In einen leeren Suchbaum werden 45, 20, 70, 10, 30, 60, 90, 25, 65 eingefügt.

a) Welche Höhe hat der Baum? b) Wie viele Vergleiche kostet der Aufbau insgesamt?

Ansatz: Jeder Wert braucht beim Einfügen so viele Vergleiche, wie seine Tiefe angibt.
Weg: Tiefen: 45:0, 20:1, 70:1, 10:2, 30:2, 60:2, 90:2, 25:3, 65:3.
Lösung: a) 4 b) 16
Vollständige Lösung
25 wird linkes Kind von 30, 65 rechtes Kind von 60 — Höhe 4. Summe der Tiefen: 0 + 1 + 1 + 4 · 2 + 2 · 3 = 16.
A6
Sortiert eingefügt
AFB II

Die Zahlen 1 bis 8 werden aufsteigend in einen leeren Suchbaum eingefügt.

a) Welche Höhe hat der Baum? b) Wie viele Vergleiche kostet der Aufbau?

Ansatz: Jeder neue Wert ist größer als alle vorhandenen.
Weg: Kette nach rechts; Vergleiche 0 + 1 + … + 7.
Lösung: a) 8 b) 28
Vollständige Lösung
Der Baum entartet zur Kette: Höhe 8. Vergleiche: 8 · 7 : 2 = 28.
A7
Was berechnet f?
AFB II
Baum für A7
1358

Gegeben ist static int f(BinTree<Integer> b) { if (b.isEmpty()) return 0; return b.getItem() + f(b.getLeft()) + f(b.getRight()); }

a) Was liefert f für den abgebildeten Baum? b) Wie oft wird f dabei insgesamt aufgerufen?

Ansatz: f addiert die Inhalte aller Knoten.
Weg: 5 + 3 + 1 + 8 = 17; Aufrufe: 4 Knoten + 5 leere Bäume.
Lösung: a) 17 b) 9
Vollständige Lösung
f bildet die Summe aller Knoteninhalte. Aufgerufen wird sie für jeden Knoten und jeden leeren Teilbaum: 2n + 1 = 9.
A8
Postorder mit dem Stapel
AFB II

Die Postorder eines Rechenbaums lautet 4 6 + 2 *. Sie wird mit einem Stapel ausgewertet: Zahl → push; Operator → zweimal pop, rechnen, push.

a) Welches Ergebnis liegt am Ende im Stapel? b) Wie viele Werte liegen höchstens gleichzeitig darin?

Ansatz: Spiele Zeichen für Zeichen durch.
Weg: [4] → [4, 6] → [10] → [10, 2] → [20].
Lösung: a) 20 b) 2
Vollständige Lösung
Der Term ist (4 + 6) · 2 = 20. Es liegen nie mehr als zwei Werte im Stapel.
A9
Höhe bei 1000 Knoten
AFB II

Ein binärer Suchbaum enthält 1000 Schlüssel.

a) Welche Höhe hat er mindestens? b) Welche Höhe kann er höchstens haben?

Ansatz: Nutze n ≤ 2h − 1.
Weg: 29 − 1 = 511 < 1000 ≤ 1023 = 210 − 1; entartet: Kette.
Lösung: a) 10 b) 1000
Vollständige Lösung
Ausgeglichen genügen 10 Ebenen; als Kette hat jeder Knoten eine eigene Ebene: 1000.
A10
Doppelte Werte
AFB II

In einen leeren Suchbaum werden nacheinander 7, 3, 7, 9, 3, 1 eingefügt.

a) Wie viele Knoten hat der Baum? b) Wie viele davon sind Blätter?

Ansatz: Ein vorhandener Wert wird gefunden und nicht erneut eingefügt.
Weg: Baum: 7 mit linkem Kind 3 (dessen linkes Kind 1) und rechtem Kind 9.
Lösung: a) 4 b) 2
Vollständige Lösung
Die zweite 7 und die zweite 3 fallen weg. Blätter sind 1 und 9; die 3 hat das linke Kind 1.