Graphalgorithmen in der Informatik: Verstehen, Implementieren und Anwenden

Question 1

Bei welchem Verfahren der Graphentraversierung wird die Reihenfolge der besuchten Knoten durch einen Stapel (Stack) bestimmt?

Accepted Answer

Tiefensuche (DFS)

Answer

Breitensuche (BFS)

Answer

Bellman-Ford-Algorithmus

Answer

Floyd-Warshall-Algorithmus

Question 2

Welcher Algorithmus findet den kürzesten Pfad zwischen zwei Knoten in einem gewichteten Graphen?

Accepted Answer

Dijkstra-Algorithmus

Answer

Kruskal-Algorithmus

Answer

Prims-Algorithmus

Answer

Floyd-Warshall-Algorithmus

Question 3

Welche Datenstruktur eignet sich am besten für die Breitensuche (BFS)?

Accepted Answer

Warteschlange (Queue)

Answer

Stapel (Stack)

Answer

Liste (Array)

Answer

Baum (Tree)

Question 4

Welche Komplexitätsklasse hat die Tiefensuche (DFS)?

Accepted Answer

O(V + E)

Answer

O(V^2)

Answer

O(E log V)

Answer

O(V*log(V))

Question 5

Welches Verfahren sortiert die Knoten eines azyklischen Graphen nach ihren Abhängigkeiten?

Accepted Answer

Topologische Sortierung

Answer

Tiefensuche (DFS)

Answer

Breitensuche (BFS)

Answer

Kruskal-Algorithmus

Question 6

Bei welchem Graphentraversierungsalgorithmus werden gewichtete Kanten berücksichtigt?

Accepted Answer

Dijkstra-Algorithmus

Answer

Tiefensuche (DFS)

Answer

Breitensuche (BFS)

Answer

Topologische Sortierung

Question 7

Welcher Algorithmus findet alle möglichen Pfade zwischen zwei Knoten in einem Graphen?

Accepted Answer

Floyd-Warshall-Algorithmus

Answer

Kruskal-Algorithmus

Answer

Prims-Algorithmus

Answer

Topologische Sortierung

Question 8

Welcher Algorithmus ermittelt den kürzesten Pfad zwischen zwei Knoten in einem gerichteten, gewichteten Graphen?

Accepted Answer

Bellman-Ford-Algorithmus

Answer

Prim-Algorithmus

Answer

Tiefensuche

Answer

Floyd-Warshall-Algorithmus

Question 9

Welcher Algorithmus wendet die Regel "First In, First Out" an, um Knoten in einem Graphen zu besuchen?

Accepted Answer

Breitensuche

Answer

Bellman-Ford-Algorithmus

Answer

Tiefensuche

Answer

Prims-Algorithmus

Question 10

Welcher Algorithmus wird verwendet, um Zyklen in einem gerichteten Graphen zu identifizieren?

Accepted Answer

Tiefensuche

Answer

Dijkstra-Algorithmus

Answer

Breitensuche

Answer

Floyd-Warshall-Algorithmus

Question 11

Welche Aussage über gerichtete Graphen ist zutreffend?

Accepted Answer

Sie können Zyklen aufweisen.

Answer

Alle ihre Kanten sind gewichtet.

Answer

Sie können negative Gewichtungen enthalten.

Answer

Sie können sowohl gerichtete als auch ungerichtete Kanten enthalten.

Question 12

Welcher Algorithmus verwendet eine Prioritätswarteschlange, um den nächsten zu besuchenden Knoten zu bestimmen?

Accepted Answer

Dijkstra-Algorithmus

Answer

Tiefensuche

Answer

Breitensuche

Answer

Prims-Algorithmus

Question 13

Welche der folgenden ist keine Anwendung von Graphalgorithmen?

Accepted Answer

Datenkomprimierung

Answer

Navigationssysteme

Answer

Soziale Netzwerkanalyse

Answer

Maschinelles Lernen

Question 14

Welcher Algorithmus durchsucht einen Graphen schichtweise, indem er zuerst alle Knoten der ersten Ebene besucht, dann alle Knoten der zweiten Ebene usw.?

Accepted Answer

Breitensuche

Answer

Dijkstra

Answer

Bellman-Ford

Answer

Tiefensuche

Question 15

Welche Datenstruktur wird typischerweise zur Darstellung eines Graphen verwendet?

Accepted Answer

Adjazenzliste

Answer

Array

Answer

Liste

Answer

Baum

Question 16

Welcher Algorithmus kann verwendet werden, um Zyklen in einem ungerichteten Graphen zu erkennen?

Accepted Answer

Tiefensuche

Answer

Breitensuche

Answer

Dijkstra

Answer

Bellman-Ford

Question 17

