Nicht-lineare Datenstrukturen: Quizfragen und Übungen für Klasse 10 Informatik

Question 1

Was ist die Komplexität des Suchalgorithmus in einem binären Suchbaum?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(1)

Question 2

Welche der folgenden Datenstrukturen wird verwendet, um eine Warteschlange zu implementieren?

Accepted Answer

Verkettete Liste

Answer

Stapel

Answer

Baum

Answer

Graph

Question 3

Welche Eigenschaft müssen die Schlüssel in einem Rot-Schwarz-Baum erfüllen?

Accepted Answer

Sie müssen eindeutig sein.

Answer

Sie müssen in aufsteigender Reihenfolge sortiert sein.

Answer

Sie müssen die B-Baum-Bedingung erfüllen.

Answer

Sie müssen die AVL-Bedingung erfüllen.

Question 4

Welcher der folgenden Algorithmen kann verwendet werden, um einen Graphen auf Zyklen zu untersuchen?

Accepted Answer

Tarjan-Algorithmus

Answer

Dijkstra-Algorithmus

Answer

Flood-Fill-Algorithmus

Answer

Kruskal-Algorithmus

Question 5

Welches Verfahren durchsucht einen Graphen systematisch in die Breite, sodass alle Knoten einer Ebene besucht werden, bevor die nächste Ebene durchsucht wird?

Accepted Answer

Breadth-First-Search

Answer

Depth-First-Search

Answer

Dijkstra-Algorithmus

Answer

Kruskal-Algorithmus

Question 6

Welches Merkmal gehört nicht zu den wesentlichen Eigenschaften von Bäumen?

Accepted Answer

Es können Zyklen auftreten

Answer

Daten werden in Knoten gespeichert

Answer

Knoten sind durch Kanten verbunden

Answer

Es gibt einen Wurzelknoten

Question 7

Welcher Datentyp eignet sich am besten für die Implementierung eines Graphen?

Accepted Answer

Adjazenzliste

Answer

Array

Answer

Tabelle

Answer

Hashtabelle

Question 8

Was zeichnet einen gerichteten Graphen aus?

Accepted Answer

Kanten haben eine Richtung

Answer

Kanten haben keine Richtung

Answer

Besteht nur aus Knoten

Answer

Besteht nur aus Kanten

Question 9

Welcher Graphentyp ist für die Modellierung sozialer Netzwerke geeignet?

Accepted Answer

Gerichteter Graph

Answer

Ungewerteter Graph

Answer

Gewichteter Graph

Answer

Vollständiger Graph

Question 10

Was ist eine topologische Sortierung?

Accepted Answer

Sortierung von Knoten, um Zyklen zu vermeiden

Answer

Sortierung von Knoten nach aufsteigendem Grad

Answer

Sortierung von Knoten nach Entfernung zur Quelle

Answer

Sortierung von Knoten nach Wert

Question 11

Welche der folgenden Aussagen trifft auf Bäume zu?

Accepted Answer

Jeder Knoten hat maximal einen Elternknoten.

Answer

Sie können Zyklen enthalten.

Answer

Sie sind gerichtete Graphen.

Answer

Ihre Höhe ist immer kleiner als die Anzahl der Knoten.

Question 12

Welcher Begriff beschreibt einen Knoten in einem Graphen, der keine ausgehenden Kanten hat?

Accepted Answer

Blattknoten

Answer

Wurzelknoten

Answer

Tiefe

Answer

Verzweigungsgrad

Question 13

Was erledigt der Algorithmus von Dijkstra?

Accepted Answer

Suche des kürzesten Weges in einem gewichteten Graphen

Answer

Suche des maximalen Flusses in einem Netzwerk

Answer

Topologische Sortierung eines gerichteten azyklischen Graphen

Answer

Berechnung der minimalen Spannweite eines Graphen

Question 14

Welche der folgenden Datenstrukturen zählt zu den nicht-linearen Datenstrukturen?

Accepted Answer

Baum

Answer

Array

Answer

Liste

Answer

Tabelle

Question 15

Welche Operation ist auf einem Graphen nicht möglich?

Accepted Answer

Lineare Suche

Answer

Hinzufügen von Knoten

Answer

Hinzufügen von Kanten

Answer

Topologische Sortierung

Question 16

Was bedeutet eine gerichtete Kante in einem Graphen?

Accepted Answer

Eine Kante mit einer bestimmten Richtung

Answer

Eine Kante, die auf sich selbst zeigt

Answer

Eine Kante mit einer Länge größer als 1

Answer

Eine Kante, die zu einem Zyklus gehört

Question 17

Welche Datenstruktur ist eine besondere Form eines Baumes?

Accepted Answer

