Graphen: Grundlagen und Algorithmen für nicht-lineare Datenstrukturen

Question 1

Welches Strukturmerkmal ist charakteristisch für Graphen?

Accepted Answer

Nichtlineare Anordnung von Elementen

Answer

Lineare Anordnung von Elementen

Answer

Baumartige Struktur

Answer

Sequentieller Zugriff auf Elemente

Question 2

Welche Datenstruktur wird verwendet, um die besuchten Knoten während einer Breitensuche zu speichern?

Accepted Answer

Queue

Answer

Stack

Answer

Hashtabelle

Answer

Liste

Question 3

Welche Komplexitätsklasse beschreibt die Laufzeit eines Algorithmus, der einen ungerichteten Graphen auf Zyklen untersucht?

Accepted Answer

NP-vollständig

Answer

NP

Answer

P

Answer

LogSpace

Question 4

Welche Anwendung verwendet Graphen zur Modellierung sozialer Netzwerke?

Accepted Answer

Soziale Netzwerkanalyse

Answer

Bildverarbeitung

Answer

Suchmaschinenoptimierung

Answer

Netzwerkrouting

Question 5

Welche Operation wird verwendet, um einen Knoten aus einem Graphen zu entfernen?

Accepted Answer

RemoveNode()

Answer

AddNode()

Answer

GetNode()

Answer

UpdateNode()

Question 6

Welches Kriterium wird verwendet, um den kürzesten Pfad in einem gewichteten Graphen zu finden?

Accepted Answer

Gesamtgewichtung

Answer

Anzahl der Knoten

Answer

Durchschnittliche Gewichtung

Answer

Maximale Gewichtung

Question 7

Welche Aussage über eine Baumstruktur ist korrekt?

Accepted Answer

Ein Baum ist ein zusammenhängender azyklischer Graph

Answer

Ein Baum hat immer eine ungerade Anzahl von Knoten

Answer

Alle Knoten in einem Baum haben den gleichen Grad

Answer

Ein Baum hat kein Wurzel-Blatt-Pfad

Question 8

Welcher Algorithmus untersucht einen Graphen ausgehend von einem Startknoten rekursiv und besucht jeden Knoten genau einmal?

Accepted Answer

Tiefensuche

Answer

Breitensuche

Answer

Dijkstra-Algorithmus

Answer

Kruskal-Algorithmus

Question 9

Welche Datenstruktur repräsentiert die Kanten eines Graphen typischerweise?

Accepted Answer

Liste

Answer

Tabelle

Answer

Menge

Answer

Baum

Question 10

Welche Aussage über gerichtete Graphen trifft zu?

Accepted Answer

Graphen können Zyklen enthalten.

Answer

Kanten besitzen keine Richtung.

Answer

Knoten können mehrere Elternknoten haben.

Answer

Graphen sind immer zusammenhängend.

Question 11

Was ist die Aufgabe eines topologischen Sortierungsalgorithmus?

Accepted Answer

Er ordnet einen Graphen in eine lineare Folge von Knoten an.

Answer

Er erkennt Zyklen in einem Graphen.

Answer

Er findet den kürzesten Pfad in einem Graphen.

Answer

Er berechnet den maximalen Fluss in einem Netzwerk.

Question 12

Was versteht man unter einem stark zusammenhängenden Graphen?

Accepted Answer

Ein Graph, in dem jeder Knoten über einen Pfad von jedem anderen Knoten erreichbar ist.

Answer

Ein Graph, in dem jeder Knoten mit jedem anderen Knoten verbunden ist.

Answer

Ein Graph, der keine Zyklen enthält.

Answer

Ein Graph, in dem jede Kante eine Richtung hat.

Question 13

Welche Aussage beschreibt Prims Algorithmus zur Berechnung minimaler Spannbäume korrekt?

Accepted Answer

Prim wählt bei jedem Schritt die Kante mit dem kleinsten Gewicht, die den aktuellen Baum mit einem neuen Knoten verbindet.

Answer

Prim wählt bei jedem Schritt die Kante mit dem größten Gewicht, die den aktuellen Baum mit einem neuen Knoten verbindet.

Answer

Prim wählt bei jedem Schritt zufällig eine Kante aus, die den aktuellen Baum mit einem neuen Knoten verbindet.

