Nichtlineare Datenstrukturen: Online-Quiz für Klasse 12 Informatik

Question 1

In welcher Datenstruktur wird ein vollständiger Binärbaum typischerweise implementiert?

Accepted Answer

Array

Answer

Liste

Answer

Queue

Answer

Hashtabelle

Question 2

Welcher Algorithmus nutzt einen Heap als Prioritätswarteschlange?

Accepted Answer

Dijkstra-Algorithmus

Answer

Bubblesort-Algorithmus

Answer

Quicksort-Algorithmus

Answer

Insertionsort-Algorithmus

Question 3

Welcher Suchalgorithmus zeichnet sich durch eine Zeitkomplexität von O(n^2) aus?

Accepted Answer

Lineare Suche

Answer

Binäre Suche

Answer

Interpolationssuche

Answer

Ternäre Suche

Question 4

Was ist der Grad eines Knotens in einem Graphen?

Accepted Answer

Die Anzahl der Kanten, die mit dem Knoten verbunden sind

Answer

Die Länge des längsten Weges vom Knoten zum Wurzelknoten

Answer

Die Anzahl der Kinder des Knotens

Answer

Die Anzahl der Eltern des Knotens

Question 5

Welche Datenstruktur verwendet einen Schlüssel-Wert-Speicher?

Accepted Answer

Hashtabelle

Answer

Array

Answer

Liste

Answer

Binärbaum

Question 6

Was ist der Algorithmus von Dijkstra?

Accepted Answer

Ein Algorithmus zur Suche des kürzesten Weges in einem gewichteten Graphen

Answer

Ein Algorithmus zur Sortierung eines Arrays

Answer

Ein Algorithmus zur Suche des kleinsten gemeinsamen Vielfachen

Answer

Ein Algorithmus zur Erstellung eines Spanning Trees

Question 7

Welche der folgenden Operationen hat eine Zeitkomplexität von O(log n)?

Accepted Answer

Hinzufügen eines Elements zu einem binären Suchbaum

Answer

Suchen eines Elements in einer sortierten Liste

Answer

Erstellen eines Arrays aus einer Liste

Answer

Umkehren einer Liste

Question 8

Welche Datenstruktur wird zur Darstellung von Hierarchien verwendet?

Accepted Answer

Baum

Answer

Liste

Answer

Array

Answer

Hashtabelle

Question 9

Was ist die gewichtete Summe eines Pfades in einem Graphen?

Accepted Answer

Die Summe der Gewichte der Kanten auf dem Pfad

Answer

Die Länge des Pfades in Knoten

Answer

Die Anzahl der Kanten auf dem Pfad

Answer

Die Summe der Knotenwerte auf dem Pfad

Question 10

Welche Datenstruktur verwendet das Prinzip "Last-in-first-out" (LIFO)?

Accepted Answer

Stapel

Answer

Warteschlange

Answer

Baum

Answer

Hashtabelle

Question 11

Welche Laufzeitkomplexität weist der Algorithmus zur Topologischen Sortierung eines azyklischen gerichteten Graphen auf?

Accepted Answer

O(V+E)

Answer

O(V)

Answer

O(E log V)

Answer

O(V^2)

Question 12

Welche der folgenden Anwendungen verwendet keine nichtlineare Datenstruktur vom Typ Baum?

Accepted Answer

Hashtabellen

Answer

Dateisysteme

Answer

XML-Dokumente

Answer

Dijkstra-Algorithmus

Question 13

Welches Datenstrukturmodell eignet sich für die Darstellung von Hierarchien?

Accepted Answer

Baum

Answer

Graph

Answer

Liste

Answer

Tabelle

Question 14

Welche Graphendarstellung ist für ungerichtete Graphen geeignet?

Accepted Answer

Adjazenzliste

Answer

Adjazenzmatrix

Answer

Inzidenzmatrix

Answer

Knotenliste

Question 15

Welcher Algorithmus wird für die Breitensuche in einem Graphen verwendet?

Accepted Answer

BFS-Algorithmus

Answer

Dijkstra-Algorithmus

Answer

Kruskal-Algorithmus

Answer

Prims-Algorithmus

Question 16

Welche Datenstruktur wird verwendet, um die Reihenfolge der Knoten bei der Tiefensuche in einem Graphen zu speichern?

Accepted Answer

Stapel

Answer

Warteschlange

Answer

Menge

Answer

Liste

Question 17

Welches Merkmal ist für Spannbäume charakteristisch?

Accepted Answer

