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).
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.
Wie ist die Zeitkomplexität für die Berechnung der Länge einer einfach verketteten Liste?
Um die Länge einer einfach verketteten Liste zu berechnen, muss man jeden Knoten von Kopf bis Schwanz durchlaufen, was zu einer Zeitkomplexität von O(n) führt.
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.
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.
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.
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.
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).
Welcher Algorithmus wird üblicherweise verwendet, um den kürzesten Pfad in einem gewichteten Graphen mit nicht‑negativen Kanten zu finden?
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.
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.
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).
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.
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.
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 Menge listet die gängigen Tiefen‑First‑Traversierungsreihenfolgen für einen Binärbaum auf?
In-order, Pre-order und Post-order sind die drei üblichen Tiefen‑First‑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.
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.
Ist der Bubble‑Sort‑Algorithmus stabil?
Bubble Sort ist ein stabiler Sortieralgorithmus, da er die relative Reihenfolge gleicher Elemente beim Sortieren beibehält.