Welche Anwendung eines Graphalgorithmus ist die Suche nach dem kürzesten Weg in einem Straßennetz?

Accepted Answer

Navigation

Answer

Suchmaschinen

Answer

Soziale Netzwerke

Answer

Datenbanken

Question 18

Welcher Graphalgorithmus durchläuft einen Graphen, indem er nacheinander allen Kanten folgt, die von einem Knoten ausgehen?

Accepted Answer

Tiefensuche

Answer

Breitensuche

Question 19

Welcher Algorithmus kann verwendet werden, um einen Zyklus in einem ungerichteten Graphen zu finden?

Accepted Answer

Tiefensuche

Answer

Breitensuche

Question 20

Wie lautet die Zeitkomplexität der Tiefensuche in einem Graphen mit V Knoten und E Kanten?

Accepted Answer

O(V+E)

Answer

O(V*E)

Question 21

Welcher Algorithmus wird verwendet, um den kürzesten Weg zwischen zwei Punkten in einem gewichteten, ungerichteten Graphen zu finden?

Accepted Answer

Dijkstra-Algorithmus

Answer

Tiefensuche

Answer

Breitensuche

Question 22

Welche Aussage beschreibt die Tiefensuche korrekt?

Accepted Answer

Sie findet alle Knoten im Graphen.

Answer

Sie sucht den kürzesten Pfad zwischen zwei Knoten.

Answer

Sie findet alle Zyklen im Graphen.

Question 23

Welche Datenstruktur wird in der Regel für die Breitensuche verwendet?

Accepted Answer

Queue

Answer

Stack

Answer

Liste

Question 24

Welche Methode kann verwendet werden, um einen Kreis in einem ungerichteten Graphen zu erkennen?

Accepted Answer

Tiefensuche

Answer

Breitensuche

Answer

Union-Find

Question 25

Welche Aussage über Gewichte von Graphenkanten ist korrekt?

Accepted Answer

Sie können negativ oder positiv sein.

Answer

Sie müssen ganzzahlig sein.

Answer

Sie können nur positive Werte annehmen.

Question 26

Welches Merkmal kennzeichnet einen gerichteten Graphen?

Accepted Answer

Jede Kante hat eine Richtung.

Answer

Jede Kante hat eine eindeutige ID.

Answer

Der Graph enthält keine Zyklen.

Answer

Der Graph hat mehr Kanten als Knoten.

Question 27

Welche der folgenden Aussagen beschreibt die Breitensuche am besten?

Accepted Answer

Die Breitensuche besucht alle Knoten im Graphen, beginnend mit denjenigen auf der obersten Ebene, und arbeitet sich dann schrittweise zu tieferen Ebenen vor.

Answer

Die Breitensuche durchsucht den Graphen in einer Tiefe-zuerst-Manier.

Answer

Die Breitensuche verwendet einen Stapel, um die zu besuchenden Knoten zu speichern.

Answer

Die Breitensuche findet den kürzesten Pfad zwischen zwei Knoten.

Question 28

Welcher Satz beschreibt den Dijkstra-Algorithmus am besten?

Accepted Answer

Der Dijkstra-Algorithmus ist ein gieriger Algorithmus, der bei jedem Schritt den nächsten Knoten auswählt.

Answer

Der Dijkstra-Algorithmus findet den kürzesten Pfad zwischen zwei Knoten in einem ungerichteten Graphen.

Answer

Die Laufzeitkomplexität des Dijkstra-Algorithmus beträgt O(n^2).

Answer

Der Dijkstra-Algorithmus kann negative Kantengewichte verarbeiten.

Question 29

Welcher Graphalgorithmus durchsucht einen Graphen, beginnt an einem Startknoten und durchläuft alle Knoten auf demselben Pfad, bevor er zum nächsten Pfad übergeht?

Accepted Answer

Tiefensuche

Answer

Breitensuche

Answer

Dijkstra-Algorithmus

Answer

Bellman-Ford-Algorithmus

Question 30

Welche Datenstruktur wird üblicherweise für die Implementierung der Tiefensuche verwendet?

Accepted Answer

Stapelspeicher

Answer

Warteschlange

Answer

Hashtabelle

Answer

Binärer Suchbaum

Question 31

Welche Methode des Dijkstra-Algorithmus wird verwendet, um den zu besuchenden Knoten mit der kürzesten Entfernung auszuwählen?

Accepted Answer

Prioritätswarteschlange

Answer

Breadth-First-Search

Answer

Depth-First-Search

Answer

Binäre Suche

Question 32

Nennen Sie den Vorteil des Bellman-Ford-Algorithmus gegenüber dem Dijkstra-Algorithmus.

Accepted Answer

Er kann negative Kantengewichte verarbeiten

