Graphen: Interaktive Lernquizzes für Algorithmen und Datenstrukturen

Question 1

Welche Datenstruktur eignet sich am besten zur Darstellung eines Graphen, bei dem jeder Knoten über eine eindeutige ID verfügt und die Kanten als Paare von Knoten-IDs gespeichert werden?

Accepted Answer

Adjazenzliste

Answer

Adjazenzmatrix

Answer

Inzidenzmatrix

Answer

Einfache Liste

Question 2

Welcher Algorithmus findet den kürzesten Weg zwischen zwei Knoten in einem gerichteten Graphen mit **negativen** Kantengewichten?

Accepted Answer

Bellman-Ford-Algorithmus

Answer

Dijkstra-Algorithmus

Answer

Prims-Algorithmus

Answer

Krushkal-Algorithmus

Question 3

Was ist die Laufzeit des Algorithmus zum Auffinden des tiefsten Knotens in einem binären **Such**baum?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(1)

Answer

O(n^2)

Question 4

Welche Eigenschaft muss ein Graph erfüllen, um einen Eulerkreis zu besitzen?

Accepted Answer

Der Graph ist zusammenhängend und jeder Knoten hat einen geraden Grad

Answer

Jeder Knoten hat einen geraden Grad

Answer

Jeder Knoten hat einen ungeraden Grad

Answer

Der Graph ist azyklisch

Question 5

Welcher Algorithmus wird verwendet, um einen topologischen Sortierungsalgorithmus für einen gerichteten **azyklischen** Graphen zu finden?

Accepted Answer

Tiefen-Suche

Answer

Breiten-Suche

Answer

Dijkstras Algorithmus

Answer

Bellman-Ford-Algorithmus

Question 6

Was ist die maximale Anzahl von Kanten in einem vollständigen Graphen mit n Knoten?

Accepted Answer

n(n-1)/2

Answer

n

Answer

n-1

Answer

n^2

Question 7

Welche Art von Graph wird durch eine Menge von Knoten und Kanten ohne Schleifen oder Mehrfachkanten beschrieben?

Accepted Answer

Einfacher Graph

Answer

Gerichteter Graph

Question 8

Welches Datenelement wird in einer Adjazenzliste zur Darstellung einer Kante zwischen zwei Knoten verwendet?

Accepted Answer

Tupel

Answer

Liste

Question 9

Wie wird ein Graph genannt, dessen Kanten alle eine Richtung haben?

Accepted Answer

Gerichteter Graph

Answer

Ungerichteter Graph

Question 10

Welche Eigenschaft muss ein Graph erfüllen, um als planar zu gelten?

Accepted Answer

Kann ohne Kreuzungen in die Ebene gezeichnet werden

Answer

Hat maximal drei Knoten

Question 11

Wie wird der Grad eines Knotens in einem Graphen definiert?

Accepted Answer

Anzahl der Kanten, die mit dem Knoten verbunden sind

Answer

Anzahl der Knoten, die mit dem Knoten verbunden sind

Question 12

Welcher Algorithmus wird verwendet, um alle kürzesten Pfade zwischen allen Knotenpaaren in einem gewichteten, gerichteten Graphen zu finden?

Accepted Answer

Floyd-Warshall-Algorithmus

Answer

Bellman-Ford-Algorithmus

Question 13

Welcher Algorithmus findet alle zusammenhängenden Komponenten in einem ungerichteten Graphen?

Accepted Answer

Algorithmus von Tarjan

Answer

Dijkstra-Algorithmus

Answer

Algorithmus von Kruskal

Answer

Algorithmus von Bellman-Ford

Question 14

Wer gilt als Begründer der Graphentheorie und veröffentlichte 1736 eine wegweisende Arbeit zu diesem Thema?

Accepted Answer

Leonhard Euler

Answer

Carl Friedrich Gauß

Answer

Pierre de Fermat

Answer

René Descartes

Question 15

Welche Datenstruktur eignet sich am besten zur Darstellung eines Graphen?

Accepted Answer

Adjazenzliste

Answer

Liste

Answer

Array