Binärsuchbaum

Answer

Hashtabelle

Answer

Adjazenzliste

Answer

Hashset

Question 18

Welcher der folgenden Graphen ist ein gerichteter Graph, bei dem jeder Knoten nur eine ausgehende Kante besitzt?

Accepted Answer

Baum

Answer

Kreisgraph

Answer

Vollständiger Graph

Answer

Zusammenhängender Graph

Question 19

Welche Implementierung einer nicht-linearen Datenstruktur eignet sich am besten für die Modellierung hierarchischer Daten?

Accepted Answer

Baum

Answer

Liste

Answer

Tabelle

Answer

Hashtabelle

Question 20

Welcher der folgenden Algorithmen wird verwendet, um die kürzeste Verbindung zwischen zwei Knoten in einem bewerteten Graphen zu finden?

Accepted Answer

Dijkstra-Algorithmus

Answer

Breitensuche

Answer

Tiefensuche

Answer

Prims Algorithmus

Question 21

Welche der folgenden Eigenschaften ist für einen vollständigen Graphen charakteristisch?

Accepted Answer

Jeder Knoten ist mit allen anderen Knoten verbunden.

Answer

Der Graph hat keine Schleifen.

Answer

Der Graph ist planar.

Answer

Der Graph ist azyklisch.

Question 22

Welches der folgenden Durchlaufverfahren ist für die Suche nach einem Element in einem sortierten Binärbaum am effizientesten?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Tiefensuche

Answer

Breitensuche

Question 23

Was ist eine Inorder-Traversierung eines Baumes?

Accepted Answer

Besuche den linken Teilbaum, dann den Wurzelknoten und schließlich den rechten Teilbaum.

Answer

Besuche den linken Teilbaum, dann den rechten Teilbaum und schließlich den Wurzelknoten.

Answer

Besuche den Wurzelknoten, dann den linken Teilbaum und schließlich den rechten Teilbaum.

Answer

Besuche den rechten Teilbaum, dann den linken Teilbaum und schließlich den Wurzelknoten.

Question 24

Welche Datenstruktur ist hierarchisch aufgebaut und ermöglicht ein effizientes Einfügen und Entfernen von Elementen?

Accepted Answer

Baum

Answer

Liste

Answer

Menge

Answer

Graph

Question 25

Welche Eigenschaft trifft auf einen Graphen zu?

Accepted Answer

Kann Zyklen enthalten

Answer

Kann keine parallelen Kanten enthalten

Answer

Ist immer vollständig verbunden

Answer

Speichert nur eindeutige Elemente

Question 26

Was unterscheidet einen AVL-Baum von einem normalen binären Suchbaum?

Accepted Answer

Ein AVL-Baum ist immer höhenbalanciert.

Answer

Ein normaler binärer Suchbaum ist immer höhenbalanciert.

Answer

Ein AVL-Baum kann keine doppelten Elemente enthalten.

Answer

Es gibt keinen Unterschied zwischen diesen beiden Datenstrukturen.

Question 27

Welche Operation kann an einem Graphen nicht durchgeführt werden?

Accepted Answer

Sortieren der Knoten

Answer

Tiefenensuche

Answer

Breitenensuche

Answer

Einfügen eines neuen Knotens

Question 28

Warum sind Bäume effizient für die Suche?

Accepted Answer

Sie nutzen ihre hierarchische Struktur aus.

Answer

Sie speichern die Daten in alphabetischer Reihenfolge.

Answer

Sie sind immer vollständig verbunden.

Answer

Sie können nur eindeutige Elemente speichern.

Question 29

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

Accepted Answer

Dijkstra-Algorithmus

Answer

Kruskal-Algorithmus

Answer

Bubble-Sort-Algorithmus

Answer

Mergesort-Algorithmus

Question 30

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

Accepted Answer

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

Answer

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

Answer

Ein gerichteter Graph kann Zyklen enthalten, ein ungerichteter Graph nicht.

Answer

Es gibt keinen Unterschied zwischen diesen beiden Graphentypen.

Question 31

Welche Datenstruktur eignet sich zur Abbildung von Beziehungen zwischen Objekten?

Accepted Answer

Graph

Answer

Baum

Answer

Liste

Answer

Menge

Question 32

Welche Diagrammart kann keine Zyklen enthalten?

Accepted Answer

Spannbaum

Answer

Ungelenkter Graph

Answer

Gerichteter Graph

Answer

Vollständiger Graph

Question 33

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

Accepted Answer

Dijkstra-Algorithmus

Answer

Kruskal-Algorithmus

Answer

Prima-Algorithmus

Answer

Breadth-First-Search

Question 34

Welche der folgenden Aussagen beschreibt einen Baum korrekt?