Sie enthalten keine Zyklen.

Answer

Sie verbinden alle Knoten im Graphen.

Answer

Sie minimieren das Gesamtgewicht der Kanten.

Answer

Sie maximieren die Anzahl der inneren Knoten.

Question 18

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

BFS-Algorithmus

Question 19

Welche Aussage über Binärbäume ist korrekt?

Accepted Answer

Die Höhe eines vollständigen Binärbaums mit n Knoten beträgt log2(n+1).

Answer

Jeder Knoten kann maximal drei Nachfolger haben.

Answer

Die Anzahl der Blätter ist stets größer als die Anzahl der inneren Knoten.

Answer

Ein Baum mit n Knoten besitzt immer n-1 Kanten.

Question 20

Welcher Traversal-Algorithmus besucht die Knoten eines Baumes in der Reihenfolge: Wurzel, linker Teilbaum, rechter Teilbaum?

Accepted Answer

Preorder

Answer

Inorder

Answer

Postorder

Answer

Breadth-first

Question 21

Was bedeutet ein gerichteter Graph?

Accepted Answer

Die Kanten des Graphen haben eine Richtung.

Answer

Der Graph besteht ausschließlich aus Zyklen.

Answer

Der Graph enthält keine isolierten Knoten.

Answer

Der Graph besitzt eine eindeutige Wurzel.

Question 22

Welche Datenstruktur wird üblicherweise zur Implementierung einer Warteschlange verwendet?

Accepted Answer

Liste

Answer

Kette

Answer

Baum

Answer

Hash-Tabelle

Question 23

Was ist der Zweck einer Prioritätswarteschlange?

Accepted Answer

Elemente nach ihrer Priorität zu speichern.

Answer

Elemente in einer bestimmten Reihenfolge zu speichern.

Answer

Elemente schnell zu suchen und zu löschen.

Answer

Elemente effizient zu aktualisieren.

Question 24

Welche Datenstruktur wird üblicherweise verwendet, um die Kanten eines Graphen zu repräsentieren?

Accepted Answer

Liste

Answer

Feld

Answer

Hash-Tabelle

Answer

Binärbaum

Question 25

Welche der folgenden Aussagen über Binärbäume trifft zu?

Accepted Answer

Jeder Knoten hat höchstens zwei Kinder.

Answer

Jeder Knoten hat maximal ein Kind.

Answer

Jeder Knoten hat mindestens ein Kind.

Answer

Jeder Knoten hat genau zwei Kinder.

Question 26

Welche Datenstruktur folgt dem Prinzip "First-in, First-out" (FIFO)?

Accepted Answer

Warteschlange

Answer

Baum

Answer

Graph

Answer

Array

Question 27

Welcher Algorithmus kann verwendet werden, um die kürzeste Verbindung zwischen zwei Knoten in einem gewichteten Graphen zu finden?

Accepted Answer

Dijkstra-Algorithmus

Answer

Breadth-First-Search

Answer

Depth-First-Search

Answer

Kruskal-Algorithmus

Question 28

Welche Aussage zu Bäumen ist falsch?

Accepted Answer

Bäume können Zyklen enthalten.

Answer

Bäume sind hierarchische Datenstrukturen.

Answer

Binäre Bäume haben höchstens zwei Kindknoten.

Answer

Jeder Knoten in einem Baum hat maximal einen Elternknoten.

Question 29

Welche Datenstruktur eignet sich am besten für die Repräsentation hierarchischer Daten?

Accepted Answer

Baum

Answer

Liste

Answer

Stapel

Answer

Warteschlange

Question 30

Welche Operation ist für einen AVL-Baum zulässig?

Accepted Answer

Linksrotation

Answer

Infix-Einfügung

Answer

Radix-Sortierung

Answer

Lineare Suche

Question 31

Nenne eine Anwendung, die Graphen nutzt.

Accepted Answer

Soziales Netzwerk

Answer

Sortierung

Answer

Binäre Suche

Question 32

Welche Datenstruktur wird verwendet, um die Verbindungen zwischen Knoten in einem Graphen zu verwalten?

Accepted Answer

Adjazenzliste

Answer

Menge

Answer

Warteschlange

Answer

Stapel

Question 33

Was beschreibt den Grad eines Knotens in einem Graphen?

Accepted Answer

Anzahl der mit dem Knoten verbundenen Kanten

Answer

Anzahl der Ebenen im Baum.

Answer

Höhe des Baumes.

Question 34