Answer

Hashtabelle

Question 16

Welche Operation ermöglicht es, in einem Graphen alle mit einem bestimmten Knoten verbundenen Knoten zu finden?

Accepted Answer

Nachbarn finden

Answer

Knoten hinzufügen

Answer

Kante entfernen

Answer

Graph durchlaufen

Question 17

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

Accepted Answer

Dijkstras Algorithmus

Answer

Bellman-Ford-Algorithmus

Answer

Kruskals Algorithmus

Answer

Prims Algorithmus

Question 18

Welche Komplexität hat Kruskals Algorithmus?

Accepted Answer

O(E log V)

Answer

O(E)

Answer

O(V log V)

Answer

O(V^2)

Question 19

Welches Datenfeld wird in einem Knoten eines Graphen verwendet, um zusätzliche Informationen zu speichern?

Accepted Answer

Wert

Answer

ID

Answer

Farbe

Answer

Abstand

Question 20

Welcher Datentyp eignet sich am besten, um Graphen abzubilden, bei denen jeder Knoten mit vielen anderen verknüpft sein kann?

Accepted Answer

Adjazenzliste

Answer

Verkettete Liste

Answer

Array

Answer

Hash-Tabelle

Question 21

Welche der folgenden Operationen kann für einen Graphen mit |V| Knoten in O(|V|) ausgeführt werden?

Accepted Answer

Tiefen- oder Breitensuche

Answer

Kürzester Pfad

Answer

Topologische Sortierung

Question 22

Welcher Algorithmus findet einen minimalen Spannbaum in einem gewichteten Graphen?

Accepted Answer

Prims oder Kruskals Algorithmus

Answer

Dijkstras Algorithmus

Answer

Bellman-Ford-Algorithmus

Answer

Floyds-Warshall-Algorithmus

Question 23

Welche Aussage über gerichtete Graphen ist korrekt?

Accepted Answer

Sie können Zyklen enthalten.

Answer

Sie sind immer zusammenhängend.

Answer

Sie haben immer einen eindeutigen Zyklus.

Answer

Sie haben keine parallelen Kanten.

Question 24

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

Accepted Answer

Dijkstras Algorithmus

Answer

Floyds-Warshall-Algorithmus

Answer

Prims Algorithmus

Answer

Kruskals Algorithmus

Question 25

Welche Aussage über zusammenhängende Komponenten ist richtig?

Accepted Answer

Jeder Knoten gehört zu genau einer zusammenhängenden Komponente.

Answer

Zusammenhängende Komponenten überlappen sich immer.

Answer

Ein Graph mit |V| Knoten hat immer |V| zusammenhängende Komponenten.

Question 26

Welcher Algorithmus findet eine topologische Sortierungsreihenfolge für einen azyklischen gerichteten Graphen?

Accepted Answer

Kahns Algorithmus

Answer

Bellman-Ford-Algorithmus

Answer

Fulkerson-Algorithmus

Answer

Tarjans Algorithmus

Question 27

Welche Datenstrukturen können verwendet werden, um einen Graphen darzustellen?

Accepted Answer

Adjazenzliste oder Adjazenzmatrix

Answer

AVL-Baum

Answer

Hashtabelle

Answer

Heap

Question 28

Welcher Algorithmus findet die kürzeste Distanz zwischen zwei Knoten in einem gewichteten Graphen?

Accepted Answer

Dijkstra- oder Bellman-Ford-Algorithmus

Answer

Floyd-Warshall-Algorithmus

Answer

Kruskals Algorithmus

Answer

Prims-Algorithmus

Question 29

Welche Eigenschaft eines Graphen gibt die Anzahl der möglichen Pfade zwischen zwei Knoten an?

Accepted Answer

Konnektivität

Answer

Zyklenfreiheit

Answer

Gerichtetheit

Answer

Gewichtung

Question 30

Welche Komplexitätsklasse beschreibt die Laufzeit des Algorithmus, der einen minimalen Spannbaum in einem Graphen findet?

Accepted Answer

Polynomial

Answer

NP-vollständig

Answer

NP-schwer