Accepted Answer

Eine nicht-lineare Datenstruktur, die aus einer Wurzel und darunter liegenden Knoten besteht.

Answer

Eine lineare Datenstruktur, die Elemente in einer bestimmten Reihenfolge speichert.

Answer

Eine Datenstruktur, in der jedes Element mehrere übergeordnete Elemente haben kann.

Answer

Eine Datenstruktur, die Zyklen enthalten kann.

Question 35

Welches ist ein Vorteil der Verwendung eines binären Suchbaums?

Accepted Answer

Schnelle Suche und Einfügung von Elementen.

Answer

Einfache Iteration über alle Elemente.

Answer

Speicherung einer großen Anzahl von Elementen in einem begrenzten Speicherplatz.

Answer

Unterstützung komplexer Abfragen.

Question 36

Welche Operation kann an einem Graphen NICHT durchgeführt werden?

Accepted Answer

Binäre Suche

Answer

Tiefen- oder Breitensuche

Answer

Topologische Sortierung

Answer

Kürzester Pfad-Algorithmus

Question 37

Welche Datenstruktur eignet sich am besten zur Darstellung einer Hierarchie?

Accepted Answer

Baum

Answer

Tabelle

Answer

Liste

Answer

Verkettete Liste

Question 38

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

Accepted Answer

Gerichtete Graphen haben Kanten mit Richtung, ungerichtete Graphen nicht.

Answer

Gerichtete Graphen erlauben Zyklen, ungerichtete Graphen nicht.

Answer

Ungerichtete Graphen erlauben Zyklen, gerichtete Graphen nicht.

Answer

Ungerichtete Graphen haben Kanten mit Gewicht, gerichtete Graphen nicht.

Question 39

Welche Implementierung eines Binärbaums ist NICHT platzsparend?

Accepted Answer

Verkettete Listen

Answer

Expliziter Speicher

Answer

Impliziter Speicher

Answer

Arrays

Question 40

Welcher Begriff beschreibt eine Datenstruktur, bei der die Elemente nicht in einer linearen Abfolge angeordnet sind?

Accepted Answer

Nicht-lineare Datenstruktur

Answer

Lineare Datenstruktur

Answer

Sequentielle Datenstruktur

Answer

Hierarchische Datenstruktur

Question 41

Was versteht man unter einem Knoten in einem Baum?

Accepted Answer

Ein Element des Baums

Answer

Ein Zweig des Baums

Answer

Die Wurzel des Baums

Answer

Ein Blatt des Baums

Question 42

Was stellt eine Kante in einem Graphen dar?

Accepted Answer

Eine Verbindung zwischen zwei Knoten

Answer

Einen Knoten im Graphen

Answer

Einen Pfad im Graphen

Answer

Einen Kreis im Graphen

Question 43

Was ist ein Algorithmus?

Accepted Answer

Eine präzise Schritt-für-Schritt-Anleitung zur Lösung eines Problems

Answer

Ein Computerprogramm

Answer

Eine Datenstruktur zur Speicherung von Informationen

Answer

Ein Diagramm zur Visualisierung von Daten

Question 44

Welche Art von Algorithmus löst Probleme, indem er sie in kleinere Teilprobleme aufteilt?

Accepted Answer

Rekursiver Algorithmus

Answer

Iterativer Algorithmus

Answer

Linearer Algorithmus

Answer

Nichtlinearer Algorithmus

Question 45

Was versteht man unter der Laufzeit eines Algorithmus?

Accepted Answer

Die Zeit, die zur Ausführung des Algorithmus benötigt wird

Answer

Die Anzahl der Schritte, die der Algorithmus ausführt

Answer

Die Menge an Speicher, die der Algorithmus benötigt

Answer

Die Anzahl der Eingaben, die der Algorithmus verarbeiten kann

Question 46

Welche Datenstruktur wird verwendet, um eine Sammlung eindeutiger Elemente zu speichern?

Accepted Answer

Menge

Answer

Array

Answer

Liste

Answer

Stapel

Question 47

Welches der folgenden Merkmale trifft auf einen Baum zu?

Accepted Answer

Hat genau einen Wurzelknoten

Answer

Kann Zyklen enthalten

Answer

Ist eine flache Struktur

Answer

Speichert Daten in beliebiger Reihenfolge

Question 48

Welche der folgenden Traversierungsmethoden wird verwendet, um alle Knoten in einem Baum in der gleichen Tiefe abzuarbeiten?

Accepted Answer

Levelorder

Answer

Preorder

Answer

Inorder

Answer

Postorder

Question 49

Welche der folgenden Anweisungen fügt ein neues Element am Ende einer nicht-linearen Datenstruktur ein?