Welche Aussage beschreibt korrekt die Struktur eines Baumes in der Informatik?

Accepted Answer

Eine hierarchische Datenstruktur, bei der jeder Knoten maximal einen Elternknoten, aber mehrere Kindknoten haben kann.

Answer

Eine lineare Datenstruktur, in der die Elemente in einer bestimmten Reihenfolge angeordnet sind.

Answer

Eine kollisionsfreie Hashtabelle, die zur effizienten Speicherung und Suche von Daten verwendet wird.

Question 35

Welche Datenstruktur eignet sich am besten für die Implementierung einer Warteschlange (First-in-First-Out)?

Accepted Answer

Linearisierte Liste

Answer

Baum

Answer

Hashtabelle

Answer

Menge

Question 36

Was ist das wesentliche Unterscheidungsmerkmal zwischen gerichteten und ungerichteten Graphen?

Accepted Answer

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

Answer

Gerichtete Graphen können Zyklen enthalten, während ungerichtete Graphen keine Zyklen enthalten können.

Question 37

Was ist ein wesentlicher Vorteil der Verwendung von Hashtabellen im Vergleich zu Arrays?

Accepted Answer

Schnellere Suche und Einfügeoperationen

Answer

Geringerer Speicherbedarf

Answer

Ordnungserhaltende Eigenschaften

Answer

Keine Notwendigkeit zum Sortieren

Question 38

Wie werden Graphen typischerweise in Adjazenzlisten dargestellt?

Accepted Answer

Jeder Knoten wird durch eine Liste seiner benachbarten Knoten repräsentiert.

Answer

Die Größe der Liste entspricht der Anzahl der Kanten im Graphen.

Answer

Die Kanten werden explizit in der Liste gespeichert.

Question 39

Welche der folgenden Datenstrukturen gehört zu den nichtlinearen Datenstrukturen?

Accepted Answer

Baum

Answer

Array

Answer

Hashtabelle

Answer

Tupel

Question 40

Wie viele Kindknoten kann ein vollständiger Binärbaum mit n Knoten maximal haben?

Accepted Answer

2^(n-1)

Answer

log(n)

Answer

n^2

Answer

n-1

Question 41

Welcher Algorithmus eignet sich zur Bestimmung des kürzesten Pfades zwischen zwei Knoten in einem Graphen?

Accepted Answer

Dijkstra-Algorithmus

Answer

Binary-Search

Answer

Quicksort

Answer

Breadth-First-Search

Question 42

Welche der folgenden Operationen kann nicht an einem AVL-Baum durchgeführt werden?

Accepted Answer

Rotation um einen Knoten mit Grad 1

Answer

Einfügen eines Elements

Answer

Löschen eines Elements

Answer

Suche eines Elements

Question 43

Was beschreibt der Grad eines Knotens in einem Graphen?

Accepted Answer

Anzahl der an den Knoten angrenzenden Kanten

Answer

Entfernung des Knotens zum Graphenursprung

Answer

Anzahl der Ebenen, auf denen der Knoten im Graphen liegt

Question 44

Nenne den entscheidenden Unterschied zwischen einem Graphen und einem Baum.

Accepted Answer

Bäume sind azyklisch, während Graphen Zyklen enthalten können

Answer

Graphen weisen stets mehr Knoten auf als Bäume

Answer

Bäume besitzen eine hierarchische Struktur, Graphen hingegen nicht

Question 45

Wie heißt das rekursive Verfahren zur Pfadsuche in Bäumen oder Graphen?

Accepted Answer

Depth-First-Search

Answer

Greedy-Algorithmus

Answer

Breadth-First-Search

Answer

Binary-Search

Question 46

Welche Aussage beschreibt die Eigenschaft eines Binärbaums korrekt?

Accepted Answer

Jeder Knoten hat höchstens zwei Kindknoten.

Answer

Die Blätter des Baumes befinden sich immer auf derselben Ebene.

Answer

Jeder Knoten hat mindestens einen Kindknoten.

Answer

Die Höhe des Baumes ist immer größer als die Anzahl der Knoten.

Question 47

Welcher Graphentyp ist gerichtet und gewichtet?

Accepted Answer

Digraph

Answer

Simplex-Graph

Answer

Multigraph

Answer

Hypergraph

Question 48

Welche Datenstruktur wird oft verwendet, um eine Warteschlange in einem Computersystem zu implementieren?

Accepted Answer

Verkettete Liste

Answer

Hashtabelle

Answer

Heap

Answer

Binärer Baum

Question 49