Answer

Lineare Zeit

Question 31

Welches der folgenden Probleme ist ein NP-vollständiges Problem im Zusammenhang mit Graphen?

Accepted Answer

Hamilton-Kreis-Problem

Answer

Dijkstra-Algorithmus

Answer

Breitensuche

Answer

Minimaler Spannbaum

Question 32

Welche Algorithmen können verwendet werden, um zu bestimmen, ob ein Graph einen Zyklus enthält?

Accepted Answer

Tiefen- oder Breitensuche

Answer

Bellman-Ford-Algorithmus

Answer

Floyd-Warshall-Algorithmus

Answer

Dijkstra-Algorithmus

Question 33

Was ist der Hauptunterschied zwischen einem azyklischen und einem zyklischen Graphen?

Accepted Answer

Azyklische Graphen enthalten keine Zyklen, während zyklische Graphen mindestens einen Zyklus enthalten

Answer

Azyklische Graphen sind immer vollständig, während zyklische Graphen nicht vollständig sind

Question 34

Welche Datenstruktur wird verwendet, um die Adjazenzen eines Knotens in einem Adjazenzlistengraphen zu speichern?

Accepted Answer

Verknüpfte Liste oder Array

Answer

Warteschlange

Answer

Hashtabelle

Answer

Baum

Question 35

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

Accepted Answer

Prims-Algorithmus oder Kruskal-Algorithmus

Answer

Dijkstras-Algorithmus

Answer

Floyd-Warshall-Algorithmus

Answer

Bellman-Ford-Algorithmus

Question 36

Nenne zwei gebräuchliche Datenstrukturen, die zur Darstellung eines Graphen verwendet werden.

Accepted Answer

Adjazenzliste, Adjazenzmatrix

Answer

Binärer Suchbaum

Answer

Hash-Tabelle

Answer

B-Baum

Question 37

Welche ist die asymptotische Laufzeitkomplexität des Prim-Algorithmus?

Accepted Answer

O(|E| log |V|)

Answer

O(|V|^3)

Answer

O(|V|^2)

Question 38

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

Accepted Answer

Stack

Answer

Menge

Answer

Queue

Answer

Liste

Question 39

Wie viele Kanten hat ein vollständiger Graph mit n Knoten?

Accepted Answer

n * (n-1) / 2

Answer

n * (n+1) / 2

Answer

n

Answer

n^2

Question 40

Welche Datenstruktur wird üblicherweise zur Darstellung eines Graphen verwendet?

Accepted Answer

Adjazenzliste

Answer

Verlinkte Liste

Answer

Hash-Tabelle

Answer

Binärer Suchbaum

Question 41

Welcher Algorithmus wird verwendet, um die kürzeste Strecke zwischen zwei Knoten in einem gewichteten Graphen zu finden?

Accepted Answer

Dijkstra-Algorithmus

Answer

Prims-Algorithmus

Answer

Bellman-Ford-Algorithmus

Answer

Kruskal-Algorithmus

Question 42

Welche Komplexitätsklasse hat der Algorithmus zur Suche eines Eulerkreises in einem Graphen?

Accepted Answer

NP-vollständig

Answer

NP-schwer

Answer

P

Answer

NP

Question 43

Was versteht man unter einem Hamiltonkreis?

Accepted Answer

Ein Zyklus, der alle Knoten eines Graphen genau einmal besucht

Answer

Ein Baum, der alle Knoten eines Graphen verbindet

Answer

Ein Pfad, der alle Knoten eines Graphen genau einmal besucht

Question 44

Welcher Algorithmus wird verwendet, um den maximalen Fluss in einem Flussnetzwerk zu berechnen?

Accepted Answer

Ford-Fulkerson-Algorithmus

Answer

Dijkstra-Algorithmus

Answer

Kruskal-Algorithmus

Answer

Prims-Algorithmus

Question 45

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

Accepted Answer

Bei ungerichteten Graphen haben Kanten keine Richtung, während sie bei gerichteten Graphen eine bestimmte Richtung haben

Answer