Accepted Answer

push

Answer

pop

Answer

insert

Answer

remove

Question 50

Welche der folgenden Anwendungen verwendet **keine** nicht-linearen Datenstrukturen?

Accepted Answer

Textverarbeitung

Answer

Soziale Netzwerke

Answer

Datenbanken

Answer

Webseiten

Question 51

Wie lautet die Komplexität der Tiefensuche eines **ausgeglichenen** Binärbaums mit n Knoten?

Accepted Answer

O(n)

Answer

O(log(n))

Answer

O(n^2)

Answer

O(n log(n))

Question 52

Welche der folgenden Aussagen über Bäume ist korrekt?

Accepted Answer

Ein Baum ist eine hierarchische Datenstruktur, in der jeder Knoten höchstens einen Elternknoten und mehrere Kindknoten haben kann.

Answer

Ein Baum ist eine lineare Datenstruktur, in der die Elemente in einer definierten Reihenfolge angeordnet sind.

Question 53

Welche der folgenden Aussagen über Graphen ist korrekt?

Accepted Answer

Ein Graph besteht aus einer Menge von Knoten und einer Menge von Kanten, die die Knoten verbinden.

Answer

Ein Graph ist eine hierarchische Datenstruktur, in der jeder Knoten höchstens einen Elternknoten und mehrere Kindknoten haben kann.

Answer

Ein Graph ist eine lineare Datenstruktur, in der die Elemente in einer definierten Reihenfolge angeordnet sind.

Question 54

Welche der folgenden Datenstrukturen ist am besten geeignet, um hierarchische Beziehungen darzustellen?

Accepted Answer

Baum

Answer

Liste

Answer

Tabelle

Question 55

Welche der folgenden Datenstrukturen ist am besten geeignet, um soziale Netzwerke zu modellieren?

Accepted Answer

Graph

Answer

Baum

Answer

Liste

Answer

Tabelle

Question 56

Welche Aussage zum Aufbau eines Baums trifft zu?

Accepted Answer

Ein Baum besteht aus Knoten, die über Kanten miteinander verbunden sind.

Answer

Ein Baum besteht aus Blättern, die an Ästen befestigt sind.

Answer

Ein Baum ist eine lineare Datenstruktur.

Question 57

Welche Eigenschaft beschreibt einen Binärbaum?

Accepted Answer

Jeder Knoten hat maximal zwei Kindknoten.

Answer

Ein Binärbaum ist immer sortiert.

Answer

Ein Binärbaum ist immer vollständig.

Answer

Jeder Knoten kann eine beliebige Anzahl von Kindknoten haben.

Question 58

In welcher praktischen Anwendung wird ein Baum verwendet?

Accepted Answer

Speicherung einer hierarchischen Datenstruktur, wie z.B. eines Dateisystems

Answer

Sortierung von Daten

Answer

Darstellung von Zahlenfolgen

Question 59

Welche Aussage zur Tiefensuche in einem Graphen ist richtig?

Accepted Answer

Die Tiefensuche besucht Knoten auf einem Pfad von der Wurzel bis zu einem Blatt.

Answer

Die Tiefensuche besucht alle Knoten auf derselben Ebene.

Answer

Die Tiefensuche ist immer effizienter als die Breitensuche.

Question 60

Welche Datenstruktur eignet sich am besten zur Darstellung eines Netzwerks von Computern?

Accepted Answer

Graph

Answer

Hashtabelle

Answer

Liste

Answer

Array

Question 61

Welche Aussage zur Implementierung eines Baums in Java ist korrekt?

Accepted Answer

Die Klasse 'TreeSet' implementiert einen sortierten Binärbaum.

Answer

Die Klasse 'HashMap' implementiert einen Binärsuchbaum.

Answer

Die Klasse 'ArrayList' implementiert einen Baum mit beliebiger Verzweigung.

Question 62

Welche Datenstruktur kann verwendet werden, um eine Hierarchie von Objekten darzustellen, in der jedes Objekt mehrere übergeordnete Objekte haben kann?

Accepted Answer

Gerichteter azyklischer Graph (DAG)

Answer

Queue

Answer

Hashtabelle

Answer

Binärbaum

Question 63

Welche der folgenden Eigenschaften trifft auf einen Baum zu?

Accepted Answer

Ein Baum ist eine gerichtete, azyklische, hierarchische Datenstruktur.

Answer

Ein Baum ist eine lineare Datenstruktur.

Answer

Ein Baum kann Zyklen enthalten.

Question 64

Welche der folgenden Operationen kann an einem Binärbaum durchgeführt werden?

Accepted Answer

Infix-Durchlauf

Answer

Hashing

Answer

Quick-Sort

Answer

Binary-Search