Answer

Prim läuft in O(n²) Zeit, unabhängig von der Anzahl der Kanten im Graphen.

Question 14

Welche Bedingung muss ein zusammenhängender Graph erfüllen, damit er einen Eulerkreis enthält?

Accepted Answer

Jeder Knoten hat einen geraden Grad.

Answer

Es gibt mindestens einen Knoten mit ungeradem Grad.

Answer

Der Graph ist gerichtet.

Answer

Der Graph ist gewichtet.

Question 15

Welche Speicherstruktur ist bei der Tiefensuche in einem ungerichteten Graphen zu bevorzugen und weshalb?

Accepted Answer

Stapel

Answer

Warteschlange

Question 16

(Deutsch) Welcher der folgenden Algorithmen gehört zu den Tiefensuchalgorithmen?

Accepted Answer

Depth-First Search (DFS)

Answer

Breadth-First Search (BFS)

Answer

Dijkstra-Algorithmus

Answer

Kruskal-Algorithmus

Question 17

Welcher Algorithmus erkennt Zyklen in ungerichteten Graphen?

Accepted Answer

Tarjan-Algorithmus

Answer

Kosaraju-Algorithmus

Answer

Prim-Algorithmus

Answer

Kruskal-Algorithmus

Question 18

Welche Eigenschaft trifft auf einen zusammenhängenden Graphen zu?

Accepted Answer

Jeder Knoten ist über einen Pfad mit jedem anderen Knoten verbunden.

Answer

Der Graph kann in mehrere Teilgraphen zerlegt werden.

Answer

Der Graph ist immer planar.

Answer

Der Graph ist immer azyklisch.

Question 19

Welche Aussage über Graphen ist korrekt?

Accepted Answer

Ein Graph kann sowohl gerichtete als auch ungerichtete Kanten enthalten.

Answer

Ein Graph kann nur gerichtete Kanten enthalten.

Answer

Ein Graph kann nur ungerichtete Kanten enthalten.

Answer

Ein Graph besteht immer aus Knoten und Kanten.

Question 20

Welcher Algorithmus berechnet den kürzesten Weg zwischen zwei Knoten in einem gewichteten Graphen?

Accepted Answer

Dijkstras Algorithmus

Answer

Prims Algorithmus

Answer

Kruskals Algorithmus

Answer

Bellman-Ford-Algorithmus

Question 21

Welche Laufzeitkomplexität hat die Tiefensuche für einen Graphen mit n Knoten und m Kanten?

Accepted Answer

O(n + m)

Answer

O(n)

Answer

O(m)

Answer

O(n log n)

Question 22

Welche Methode verwendet die Tiefensuche, um alle Knoten in einem Graphen zu besuchen?

Accepted Answer

Stapel

Answer

Warteschlange

Answer

Rekursion

Answer

Prioritätswarteschlange

Question 23

Welche Methode verwendet die Breitensuche, um alle Knoten in einem Graphen zu besuchen?

Accepted Answer

Warteschlange

Answer

Stapel

Answer

Rekursion

Answer

Prioritätswarteschlange

Question 24

Welche Aussage beschreibt den Unterschied zwischen gerichteten und ungerichteten Graphen?

Accepted Answer

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

Answer

In einem ungerichteten Graphen können Kanten mehrfach vorkommen, in einem gerichteten Graphen nicht.

Answer

In einem gerichteten Graphen können Knoten Gewichte haben, in einem ungerichteten Graphen nicht.

Answer

Es gibt keine Unterschiede zwischen gerichteten und ungerichteten Graphen.

Question 25

Welche der folgenden Definitionen beschreibt einen Graphen korrekt?

Accepted Answer

Ein Graph besteht aus einer Menge von Knoten, die durch Kanten miteinander verbunden sind.

Answer

Ein Graph ist eine lineare Sequenz von Elementen.

Question 26

Welche Datenstruktur kann als Graph implementiert werden?

Accepted Answer

Adjazenzliste

Answer

Hashtabelle

Answer

Fila

Answer

Binärer Suchbaum

Question 27

Welcher Algorithmus wird verwendet, um den kürzesten Weg zwischen zwei Knoten in einem gewichteten Graphen zu ermitteln?

Accepted Answer

