Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn du nicht weiterkommst, helfen die gestuften Tipps.
A1
Suchbaum oder nicht?
AFB IDie Bäume sind in der Schreibweise Wurzel(links, rechts) notiert, ∅ ist ein leerer Baum. Gib für jeden Baum an, ob er ein binärer Suchbaum ist.
Ziehe jede Karte in den passenden Korb — oder wähle sie mit Enter aus und drücke dann die Ziffer des Korbs (0 legt sie zurück).
1Suchbaum
2kein Suchbaum
Fallen sind 8(3(1, 9), 12) und 8(3, 12(7, 15)): Die 9 steht im linken Teilbaum von 8, die 7 im rechten — die Ordnung gilt für ganze Teilbäume, nicht nur für direkte Kinder.
Ansatz: Prüfe nicht nur Elternknoten und Kind, sondern jeden Knoten gegen alle seine Vorfahren.
Weiter: Alles im linken Teilbaum von 8 muss kleiner als 8 sein — auch die Enkel.
A2
Stimmt's? — Suchen in s
AFB ILies am Suchbaum s ab, ob die Aussagen stimmen.
Suchbaum s
5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann startest du die Serie mit „Neue Runde“ neu.
Jeder Vergleich schließt einen ganzen Teilbaum aus — deshalb berührt die Suche nie beide Seiten.
Ansatz: Fahre den Suchpfad mit dem Finger nach.
Weiter: Zähle nur Vergleiche mit Knoten, nicht den leeren Baum am Ende.
A3
Der Suchalgorithmus in Worten
AFB INenne die fehlenden Begriffe im Suchalgorithmus.
Wort anklicken, dann Lücke anklicken (oder umgekehrt) — mit Tab und Enter geht es genauso. Ein Klick auf eine gefüllte Lücke legt das Wort zurück.
Die Suche vergleicht x zuerst mit der . Ist x kleiner, geht sie im Teilbaum weiter, ist x größer, im Teilbaum. Erreicht sie einen , kommt x nicht vor. Sie braucht höchstens so viele Vergleiche, wie die des Baums angibt.
„Blatt“ passt nicht: Auch unter einem Blatt geht die Suche noch einen Schritt weiter — in einen leeren Teilbaum.
Ansatz: Die vier Fälle stehen in der Merke-Box.
Weiter: Die Suche endet erfolglos nicht an einem Blatt, sondern darunter.