Ungerichtete Graphen haben nur eine Komponente, während gerichtete Graphen mehrere Komponenten haben können

Question 46

Welche Art von Suche findet alle Pfade von einem Knoten zu allen anderen Knoten in einem Graphen?

Accepted Answer

Breitensuche

Answer

Tiefensuche

Answer

Lineare Suche

Answer

Binäre Suche

Question 47

Welche Datenstruktur eignet sich zur Darstellung eines Graphen?

Accepted Answer

Adjazenzliste

Answer

Baum

Answer

Hashtabelle

Answer

Array

Question 48

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

Accepted Answer

Dijkstra-Algorithmus

Answer

Kruskal-Algorithmus

Answer

Prims-Algorithmus

Answer

Bellman-Ford-Algorithmus

Question 49

Welche Eigenschaft zeichnet einen gerichteten azyklischen Graphen (DAG) aus?

Accepted Answer

Keine Zyklen

Answer

Negativ gewichtete Kanten

Answer

Gewichtete Kanten

Answer

Alle Knoten sind verbunden

Question 50

Welche Komplexität hat der Dijkstra-Algorithmus für einen Graphen mit V Knoten und E Kanten?

Accepted Answer

O((V + E) * log V)

Answer

O(E^2)

Answer

O(V^2)

Answer

O(V * E)

Question 51

Welche Datenstruktur wird zur Verfolgung besuchter Knoten bei einer Tiefensuche (DFS) verwendet?

Accepted Answer

Stack

Answer

Warteschlange

Answer

Hashtabelle

Answer

Adjazenzliste

Question 52

In welchem Bereich der Informatik werden gerichtete azyklische Graphen (DAGs) eingesetzt?

Accepted Answer

Abhängigkeitsmodellierung

Answer

Verschlüsselung

Answer

Datenkompression

Answer

Suchmaschinen

Question 53

Welche Eigenschaft kennzeichnet einen vollständigen Graphen?

Accepted Answer

Jeder Knoten ist mit jedem anderen Knoten verbunden

Answer

Gewichtete Kanten

Answer

Negativ gewichtete Kanten

Answer

Keine Zyklen

Question 54

Welcher Algorithmus wird verwendet, um die Existenz eines Hamilton-Kreises in einem Graphen zu bestimmen?

Accepted Answer

Es existiert kein garantierter polynomialer Algorithmus

Answer

Dijkstra-Algorithmus

Answer

Kruskal-Algorithmus

Question 55

Welche Datenstruktur wird typischerweise verwendet, um einen Graphen darzustellen?

Accepted Answer

Adjazenzliste

Answer

Array

Answer

Queue

Question 56

Welche Aussage über azyklische Graphen ist korrekt?

Accepted Answer

Sie können topologisch sortiert werden

Answer

Sie sind nicht zusammenhängend

Answer

Sie haben mindestens einen Zyklus

Answer

Sie haben mindestens eine Euler-Tour

Question 57

Was repräsentieren die Kanten in einem Graphen?

Accepted Answer

Beziehungen zwischen Knoten

Answer

Knotenbeschriftungen

Answer

Gewichte

Answer

Knoten

Question 58

Welcher der folgenden Graphen ist nicht planar?

Accepted Answer

Vollständiger Graph K₅

Answer

Kreisgraph

Answer

Baum

Answer

Stern

Question 59

Wie viele Kanten hat ein vollständiger Graph mit n Knoten?

Accepted Answer

n * (n - 1) / 2

Answer

n * (n - 1)

Answer

n * n

Answer

n * (n + 1) / 2

Question 60

Welcher Algorithmus kann verwendet werden, um zu überprüfen, ob ein Graph zusammenhängend ist?

Accepted Answer

Tiefensuche oder Breitensuche

Answer

Dijkstra-Algorithmus

Question 61

Welche Aussage zu gewichteten Graphen ist wahr?

Accepted Answer

Sie können negative Kantengewichte haben

Answer

Sie können keine negativen Kantengewichte haben

Answer

Sie können nur ganzzahlige Kantengewichte haben

Answer

Sie können nur positive Kantengewichte haben