Dijkstra-Algorithmus

Answer

Tiefensuche

Answer

Kruskal-Algorithmus

Answer

Breitensuche

Question 28

Welche Aussage über Breitensuche ist korrekt?

Accepted Answer

Breitensuche durchläuft alle Knoten auf einer Ebene, bevor sie zur nächsten Ebene übergeht.

Answer

Breitensuche kann verwendet werden, um Zyklen in einem Graphen zu erkennen.

Answer

Breitensuche ist eine effiziente Methode, um den kürzesten Weg zwischen zwei Knoten zu finden.

Question 29

Welcher Datenstrukturtyp ähnelt einem Graphen am meisten?

Accepted Answer

Baum

Answer

Stapel

Answer

Array

Answer

Hashtabelle

Question 30

Welche Datenstruktur wird am häufigsten zur Darstellung von Graphen in einem Computerprogramm verwendet?

Accepted Answer

Adjazenzliste

Answer

Knotenliste

Answer

Kantenliste

Answer

Inzidenzmatrix

Question 31

Welcher der folgenden Algorithmen wird verwendet, um zu überprüfen, ob ein Graph zusammenhängend ist?

Accepted Answer

Tiefensuche oder Breitensuche

Answer

Prims-Algorithmus

Answer

Kruskal-Algorithmus

Answer

Dijkstra-Algorithmus

Question 32

Was ist das Ziel des minimalen Spannbaums?

Accepted Answer

Alle Knoten eines gewichteten Graphen mit minimalen Gesamtgewichten zu verbinden.

Answer

Den kürzesten Weg zwischen zwei Knoten zu finden.

Answer

Zu überprüfen, ob ein Graph zusammenhängend ist.

Question 33

Welcher der folgenden Graphen ist nicht planar?

Accepted Answer

Vollständiger Graph K5

Answer

Baumgraph T4

Answer

Kreisgraph C5

Answer

Vollständiger Graph K4

Question 34

Welches der folgenden Probleme gehört zur Komplexitätsklasse NP-vollständig?

Accepted Answer

Hamiltonkreisproblem

Answer

Dijkstra-Algorithmus

Answer

Breitensuche

Answer

Tiefensuche

Question 35

Nenne eine Anwendung von Graphen im Bereich der Künstlichen Intelligenz.

Accepted Answer

Modellierung von Wissensrepräsentationen und Inferenzsystemen.

Answer

Erkennung von Mustern in großen Datenmengen.

Answer

Planung von Routen für Fahrzeuge.

Answer

Suche nach dem kürzesten Weg zwischen Städten.

Question 36

Welche der folgenden Aussagen beschreibt die Definition eines Graphen korrekt?

Accepted Answer

Eine nicht-lineare Datenstruktur, die aus einer Menge von Knoten und Kanten besteht, die diese verbinden.

Answer

Eine lineare Datenstruktur, die aus einer geordneten Folge von Elementen besteht, auf die nacheinander zugegriffen werden kann.

Answer

Eine hierarchische Datenstruktur, die aus einem einzigen Wurzelknoten besteht, von dem sich sukzessive Unterknoten abzweigen.

Question 37

Welche der folgenden Datenstrukturen kann zur Implementierung eines Graphen verwendet werden?

Accepted Answer

Adjazenzliste

Answer

AVL-Baum (für effizientes Einfügen und Löschen)

Answer

Binomial Heap (für effiziente Vereinigungsoperationen)

Answer

Hashtabelle (für schnelles Suchen)

Question 38

Welcher der folgenden Begriffe beschreibt die Anzahl der Kanten, die an einen Knoten in einem Graphen angrenzen?

Accepted Answer

Grad

Answer

Zyklus (geschlossen, keine Eingangsknoten)

Answer

Gewicht (für gewichtete Graphen)

Answer

Pfad (eine Folge von Kanten, die Knoten verbinden)

Question 39

Welche der folgenden Eigenschaften zeichnet einen gerichteten Graphen aus?

Accepted Answer

Kanten haben eine bestimmte Richtung, d. h. sie verbinden Knoten in einer festgelegten Reihenfolge.

Answer

Alle Knoten haben den gleichen Grad (gleiche Anzahl eingehender und ausgehender Kanten).

Answer

