Datenstrukturen
Eine Datenstruktur sieht im Speicher so aus: [12 | •] → [7 | •] → [30 | null]. Jedes Element traegt einen Wert und einen Verweis. Welche Struktur ist das?
Erklärung: In einer verketteten Liste besteht jeder Knoten aus Datenteil und Verweis auf den naechsten Knoten; der letzte verweist auf null. Ein Array liegt am Stueck im Speicher ohne Verweise, ein Binaerbaum haette bis zu zwei Verweise pro Knoten.
Bei einem Stapel (Stack) gilt das ___-Prinzip: Das zuletzt eingefuegte Element wird zuerst entnommen.
Erklärung: LIFO = Last In, First Out. Wie bei einem Buecherstapel: Man legt oben drauf (push) und nimmt oben weg (pop). Anwendungen: Funktionsaufrufe, Klammerung pruefen, Undo-Operationen.
In eine leere Warteschlange (Queue) werden nacheinander 4, 7 und 9 eingefuegt. Beim ersten Entnehmen erhaelt man die 4.
Erklärung: Richtig. Eine Queue arbeitet nach dem FIFO-Prinzip (First In, First Out) — die zuerst eingefuegte 4 wird zuerst entnommen. Elemente kommen hinten dazu (enqueue) und vorne heraus (dequeue).
Welche zwei grundlegenden Operationen definieren einen Stapel (Stack)?
Erklärung: push legt ein Element oben auf den Stapel, pop entfernt das oberste Element. Oft gibt es zusaetzlich peek (oberstes Element ansehen ohne zu entfernen) und isEmpty.
Ein Binaerbaum ist ein Baum, bei dem jeder Knoten hoechstens ___ Kindknoten hat.
Erklärung: In einem Binaerbaum hat jeder Knoten maximal zwei Kinder: ein linkes und ein rechtes Kind. Binaerbaeume sind die Grundlage fuer binaere Suchbaeume, Heaps und viele weitere Datenstrukturen.
In einem Baum hat der Knoten 8 die Kinder 3 und 10; der Knoten 3 hat das Kind 1. Welcher Knoten ist die Wurzel?
Erklärung: Die Wurzel ist der oberste Knoten — der einzige ohne Elternknoten. Das ist hier die 8. Die 1 ist ein Blatt (Knoten ohne Kinder), die 10 ein Kind der Wurzel. Der groesste Wert spielt keine Rolle.
Ein vollstaendiger Binaerbaum hat 3 Ebenen (Wurzel = Ebene 1). Wie viele Knoten hat er insgesamt?
Erklärung: Ebene 1: 1 Knoten (Wurzel), Ebene 2: 2 Knoten, Ebene 3: 4 Knoten. Gesamt: 1 + 2 + 4 = 7. Allgemein hat ein vollstaendiger Binaerbaum mit h Ebenen 2^h - 1 Knoten.
Ordne die Schritte zum Einfuegen eines Elements am Anfang einer verketteten Liste in die richtige Reihenfolge:
Erklärung: Die Reihenfolge ist wichtig: Zuerst den neuen Knoten anlegen, dann seinen next-Verweis setzen, und erst dann den Kopf umhaengen. Sonst verliert man den Zugriff auf die restliche Liste.
In einem binaeren Suchbaum steht die 8 als LINKES Kind des Knotens 5. Kann das ein gueltiger Suchbaum sein?
Erklärung: Nein. Die Suchbaum-Eigenschaft verlangt: Im linken Teilbaum stehen nur kleinere Werte als im Elternknoten, im rechten nur groessere. 8 > 5 muesste also rechts stehen. Diese Ordnung ermoeglicht Suchen in O(log n).
Welche Traversierungsart eines Binaerbaums besucht zuerst den linken Teilbaum, dann die Wurzel, dann den rechten Teilbaum?
Erklärung: Inorder: links - Wurzel - rechts. Bei einem binaeren Suchbaum liefert Inorder die Elemente in sortierter Reihenfolge. Preorder: Wurzel - links - rechts. Postorder: links - rechts - Wurzel.
Eine Datenstruktur, bei der Elemente hinten angefuegt und vorne entnommen werden, heisst ___ (englischer Fachbegriff).
Erklärung: Eine Queue (Warteschlange) arbeitet nach dem FIFO-Prinzip. Typische Anwendungen: Druckerwarteschlange, Breitensuche in Graphen, Pufferung von Nachrichten.
Ordne die Baumtraversierungen der Reihenfolge zu, in der sie die Wurzel besuchen (von frueh nach spaet):
Erklärung: Pre = vor (Wurzel vor den Teilbaeumen), In = zwischen (Wurzel zwischen den Teilbaeumen), Post = nach (Wurzel nach den Teilbaeumen). Das Praefix sagt, wann die Wurzel besucht wird.
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?
Erklärung: Der Baum hat 3 Ebenen: Wurzel 5, Ebene 2: 3 und 8, Ebene 3: 1, 4, 7, 9. Um z. B. die 9 zu finden: 5 (rechts), 8 (rechts), 9 (gefunden) = 3 Vergleiche.
Knoten in einem Baum, die keine Kinder haben, werden als ___ bezeichnet.
Erklärung: Blaetter (Blattknoten) sind die Endpunkte eines Baumes. Sie haben keine Kindknoten. Innere Knoten hingegen haben mindestens ein Kind.
Welche Datenstruktur eignet sich am besten fuer die Breitensuche (BFS) in einem Graphen?
Erklärung: Die Breitensuche verwendet eine Queue: Der Startknoten wird eingefuegt. In jedem Schritt wird der vorderste Knoten entnommen und seine Nachbarn werden hinten angefuegt. So werden Knoten ebenenweise besucht.
Ein Stapel (Stack) eignet sich besonders gut zur Implementierung der Tiefensuche (DFS).
Erklärung: Richtig. Die Tiefensuche geht so tief wie moeglich in den Graphen, bevor sie zurueckkehrt. Dies entspricht dem LIFO-Prinzip eines Stacks. Alternativ kann DFS auch rekursiv implementiert werden (der Call-Stack dient dann als Stapel).
Ordne die folgenden Datenstrukturen nach ihrer typischen Zugriffsart (von eingeschraenkt zu flexibel):
Erklärung: Stack und Queue schraenken den Zugriff bewusst ein (Datenkapselung). Eine verkettete Liste erlaubt sequentiellen Zugriff. Ein Array ermoeglicht direkten Zugriff auf jede Position in O(1).
Ein vollstaendiger Binaerbaum hat 4 Ebenen. Wie viele Blattknoten hat er?
Erklärung: In einem vollstaendigen Binaerbaum mit h Ebenen hat die unterste Ebene 2^(h-1) Blaetter. Bei 4 Ebenen: 2^3 = 8 Blaetter. Gesamtzahl Knoten: 2^4 - 1 = 15.
Vor 1.000.000 gespeicherte Elemente soll ein neues Element ganz vorne eingefuegt werden. Wie viele bestehende Elemente muessen dafuer bewegt werden?
Erklärung: Im Array muss jedes Element eine Position nach rechts ruecken (O(n)). In der verketteten Liste haengt man nur zwei Verweise um (O(1)) — kein Element wird bewegt. Das ist ihr grosser Vorteil beim Einfuegen.
Die ___ eines binaeren Suchbaums gibt an, wie viele Ebenen er hat. Ein entarteter Baum hat eine grosse, ein balancierter Baum eine kleine.
Erklärung: Die Hoehe bestimmt die Effizienz der Suche. Ein balancierter Baum mit n Knoten hat Hoehe O(log n), ein entarteter (zur Liste degradierter) Baum hat Hoehe O(n). Balancierte Baeume (AVL, Rot-Schwarz) halten die Hoehe gering.