MINT lernen

Übung — AFB I (Reproduzieren)

Zehn Grundaufgaben von DynArray bis Suchbaum — sichere Punkte für die Klausur.

Dein Fortschritt:
0 / 0 Aufgaben
1

Aufgabenblock — AFB I

Zehn Grundaufgaben zum Reproduzieren: Operation kennen, anwenden, Ergebnis angeben. Drei wiederholen die linearen Strukturen, sieben gehören zu den Binärbäumen — das sind die sicheren Punkte in der Klausur.

A1
Einfügen in die Reihung
AFB I

Auf l = [7, 3, 9, 4] wird l.insertAt(2, 5) ausgeführt. Welchen Wert liefert danach l.getItem(3)?

insertAt: Das Element an Index 2 und alle folgenden rücken eine Stelle nach hinten.
Lösung anzeigen
[7, 3, 5, 9, 4] — an Index 3 steht jetzt 9 = 9
A2
top nach pop
AFB I

Auf einem leeren Stapel laufen push(2), push(6), push(8) und pop(). Welchen Wert liefert danach top()?

LIFO: pop entfernt das zuletzt aufgelegte Element; top schaut nur nach.
Lösung anzeigen
pop entfernt die 8, oben liegt die 6 = 6
A3
Zweimal dequeue
AFB I

Auf einer leeren Schlange laufen enqueue(4), enqueue(1), enqueue(7). Danach wird zweimal dequeue() aufgerufen. Was liefert der zweite Aufruf?

FIFO: Entnommen wird vorn, in der Reihenfolge des Anstellens.
Lösung anzeigen
erst 4, dann 1 = 1
A4
Blätter zählen
AFB I
Binärbaum k (kein Suchbaum)
6834129

Wie viele Blätter hat der Binärbaum k?

Blatt: Knoten, dessen linker und rechter Teilbaum leer sind.
Lösung anzeigen
Blätter sind 6, 4 und 2 = 3
A5
Höhe
AFB I

Welche Höhe hat der Binärbaum k aus A4 (gezählt in Ebenen)?

Höhe: Anzahl der Ebenen = größte Tiefe + 1.
Lösung anzeigen
längster Weg 3 – 1 – 9 – 2 hat vier Ebenen = 4
A6
Einen Weg gehen
AFB I

Was liefert k.getRight().getRight().getItem() für den Baum k aus A4?

Weg lesen: getRight() = eine Ebene tiefer nach rechts, von der Wurzel aus.
Lösung anzeigen
3 → rechts 1 → rechts 9 = 9
A7
Preorder
AFB I

Gib die Preorder-Folge des Baums k aus A4 an (Werte ohne Trennzeichen oder mit Kommas).

Preorder: Wurzel – linker Teilbaum – rechter Teilbaum.
Lösung anzeigen
3, dann links 8, 6, dann rechts 1, 4, 9, 2 = 3 8 6 1 4 9 2
A8
Suchen zählen
AFB I
Suchbaum m
1020303540506070

Wie viele Vergleiche mit Knoten braucht die Suche nach 35 im Suchbaum m?

Suchen: kleiner → links, größer → rechts, jeder besuchte Knoten ist ein Vergleich.
Lösung anzeigen
40 → 20 → 30 → 35 = 4
A9
Wo landet die 25?
AFB I

In den Suchbaum m aus A8 wird 25 eingefügt. Von welchem Knoten wird 25 das linke Kind?

Einfügen: Suchpfad bis zum leeren Baum, dort wird der Wert als Blatt gesetzt.
Lösung anzeigen
25 < 40, 25 > 20, 25 < 30 → linker Teilbaum von 30 ist leer = 30
A10
Platz im Baum
AFB I

Wie viele Knoten hat ein Binärbaum der Höhe 4 höchstens?

Maximum: Auf Ebene k (Tiefe k) passen höchstens 2k Knoten; zusammen 2h − 1.
Lösung anzeigen
1 + 2 + 4 + 8 = 15