Der Graph ist azyklisch (enthält keine Zyklen).

Answer

Der Graph ist zusammenhängend (alle Knoten sind durch Pfade verbunden).

Question 40

Welche der folgenden Aussagen beschreibt einen azyklischen Graphen (DAG)?

Accepted Answer

Ein DAG enthält keine Zyklen (geschlossene Pfade).

Answer

Ein DAG kann sowohl gerichtete als auch ungerichtete Kanten haben.

Answer

Ein DAG ist immer zusammenhängend (alle Knoten sind durch Pfade verbunden).

Answer

Ein DAG hat nur einen einzigen Knoten.

Question 41

Welcher der folgenden Graphentypen eignet sich am besten zur Modellierung hierarchischer Beziehungen, wie z. B. einer Organisationsstruktur?

Accepted Answer

Baum

Answer

Zweigeteilter Graph (in dem zwei Mengen von Knoten nur durch eine Kante verbunden sind)

Answer

Netzwerkflussgraph (für die Modellierung von Flüssen in Netzwerken)

Answer

Vollständiger Graph (in dem jeder Knoten mit jedem anderen Knoten verbunden ist)

Question 42

Welcher der folgenden Graphen ist ein ungerichteter Graph?

Accepted Answer

Graph G = (V, E) mit V = {1, 2, 3} und E = {(1, 2), (2, 3), (1, 3)}

Answer

Graph G = (V, E) mit V = {1, 2, 3} und E = {(1, 2), (2, 3), (1, 4)}

Answer

Graph G = (V, E) mit V = {1, 2, 3} und E = {(1, 2), (2, 3)}

Question 43

Welche der folgenden Aussagen über Tiefensuche ist richtig?

Accepted Answer

Tiefensuche besucht einen Knoten rekursiv, bevor er dessen Nachbarknoten besucht.

Answer

Tiefensuche ist ein nicht-deterministischer Algorithmus.

Answer

Tiefensuche besucht alle Nachbarknoten eines Knotens, bevor er den Knoten besucht.

Question 44

Welcher der folgenden Algorithmen findet minimale Spannbäume?

Accepted Answer

Kruskal-Algorithmus

Answer

Dijkstra-Algorithmus

Answer

Bellman-Ford-Algorithmus

Answer

Floyd-Warshall-Algorithmus

Question 45

Welche der folgenden Datenstrukturen wird zur Implementierung von Graphen verwendet?

Accepted Answer

Adjazenzliste

Answer

Stapel

Answer

Hashtabelle

Answer

Binärbaum

Question 46

Was ist der Grad eines Knotens in einem Graphen?

Accepted Answer

Anzahl der Kanten, die mit dem Knoten verbunden sind

Answer

Anzahl der Pfade, die vom Knoten ausgehen

Answer

Entfernung des Knotens zum nächsten Knoten

Question 47

Welche der folgenden Aussagen über planare Graphen ist richtig?

Accepted Answer

Jeder planare Graph kann auf einer Ebene ohne Überschneidungen gezeichnet werden.

Answer

Planare Graphen haben immer einen geraden Zyklus.

Answer

Planare Graphen können nicht mehr als drei Farben zur Färbung benötigen.

Question 48

Welcher der folgenden Algorithmen findet den maximalen Fluss in einem Flussnetzwerk?

Accepted Answer

Ford-Fulkerson-Algorithmus

Answer

Bellman-Ford-Algorithmus

Answer

Dijkstra-Algorithmus

Answer

Kruskal-Algorithmus

Question 49

Welche der folgenden Aussagen über Hamilton-Pfade ist richtig?

Accepted Answer

Ein Hamilton-Pfad besucht jeden Knoten in einem Graphen genau einmal.

Answer

Ein Hamilton-Pfad ist ein Spezialfall eines Euler-Kreises.

Answer

Ein Hamilton-Pfad existiert immer in jedem zusammenhängenden Graphen.

Question 50

Welche der folgenden Eigenschaften trifft NICHT auf einen Graphen zu?

Accepted Answer

Er muss zyklisch sein

Answer

Seine Knoten können Gewichtungen haben

Answer

Er kann unterschiedliche Datentypen als Knoten speichern

Answer

Er besteht aus Knoten und Kanten

Question 51