Wie funktioniert eine Tiefensuche in einem Graphen?

Accepted Answer

Sie besucht Knoten, indem sie einem Pfad folgt, bis ein Endpunkt erreicht ist.

Answer

Sie besucht alle Knoten auf einer Ebene, bevor sie zur nächsten Ebene übergeht.

Answer

Sie wählt Knoten zufällig aus und besucht sie.

Question 50

Welche Datenstruktur wird typischerweise zur Implementierung eines Stapels in einem Computersystem verwendet?

Accepted Answer

Stack

Answer

Tree

Answer

Graph

Answer

Queue

Question 51

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

Accepted Answer

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

Answer

In einem gerichteten Graphen sind die Knoten immer gewichtet, während in einem ungerichteten Graphen die Knoten nicht gewichtet sind.

Question 52

Welche Eigenschaft beschreibt am besten Bäume als nichtlineare Datenstruktur?

Accepted Answer

Bäume haben eine hierarchische Struktur, wobei jeder Knoten höchstens einen Elternknoten besitzt.

Answer

Bäume sind linear angeordnet und ermöglichen den Zugriff auf Elemente nur sequenziell.

Answer

Bäume sind dynamisch und können jederzeit beliebig viele Elemente einfügen oder entfernen.

Question 53

Wie fügt man einen Knoten effizient in einen binären Suchbaum ein?

Accepted Answer

Rekursive Einfügeoperation

Answer

Breitensuche (Breadth-first Search)

Answer

Tiefensuche (Depth-first Search)

Question 54

Was unterscheidet einen gerichteten Graphen von einem ungerichteten Graphen?

Accepted Answer

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

Answer

Gerichtete Graphen haben eine begrenzte Anzahl von Knoten, während ungerichtete Graphen beliebig viele Knoten haben können.

Question 55

Wie funktioniert die rekursive Berechnung der Fakultätsfunktion?

Accepted Answer

Die Fakultätsfunktion wird für n>0 rekursiv definiert als n multipliziert mit der Fakultät von n-1. Die Fakultät von 0 ist 1.

Answer

Die Fakultätsfunktion wird iterativ berechnet, indem n-mal mit sich selbst multipliziert wird.

Question 56

Welche Datenstruktur ermöglicht es, dass jedes Element genau einen Vorgänger und beliebig viele Nachfolger besitzt?

Accepted Answer

Baum

Answer

Liste

Answer

Hashtabelle

Answer

Array

Question 57

Welche Aussage zu Graphen ist richtig?

Accepted Answer

Graphen können sowohl gerichtete als auch ungerichtete Verbindungen enthalten.

Answer

Graphen sind immer zyklisch.

Answer

Graphen haben immer einen eindeutigen Startknoten.

Question 58

Welche Baum-Implementierung ist am besten geeignet, um ein Element schnell zu finden?

Accepted Answer

Binärer Suchbaum

Answer

Heap

Answer

Array

Answer

Verkettete Liste

Question 59

Welcher Algorithmus ermittelt die kürzeste Distanz zwischen zwei Knoten in einem Graphen mit gewichteten Verbindungen?

Accepted Answer

Dijkstra-Algorithmus

Answer

Tiefensuche (Depth-First-Search)

Answer

Breitensuche (Breadth-First-Search)

Question 60

In welcher Anwendung werden nichtlineare Datenstrukturen häufig eingesetzt?

Accepted Answer

Soziale Netzwerke

Answer

Betriebssysteme

Answer

Compiler

Answer

Datenbanken

Question 61

Welche nichtlineare Datenstruktur stellt eine hierarchische Ordnung von Elementen dar?

Accepted Answer

Baum

Answer

Hashtabelle

Answer

Array

Answer

Liste

Question 62

Wie nennt man einen Baum, bei dem jeder Knoten höchstens zwei Nachfolger hat?

Accepted Answer

Binärer Baum

Answer

Unärer Baum

Answer

Tertiärer Baum

Answer

Multi-Way-Baum

Question 63

Welcher Algorithmus findet einen Pfad zwischen zwei Knoten in einem Graphen?

Accepted Answer

Breitensuche (Breadth-First-Search)

Answer

A*-Algorithmus

Answer

Dijkstra-Algorithmus

Answer

Tiefensuche (Depth-First-Search)

Question 64

Welche Datenstruktur ist geeignet, um Daten in einer hierarchischen Struktur zu speichern?

Accepted Answer

Baum

Answer

Array

Answer

Hashtabelle

Answer

Liste