Answer

Er findet immer den kürzesten Pfad

Answer

Er ist schneller als der Dijkstra-Algorithmus

Answer

Er ist einfacher zu implementieren

Question 33

Welcher der folgenden Graphen ist azyklisch?

Accepted Answer

Ein Baum

Answer

Ein Graph mit einer Schleife

Answer

Ein Graph mit einer Brücke

Answer

Ein vollständiger Graph

Question 34

Welcher Algorithmus durchsucht einen Graphen systematisch, indem er zuerst in die Tiefe geht?

Accepted Answer

Tiefensuche

Answer

Dijkstra-Algorithmus

Answer

Breitensuche

Answer

Kruskal-Algorithmus

Question 35

Welche Datenstruktur eignet sich am besten zur Speicherung von Knoten in einer Adjazenzliste?

Accepted Answer

Liste

Answer

Menge

Answer

Hash-Map

Answer

Baum

Question 36

Welche Eigenschaft des Dijkstra-Algorithmus macht ihn effizient?

Accepted Answer

Er ist ein gieriger Algorithmus

Answer

Er hat eine lineare Zeitkomplexität

Answer

Er kann nur in gerichteten Graphen verwendet werden

Answer

Er ist unabhängig von der Kantengewichtung

Question 37

Welche Methode eignet sich zur Erkennung von Zyklen in einem Graphen?

Accepted Answer

Tiefenfirstsuche

Answer

Breitenfirstsuche

Answer

Kruskal-Algorithmus

Answer

Dijkstra-Algorithmus

Question 38

Welche Eigenschaft ist für Spannbäume charakteristisch?

Accepted Answer

Sie sind azyklisch

Answer

Sie enthalten alle Kanten im Graphen

Answer

Sie haben das gleiche Gewicht wie der ursprüngliche Graph

Answer

Sie verbinden nicht alle Knoten im Graphen

Question 39

Was ist der Zweck des Kruskal-Algorithmus?

Accepted Answer

Einen minimalen Spannbaum in einem gewichteten Graphen finden

Answer

Den kürzesten Pfad zwischen zwei Knoten finden

Answer

Einen Eulerkreis in einem Graphen finden

Answer

Die Konnektivität eines Graphen bestimmen

Question 40

Welcher Algorithmus verwendet eine Warteschlange (Queue) zur Speicherung der zu besuchenden Knoten?

Accepted Answer

Breitensuche

Answer

Tiefensuche

Answer

Dijkstra-Algorithmus

Answer

Prims-Algorithmus

Question 41

Welche Komplexitätsklasse hat der Algorithmus zur Suche des kürzesten Pfades mit Hilfe von Dijkstra?

Accepted Answer

