MINT üben

Lineare Strukturen, Binärbäume

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).