Bei der Erstellung der Unterlagen wurden KI Assistenten (insbesondere Claude aber ggf. auch ChatGPT, Ollama mit Gemma/LLama/Qwen oder OpenCode mit Kimi/Qwen/Deepseek...) unterstützend eingesetzt. Dies erfolgte insbesondere zur Unterstützung bei der Generierung von Grafiken (d. h. SVG Dateien), oder um sich Übersichtstabellen generieren zu lassen. Weiterhin wurde KI zur allgemeinen Qualitätssicherung eingesetzt. Inhalte, die ggf. von der KI vorgeschlagen wurden, wurden im Falle der Übernahme explizit validiert und angepasst.
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?