O(n log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(2^n)

Question 42

Welche Datenstruktur eignet sich am besten, um die Menge der besuchten Knoten in einem Graphalgorithmus abzubilden?

Accepted Answer

Menge

Answer

Array

Answer

Liste

Answer

Baum

Question 43

Welcher Algorithmus wird verwendet, um zu überprüfen, ob ein Graph einen Kreis enthält?

Accepted Answer

Tarjan-Algorithmus

Answer

Tiefensuche

Answer

Breitensuche

Answer

Dijkstra-Algorithmus

Question 44

Welche Datenstruktur wird in der Regel verwendet, um die besuchten Knoten in der Breitensuche zu speichern und zu gewährleisten, dass alle Knoten in der richtigen Reihenfolge besucht werden?

Accepted Answer

Queue

Answer

Stapel

Answer

Liste

Answer

Hashtabelle

Question 45

Welcher Algorithmus findet den kürzesten Pfad zwischen zwei Knoten in einem gewichteten, gerichteten Graphen?

Accepted Answer

Dijkstras Algorithmus

Answer

Kruskals Algorithmus

Answer

Prims Algorithmus

Answer

Bellman-Ford-Algorithmus

Question 46

Welche Komplexitätsklasse hat der Floyd-Warshall-Algorithmus, der alle kürzesten Pfade in einem Graphen berechnet?

Accepted Answer

O(V^3)

Answer

O(V)

Answer

O(V^2)

Answer

O(V^4)

Question 47

Welcher Graphalgorithmus durchquert alle Knoten in einem ungerichteten Graphen, indem er ausgehend von einem Knoten rekursiv die angrenzenden Knoten besucht?

Accepted Answer

Tiefensuche

Answer

Dijkstra-Algorithmus

Answer

Breitensuche

Answer

Prim-Algorithmus

Question 48

Welche Aussage beschreibt den Prim-Algorithmus korrekt?

Accepted Answer

Er findet den Spannbaum mit dem minimalen Gewicht in einem ungerichteten Graphen.

Answer

Er findet den kürzesten Weg zwischen zwei Knoten in einem gerichteten Graphen.

Answer

Er findet die kürzeste Schleife in einem Graphen.

Answer

Er sortiert die Knoten in einem Graphen nach ihren Graden.

Question 49

Welcher Datentyp repräsentiert eine Menge von Knoten, die in einem Graphen besucht wurden?

Accepted Answer

Menge

Answer

Liste

Answer

Array

Answer

Queue

Question 50

Welche Komplexität hat die Tiefensuche?

Accepted Answer

O(V + E)

Answer

O(V^2)

Answer

O(E^2)

Answer

O(V)

Question 51

Welche Datenstruktur eignet sich am besten zur Darstellung eines Graphen, der aus Knoten und Kanten besteht?

Accepted Answer

Adjazenzliste

Answer

Liste

Answer

Tabelle

Answer

Hashtabelle

Question 52

In welchen Anwendungsfällen kann Breitensuche eingesetzt werden?

Accepted Answer

Ermittlung verbundener Komponenten in einem Graphen

Answer

Topologische Sortierung von Aufgaben

Answer

Bestimmung des längsten Weges zwischen zwei Knoten

Answer

Erkennung von Zyklen in einem Graphen

Question 53

Welche Komplexitätsklasse hat der Prim-Algorithmus, der einen minimalen Spannbaum in einem Graphen findet?

Accepted Answer

O(V log V)

Answer

O(V^2)

Answer

O(E log V)

Answer

O(E)

Question 54

Welche Technik kann verwendet werden, um Zyklen in einem Graphen zu identifizieren?

Accepted Answer

Tiefensuche mit Zykluserkennung

Answer

Breitensuche mit Zykluserkennung

Answer

Kantenentspannung

Answer

Topologische Sortierung

Question 55

Welche Datenstruktur wird zur Implementierung der Prioritätswarteschlange im Dijkstra-Algorithmus verwendet?

Accepted Answer

Binärer Heap

Answer

Liste

Answer

Hashtabelle

Answer

Stapel

Question 56

Welche Eigenschaft eines Graphen kann mithilfe der Breitensuche festgestellt werden?

Accepted Answer

Konnektivität

Answer

Gewichtung

Answer

Zyklusfreiheit

Answer

Planarität

Question 57

Welche Datenstruktur wird **bei der Breitensuche** zur Verwaltung der zu besuchenden Knoten verwendet?

Accepted Answer

Warteschlange

Answer

Array

Answer

Stapel

Answer

Liste

Question 58

Welches Kriterium wird beim **Dijkstra-Algorithmus** verwendet, um den nächsten zu besuchenden Knoten auszuwählen?

Accepted Answer

Geringstes Gewicht

Answer

Zufällige Auswahl

Answer

Größte Tiefe

Answer

Höchster Grad

Question 59

Was ist der wesentliche **Unterschied zwischen einem gerichteten und einem ungerichteten Graphen**?

Accepted Answer

Kanten in gerichteten Graphen haben eine Richtung, in ungerichteten nicht.

Answer

Gerichtete Graphen enthalten Knoten, während ungerichtete keine Knoten enthalten.

Answer

Ungerichtete Graphen haben keine Zyklen, während gerichtete Graphen Zyklen haben können.

Question 60

**Welche Art von Graph** ist ein ungerichteter, zusammenhängender Graph ohne Zyklen?

Accepted Answer

Baum

Answer

Wald

Answer

Vollständiger Graph

Question 61

Welcher Graphalgorithmus untersucht einen Graphen ausgehend von einem Startknoten rekursiv in die Tiefe?

Accepted Answer

Tiefensuche

Answer

Topologische Sortierung

Answer

Suche nach dem kürzesten Pfad

Answer

Breitensuche

Question 62

Welcher Graphalgorithmus untersucht einen Graphen ausgehend von einem Startknoten iterativ in die Breite?

Accepted Answer

Breitensuche

Answer

Tiefensuche

Answer

Suche nach dem minimalen Spannbaum

Answer

Suche nach dem kürzesten Pfad

Question 63

Welche Algorithmenklasse findet die kürzesten Pfade zwischen allen Knotenpaaren in einem Graphen?

Accepted Answer

All-Pairs-Shortest-Path-Algorithmen

Answer

Topologische Sortierungsalgorithmen

Answer

Suchalgorithmen

Answer

Minimalspannbaumalgorithmen

Question 64

Welcher Graphalgorithmus findet den minimalen Spannbaum in einem ungerichteten, gewichteten Graphen?

Accepted Answer

Minimalspannbaumalgorithmus

Answer

Suchalgorithmen

Answer

Suche nach dem kürzesten Pfad

Answer

Topologische Sortierung