Datenstrukturen
Data Structures
Jenseits des Arrays gibt es dynamische Strukturen, die mit den Daten wachsen: die verkettete Liste, der Stapel (LIFO), die Schlange (FIFO) und der Binärbaum. Die bayerische Implementierung nutzt das Kompositum-Muster — Knoten und Abschluss teilen eine Oberklasse, Operationen wandern polymorph durch die Struktur, Bäume werden rekursiv durchlaufen. Die tragende Auswahlfrage: Welche Struktur passt zu welchem Zugriffsmuster — Index-Zugriff (Array), nur oben (Stapel), vorn entnehmen (Schlange), sortiert suchen (Suchbaum)?
Voraussetzungen (3)
Ermöglicht (1)
Eine Datenstruktur sieht im Speicher so aus: [12 | •] → [7 | •] → [30 | null]. Jedes Element traegt einen Wert und einen Verweis. Welche Struktur ist das?
Bei einem Stapel (Stack) gilt das ___-Prinzip: Das zuletzt eingefuegte Element wird zuerst entnommen.
In eine leere Warteschlange (Queue) werden nacheinander 4, 7 und 9 eingefuegt. Beim ersten Entnehmen erhaelt man die 4.
Welche zwei grundlegenden Operationen definieren einen Stapel (Stack)?
Ein Binaerbaum ist ein Baum, bei dem jeder Knoten hoechstens ___ Kindknoten hat.
In einem Baum hat der Knoten 8 die Kinder 3 und 10; der Knoten 3 hat das Kind 1. Welcher Knoten ist die Wurzel?
Ein vollstaendiger Binaerbaum hat 3 Ebenen (Wurzel = Ebene 1). Wie viele Knoten hat er insgesamt?
Eine Datenstruktur, bei der Elemente hinten angefuegt und vorne entnommen werden, heisst ___ (englischer Fachbegriff).
Knoten in einem Baum, die keine Kinder haben, werden als ___ bezeichnet.
Ordne die Schritte zum Einfuegen eines Elements am Anfang einer verketteten Liste in die richtige Reihenfolge:
In einem binaeren Suchbaum steht die 8 als LINKES Kind des Knotens 5. Kann das ein gueltiger Suchbaum sein?
Welche Traversierungsart eines Binaerbaums besucht zuerst den linken Teilbaum, dann die Wurzel, dann den rechten Teilbaum?
Ordne die Baumtraversierungen der Reihenfolge zu, in der sie die Wurzel besuchen (von frueh nach spaet):
Ein binaerer Suchbaum enthaelt die Werte 5, 3, 8, 1, 4, 7, 9 (in dieser Reihenfolge eingefuegt). Wie viele Vergleiche braucht man maximal, um einen Wert zu finden?
Welche Datenstruktur eignet sich am besten fuer die Breitensuche (BFS) in einem Graphen?
Ein Stapel (Stack) eignet sich besonders gut zur Implementierung der Tiefensuche (DFS).
Ordne die folgenden Datenstrukturen nach ihrer typischen Zugriffsart (von eingeschraenkt zu flexibel):
Ein vollstaendiger Binaerbaum hat 4 Ebenen. Wie viele Blattknoten hat er?
Vor 1.000.000 gespeicherte Elemente soll ein neues Element ganz vorne eingefuegt werden. Wie viele bestehende Elemente muessen dafuer bewegt werden?
Die ___ eines binaeren Suchbaums gibt an, wie viele Ebenen er hat. Ein entarteter Baum hat eine grosse, ein balancierter Baum eine kleine.