Woraus besteht ein gerichteter Graph?
Was unterscheidet einen ungerichteten von einem gerichteten Graphen?
Was ist ein gewichteter Graph?
Was ist ein markierter Graph und welche Rolle spielen Markierungen?
Wie viele Kanten kann es maximal zwischen zwei verschiedenen Knoten in einem gerichteten Graphen geben? Kann ein Knoten eine Kante zu sich selbst haben?
Was ist ein Pfad in einem Graphen und wie wird seine Länge definiert?
Welche zwei grundlegenden Datenstrukturen können zur Implementierung von Graphen verwendet werden?
Beschreiben Sie die Struktur einer Adjazenzliste.
Nennen Sie je zwei Vor- und Nachteile der Adjazenzliste gegenüber der Adjazenzmatrix.
Wie ist eine Adjazenzmatrix aufgebaut und was bedeuten ihre Einträge?
Wann ist die Adjazenzmatrix besonders ineffizient und warum?
Was ist der Unterschied zwischen einem aktiven und einem passiven Knoten bei der Graphensuche?
Welche Datenstruktur wird bei der Breite-zuerst-Suche zur Verwaltung der aktiven Knoten verwendet und warum?
Welche Datenstruktur wird bei der Tiefe-zuerst-Suche zur Verwaltung der aktiven Knoten verwendet und warum?
Welche besondere Eigenschaft hat der Erreichbarkeitsbaum, der durch die Breite-zuerst-Suche erzeugt wird?
Beschreiben Sie den grundlegenden Ablauf einer Graphensuche (unabhängig von BFS oder DFS).
Wie unterscheidet sich der Schritt bzgl. der Kantenwahl bei der Tiefe-zuerst-Suche von der Breite-zuerst-Suche?
Erklären Sie die folgenden Begriffe im Zusammenhang mit Bäumen: Wurzel, Blattknoten, innerer Knoten, Elternknoten, Kindknoten.
Was ist der Unterschied zwischen der Höhe eines Baumes und der Tiefe eines Knotens?
Was ist ein binärer Suchbaum und welche Eigenschaft muss er erfüllen?
In welcher Reihenfolge werden die Knoten bei einer Präorder-, Inorder- und Postorder-Traversierung besucht?
Welche besondere Eigenschaft hat die Inorder-Traversierung eines binären Suchbaums?
Gegeben sei ein binärer Suchbaum mit den Werten 2, 1, 7, 4, 8, 3, 6, 5 (eingefügt in dieser Reihenfolge). Geben Sie die Reihenfolge der Knoten bei einer Postorder-Traversierung an.
Welche Laufzeit hat die Suche in einem binären Suchbaum und wovon hängt sie ab?
Warum sollten häufig benötigte Schlüssel zuerst in einen binären Suchbaum eingefügt werden?
Was ist eine Prioritätswarteschlange und welche Standardoperationen bietet sie?
Was ist ein Heap und welche Eigenschaft muss er erfüllen?
Inwiefern ist eine Prioritätswarteschlange eine Verallgemeinerung von Stacks und Queues? Welchen Typ von Heap verwendet man ggf. zur Implementierung eines Stacks/eine Queue?
Wie wird ein Heap effizient in einem Array gespeichert? Geben Sie die Indexformeln für Eltern und Kinder an (Wurzel bei Index 0).
Beschreiben Sie den Ablauf beim Einfügen eines neuen Elements in einen Min-Heap.
Beschreiben Sie den Ablauf beim Entfernen des kleinsten Elements aus einem Min-Heap.
Welche Laufzeiten haben die Standardoperationen auf einem Heap?
Gegeben sei ein Min-Heap als Array: [1, 3, 2, 5, 4, 8, 6]. Zeichnen Sie den zugehörigen Binärbaum. Was passiert, wenn das Minimum entfernt wird?