Welche Datenstruktur eignet sich am besten, um einen Graphen in einem Programm darzustellen?

Accepted Answer

Adjazenzliste

Answer

Hash-Tabelle

Answer

Binärer Baum

Answer

Warteschlange

Question 52

Welcher Algorithmus wird verwendet, um einen minimalen Spannbaum in einem gewichteten Graphen zu finden?

Accepted Answer

Kruskal-Algorithmus

Answer

Tiefensuche

Answer

Dijkstra-Algorithmus

Answer

Breitensuche

Question 53

Was ist ein Nachteil der Darstellung von Graphen mit Adjazenzlisten?

Accepted Answer

Sie können viel Speicherplatz belegen

Answer

Sie sind schwer zu aktualisieren

Answer

Sie sind langsam beim Zugriff auf Knoten

Answer

Sie unterstützen keine gewichteten Kanten

Question 54

Was ist eine zusammenhängende Komponente in einem Graphen?

Accepted Answer

Eine Menge von Knoten, die alle miteinander verbunden sind

Answer

Eine Menge von Knoten, die nur durch eine einzige Kante verbunden sind

Answer

Eine Menge von Knoten, die keinen Zyklus bilden

Question 55

Was ist der Hauptunterschied zwischen einem gerichteten und einem ungerichteten Graphen?

Accepted Answer

In einem gerichteten Graphen haben die Kanten eine Richtung, während sie in einem ungerichteten Graphen keine Richtung haben.

Answer

Gerichtete Graphen können Zyklen enthalten, ungerichtete Graphen nicht

Question 56

Welcher der folgenden Graphentypen ist gekennzeichnet durch Kanten, die eine Richtung haben?

Accepted Answer

Digraph

Answer

Ungraph

Answer

Hypergraph

Answer

Multigraph

Question 57

Welcher Algorithmus wird eingesetzt, um in einem gewichteten Graphen den kürzesten Pfad zwischen zwei gegebenen Knoten zu finden?

Accepted Answer

Dijkstra-Algorithmus

Answer

Kruskal-Algorithmus

Answer

Breitensuche

Answer

Tiefensuche

Question 58

Was beschreibt den Grad eines Knotens in einem Graphen?

Accepted Answer

Die Anzahl der mit dem Knoten verbundenen Kanten

Answer

Die Entfernung des Knotens zum nächstgelegenen Knoten

Answer

Die Anzahl der Pfade, die an dem Knoten beginnen

Question 59

Welcher der folgenden Algorithmen berechnet einen minimalen Spannbaum in einem ungerichteten, zusammenhängenden Graphen?

Accepted Answer

Prims Algorithmus

Answer

Floyd-Warshall-Algorithmus

Answer

Edmonds-Karp-Algorithmus

Answer

Bellman-Ford-Algorithmus

Question 60

Welche Laufzeitkomplexität hat die Tiefensuche in einem azyklischen Graphen?

Accepted Answer

O(V)

Answer

O(E^2)

Answer

O(E)

Answer

O(V^2)

Question 61

Welche Datenstruktur eignet sich zur Repräsentation eines Graphen?

Accepted Answer

Adjazenzliste

Answer

Warteschlange

Answer

Binärer Suchbaum

Answer

Hashtabelle

Question 62

Was unterscheidet einen gewichteten Graphen von einem ungerichteten Graphen?

Accepted Answer

Ein gewichteter Graph weist seinen Kanten Gewichte zu, während ein ungerichteter Graph dies nicht tut.

Answer

Ein ungerichteter Graph hat nur zwei Knoten, während ein gewichteter Graph mehrere Knoten haben kann.

Answer

Ein gewichteter Graph hat zyklische Kanten, während ein ungerichteter Graph keine zyklischen Kanten hat.

Question 63

Welche der folgenden Graphenarten ist planar?

Accepted Answer

Baum

Answer

Sternförmiger Graph

Answer

Zyklusgraph

Answer

Vollständiger Graph

Question 64

Wie lautet die Definition eines Baumes im Kontext der Graphentheorie?

Accepted Answer

Ein zusammenhängender Graph ohne Zyklen

Answer

Ein Graph mit einem Knoten mit dem höchsten Grad

Answer

Ein Graph, in dem alle Knoten besucht werden können