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?
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 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 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.
