Quiz: Datenstrukturen & Algorithmen
Kannst du einen Binärbaum durchsuchen?
Willkommen zu meinem Datenstrukturen‑ und Algorithmen‑Quiz!
Dieses Quiz prüft Ihr Wissen über Datenstrukturen (Stacks, Listen, Bäume usw.), Algorithmen und die Zeitkomplexität.
20 Fragen… Los!
Welche Datenstruktur eignet sich am besten für ein LIFO‑Muster (Last In, First Out)?
Stapel sind ideal für LIFO‑Zugriffsmuster. Warteschlangen eignen sich am besten für FIFO (First In, First Out).
Welches Element muss bei Last In, First Out als Erstes entfernt werden?
Wie lautet die Zeitkomplexität eines Algorithmus, der immer die gleiche Laufzeit hat, unabhängig von der Eingabegröße?
O(1) steht für konstante Zeitkomplexität. Es bedeutet, dass der Algorithmus immer die gleiche Laufzeit hat, unabhängig von der Eingabegröße.
Wächst der Aufwand überhaupt mit der Eingabegröße?
Wenn eine einfach verkettete Liste ihre Länge nicht speichert, welche Zeitkomplexität hat deren Berechnung durch Durchlaufen der Liste?
Um die Länge einer einfach verketteten Liste zu berechnen, muss man jeden Knoten vom ersten bis zum letzten Knoten durchlaufen, was zu einer Zeitkomplexität von O(n) führt.
Die Länge ist nicht gespeichert. Wie viele Knoten müssen besucht werden?
Wie lautet die durchschnittliche Zeitkomplexität für das Nachschlagen eines Elements in einem balancierten Binären Suchbaum?
In einem balancierten BST ist die durchschnittliche Zeitkomplexität für die Suche O(log n), weil jede Ebene den Suchraum halbiert.
Betrachte die Höhe eines balancierten binären Suchbaums.
Wie lautet die Zeitkomplexität des Merge‑Sort‑Algorithmus im schlechtesten Fall?
Merge Sort hat immer eine Worst‑Case‑Komplexität von O(n log n), da es das Array wiederholt halbiert und die sortierten Teilarrays zusammenführt.
Pro Aufteilungsebene werden die Elemente zusammengeführt. Wie viele Ebenen gibt es?
Welche Datenstruktur wird typischerweise verwendet, um Breitensuche (Breadth-First Search, BFS) zu implementieren?
BFS verwendet eine Warteschlange, um Knoten Ebene für Ebene zu erkunden und verarbeitet Knoten breitensuchartig (nach “Zeile”).
Der nächste Knoten muss in der Reihenfolge seiner Entdeckung verarbeitet werden.
Welche Traversierung erkennt einen gerichteten Zyklus anhand einer Kante zu einem Knoten, der noch auf ihrem Rekursionsstack liegt?
Tiefensuche (Depth-First Search, DFS) wird typischerweise verwendet, um Zyklen in einem Graphen zu erkennen, indem ein Rekursions‑Stack geführt wird, der besuchte Knoten nachverfolgt.
Welche Suche hält den noch aktiven Pfad in einem Rekursionsstack?
Wie lautet die Zeitkomplexität von Heap Sort im schlechtesten Fall?
Heap Sort hat eine worst‑case Zeitkomplexität von O(n log n), da es einen Heap aufbaut und wiederholt das maximale Element extrahiert.
Das Entfernen des größten Heap-Elements wird für alle Elemente wiederholt.
Wie lautet die durchschnittliche Zeitkomplexität für den Zugriff auf ein Element in einer Hash‑Tabelle?
Hash‑Tabellen haben eine durchschnittliche Zeitkomplexität von O(1) für den Zugriff auf Elemente, vorausgesetzt, es gibt eine gute Hash‑Funktion, die Kollisionen minimiert.
Betrachte den durchschnittlichen Zugriff bei einer guten Hash-Verteilung.
Welche Menge enthält typische Operationen, die auf einem Stack ausgeführt werden?
Die grundlegenden Operationen eines Stacks sind Push (Element hinzufügen), Pop (Element entfernen) und Peek (das oberste Element ansehen, ohne es zu entfernen).
Ein Stack fügt oben hinzu, entfernt oben und kann das oberste Element ansehen.
Welcher gierige Kürzeste-Wege-Algorithmus wählt ausgehend von einem Startknoten wiederholt den noch nicht abgeschlossenen Knoten mit der kleinsten vorläufigen Entfernung, typischerweise mit einer Prioritätswarteschlange, und setzt nicht negative Kantengewichte voraus?
Der Algorithmus von Dijkstra wird häufig zum Finden des kürzesten Pfades in Graphen mit nicht‑negativen Kantengewichten verwendet. Er nutzt eine Prioritätswarteschlange, um die kürzeste Entfernung effizient zu bestimmen.
Gesucht ist der gierige Algorithmus mit einer Prioritätswarteschlange und nicht negativen Gewichten.
Welche Menge enthält Beispiele für selbstbalancierende binäre Suchbaum-Datenstrukturen?
AVL‑Bäume und Rot-Schwarz‑Bäume sind Arten von selbstbalancierenden Bäumen, die dafür sorgen, dass der Baum nach jeder Einfügung oder Löschung ausgeglichen bleibt.
Welche Suchbäume stellen nach Änderungen ihre Balance wieder her?
Was muss in einer rekursiven Funktion definiert werden, um unendliche Rekursion zu verhindern?
Ein Basisfall ist in einer rekursiven Funktion notwendig, um die rekursiven Aufrufe zu stoppen, wenn eine bestimmte Bedingung erfüllt ist, und so unendliche Rekursion zu verhindern.
Welche Bedingung beendet die rekursiven Aufrufe?
Was sind die beiden Hauptoperationen einer Warteschlange?
Die beiden Hauptoperationen einer Warteschlange sind Einreihen (ein Element am Ende hinzufügen) und Ausreihen (ein Element am Anfang entfernen).
Ein Element wird am Ende eingefügt und am Anfang entfernt.
Welche Bedingungen müssen erfüllt sein, um eine topologische Sortierung auf einem Graphen durchzuführen?
Eine topologische Sortierung kann auf einem Graphen durchgeführt werden, wenn er gerichtet und azyklisch (DAG) ist. Diese Art der Anordnung ist nützlich bei Aufgabenplanungsproblemen.
Ein Zyklus würde eine Reihenfolge mit allen Vorgängern vor ihren Nachfolgern verhindern.
Wie ist die Zeitkomplexität einer naiven rekursiven Implementierung der Fibonacci‑Reihe?
Die naive rekursive Implementierung der Fibonacci‑Reihe hat eine Zeitkomplexität von O(2^n) wegen der umfangreichen wiederholten Berechnungen für jede Fibonacci‑Zahl.
Die naive Rekursion berechnet dieselben Teilprobleme immer wieder.
Welche Datenstruktur wird üblicherweise verwendet, um eine Prioritätswarteschlange zu implementieren?
Eine Prioritätswarteschlange wird am häufigsten mit einem Heap implementiert, weil er eine effiziente Entnahme des Elements mit höchster oder niedrigster Priorität ermöglicht.
Welche Struktur stellt das kleinste oder größte Element effizient an der Wurzel bereit?
Welche Menge listet die gängigen Tiefensuch-Traversierungsreihenfolgen für einen Binärbaum auf?
In-order, Pre-order und Post-order sind die drei üblichen Tiefensuch-Traversierungsreihenfolgen für Binärbäume, wobei jede eine andere Reihenfolge beim Besuch der Knoten hat. Die Breitensuche (Breadth‑first) ist ebenfalls verbreitet, gehört aber zu einer anderen Traversierungskategorie.
Überlege, wann bei einer Tiefensuche die Wurzel im Verhältnis zu ihren Teilbäumen besucht wird.
Welche der folgenden Eigenschaften gelten für einen Min-Heap?
In einem Min-Heap ist die Wurzel immer das kleinste Element, und die Höhe des Baumes ist O(log n), wodurch Einfügen und Entfernen effizient sind.
Ein binärer Min-Heap ist vollständig und hält das kleinste Element an der Wurzel.
Ist die übliche Variante von Bubble Sort stabil, die benachbarte Elemente nur dann vertauscht, wenn das linke strikt größer als das rechte ist?
Bubble Sort ist ein stabiler Sortieralgorithmus, da er die relative Reihenfolge gleicher Elemente beim Sortieren beibehält.
Werden zwei gleich große Elemente in der angegebenen Variante jemals vertauscht?