Bäume: Quizfragen und Übungen für Algorithmen und Datenstrukturen

Question 1

Welche Datenstruktur kann als Suchbaum verwendet werden, um Schlüssel-Werte-Paare zu speichern?

Accepted Answer

Binärer Suchbaum

Answer

Hashtabelle

Answer

Heap

Answer

Liste

Question 2

Welche wesentliche Anforderung erfüllt ein AVL-Baum?

Accepted Answer

Der Baum ist immer balanciert

Answer

Alle Knoten haben den gleichen Grad

Answer

Die Höhe des Baumes ist minimal

Answer

Die Anzahl der Blätter ist maximal

Question 3

Welche Operation an einem Binärbaum hat eine Laufzeitkomplexität von O(n)?

Accepted Answer

Durchlauf

Answer

Einfügen

Answer

Löschen

Answer

Suchen

Question 4

Was ist der Vorteil eines balancierten Binärbaums gegenüber einem unbalancierten Binärbaum?

Accepted Answer

Schnellere Suchoperationen

Answer

Geringerer Speicherbedarf

Answer

Einfachere Implementierung

Answer

Robustheit gegenüber Datenänderungen

Question 5

Welche Methode wird verwendet, um einen Knoten aus einem Binärsuchbaum zu entfernen?

Accepted Answer

Delete

Answer

Insert

Answer

Find

Answer

Count

Question 6

Welches Kriterium ist NICHT Teil der Definition eines Binärbaums?

Accepted Answer

Die Baumhöhe ist begrenzt

Answer

Jeder Knoten hat höchstens zwei Kindknoten

Question 7

Welche Eigenschaft zeichnet einen Suchbaum aus?

Accepted Answer

Alle Elemente im linken Teilbaum sind kleiner als die Elemente im rechten Teilbaum

Answer

Jeder Knoten speichert einen eindeutigen Schlüssel

Question 8

Welche Operation kann an einem Binärbaum durchgeführt werden, um eine sortierte Liste seiner Elemente zu erhalten?

Accepted Answer

In-Order-Traversierung

Answer

Pre-Order-Traversierung

Question 9

Welche Laufzeitkomplexität hat die Suche nach einem Knoten in einem BST mit n Knoten im schlimmsten Fall?

Accepted Answer

O(n)

Answer

O(log n)

Question 10

Welche Operation kann an einem AVL-Baum durchgeführt werden, um seine Balance wiederherzustellen?

Accepted Answer

Rotation

Answer

Umsortieren

Question 11

Welche Laufzeitkomplexität besitzt die Einfügeoperation in einem binären Suchbaum?

Accepted Answer

O(logarithmus der Anzahl der Knoten)

Answer

O(Anzahl der Knoten)

Answer

O(Produkt aus Anzahl der Knoten und Logarithmus der Anzahl der Knoten)

Answer

O(Quadrat der Anzahl der Knoten)

Question 12

Was kennzeichnet einen vollständigen Binärbaum?

Accepted Answer

Alle Blätter befinden sich auf derselben Ebene.

Answer

Alle Knoten besitzen Kindknoten.

Answer

Die Anzahl der Blätter ist minimal.

Answer

Die Höhe des Baumes ist minimal.

Question 13

Welche Aussage zur Inorder-Traversierung eines binären Suchbaums trifft zu?

Accepted Answer

Erzeugt eine sortierte Liste der Knotenwerte in aufsteigender Reihenfolge.

Answer

Erzeugt eine sortierte Liste der Knotenwerte in absteigender Reihenfolge.

Answer

Erzeugt eine unsortierte Liste der Knotenwerte.

Answer

Erzeugt eine Liste der Knotenwerte in Postorder-Reihenfolge.

Question 14

Welche maximale Höhe kann ein AVL-Baum mit n Knoten besitzen?

Accepted Answer

O(logarithmus von n)

Answer

O(n)

Answer

O(n²)

Answer

O(logarithmus von n im Quadrat)

Question 15

Welche Aufgabe hat ein Knotenattribut in einem binären Suchbaum?

Accepted Answer

Speichert den Wert des Knotens.

Answer

Speichert einen Verweis auf den linken Kindknoten.

Answer

Speichert einen Verweis auf den rechten Kindknoten.

Answer

Speichert die Höhe des Knotens.

Question 16

Was unterscheidet einen Binärbaum von einem binären Suchbaum?

Accepted Answer

Ein Binärbaum kann eine beliebige Struktur aufweisen, während ein binärer Suchbaum eine bestimmte Anordnung besitzt.

Answer

Ein binärer Suchbaum kann eine beliebige Struktur aufweisen, während ein Binärbaum eine bestimmte Anordnung besitzt.

Answer

Ein Binärbaum speichert numerische Daten, während ein binärer Suchbaum Zeichenketten speichert.

Answer

Ein binärer Suchbaum speichert numerische Daten, während ein Binärbaum Zeichenketten speichert.

Question 17

Welche Traversierungsmethode erzeugt eine Liste der Knoten entsprechend ihrer Höhe?

Accepted Answer

Levelorder

Answer

Preorder

Answer

Inorder

Answer

Postorder

Question 18

Welcher Baumtyp ist dadurch definiert, dass jeder Knoten maximal einen Kindknoten haben kann?

Accepted Answer

Binärbaum

Answer

B-Baum

Answer

AVL-Baum

Answer

Rot-Schwarz-Baum

Question 19

Welche Laufzeitkomplexität hat im schlimmsten Fall die Suche nach einem Element in einem binären Suchbaum?

Accepted Answer

O(log n)

Answer

O(1)

Answer

O(n)

Answer

O(n^2)

Question 20

Welche Eigenschaft muss ein AVL-Baum erfüllen, um als ausgeglichen zu gelten?

Accepted Answer

Jeder Knoten hat einen ausgeglichenen Höhenunterschied zu seinen Kindknoten.

Answer

Jeder Knoten hat ein ausgeglichenes Gewicht.

Answer

Jeder Knoten hat eine ausgeglichene Anzahl von Kindknoten.

Answer

Jeder Knoten hat eine ausgeglichene Tiefe.

Question 21

Welche Informationen werden typischerweise in den Knoten eines binären Suchbaums gespeichert?

Accepted Answer

Beide (Schlüssel und Wert)

Answer

Schlüssel

Answer

Wert

Answer

Keine der genannten Optionen

Question 22

Was ist der wesentliche Unterschied zwischen einem vollständigen und einem vollständigen Binärbaum?

Accepted Answer

Ein vollständiger Binärbaum hat alle Blätter auf derselben Ebene.

Answer

Ein vollständiger Binärbaum hat alle Ebenen gefüllt.

Answer

Ein vollständiger Binärbaum hat alle Knoten mit genau zwei Kindknoten.

Answer

Es gibt keinen Unterschied.

Question 23

Welche Baumstruktur wird in einer Heap-Datenstruktur verwendet?

Accepted Answer

Binärer Baum

Answer

B-Baum

Answer

AVL-Baum

Answer

Rot-Schwarz-Baum

Question 24

Welches Merkmal trifft auf Binärbäume zu?

Accepted Answer

Jeder Knoten hat maximal zwei Kindknoten.

Answer

Blätter sind immer auf der obersten Ebene.

Answer

Die Höhe eines Baumes entspricht der Anzahl seiner Knoten.

Answer

Binärbäume sind immer vollständig.

Question 25

Welcher Algorithmus hat eine Laufzeitkomplexität von O(log n) für das Suchen und Einfügen in einen Binärsuchbaum?

Accepted Answer

Binäre Suche

Answer

Heapsort

Answer

Quicksort

Answer

Breadth-First-Search

Question 26

Was beschreibt die Höhe eines Binärbaums?

Accepted Answer

Anzahl der Ebenen im Baum

Answer

Anzahl der Knoten im Baum

Answer

Maximale Knotenzahl auf einer Ebene

Answer

Minimale Knotenzahl auf einer Ebene

Question 27

Welche Traversal-Methode besucht die Knoten eines Binärbaums in der Reihenfolge Wurzel, linker Teilbaum, rechter Teilbaum?

Accepted Answer

Preorder-Traversal

Answer

Inorder-Traversal

Answer

Postorder-Traversal

Answer

Levelorder-Traversal

Question 28

Welche Datenstruktur eignet sich am besten für die Speicherung hierarchischer Daten wie XML?

Accepted Answer

Binärbaum

Answer

Array

Answer

Hash-Tabelle

Answer

Binärer Heap

Question 29

Welche Aussage über AVL-Bäume ist korrekt?

Accepted Answer

Immer höhenbalanciert

Answer

Immer perfekt balanciert

Answer

Nur für Suchen und Einfügen verwendbar

Answer

Effizienter als Binärsuchbäume

Question 30

Welcher Baumtyp hat höchstens zwei Kindknoten pro Knoten?

Accepted Answer

Binärbaum

Answer

Binärer Heap

Answer

K-ärer Baum

Answer

AVL-Baum

Question 31

Welcher Datentyp ist ein Baum?

Accepted Answer

Binärbaum

Answer

Array

Answer

Stapel

Answer

Warteschlange

Question 32

Welche Operation in einem binären Suchbaum hat eine Laufzeitkomplexität von O(log n)?

Accepted Answer

Suchen

Answer

Einfügen

Answer

Löschen

Answer

Traversal

Question 33

Wie hoch ist maximal ein AVL-Baum mit n Knoten?

Accepted Answer

log2 n

Answer

log10 n

Answer

n

Answer

n log2 n

Question 34

Welcher Baumtyp wird zur Implementierung von Priority-Warteschlangen verwendet?

Accepted Answer

Bin heap

Answer

Binärbaum

Answer

AVL-Baum

Answer

Rot-Schwarz-Baum

Question 35

Welche Eigenschaft sorgt dafür, dass ein BST ein Suchbaum ist?

Accepted Answer

Inorder-Traversal ergibt eine sortierte Liste

Answer

Preorder-Traversal ergibt eine sortierte Liste

Answer

Postorder-Traversal ergibt eine sortierte Liste

Answer

Levelorder-Traversal ergibt eine sortierte Liste

Question 36

Welche Aussage zur Levelorder-Traversal ist korrekt?

Accepted Answer

Sie besucht die Knoten in aufsteigender Höhe

Answer

Sie besucht die Knoten in absteigender Höhe

Answer

Sie besucht die Knoten in zufälliger Reihenfolge

Answer

Sie besucht nur die Knoten auf der untersten Ebene

Question 37

Welcher Baumtyp hat die Eigenschaft, dass jeder Blattknoten die gleiche Tiefe hat?

Accepted Answer

Vollständiger Binärbaum

Answer

Binärbaum

Answer

AVL-Baum

Answer

B-Baum

Question 38

Welche Laufzeitkomplexität hat die in-order-Traversierung eines binären Suchbaums mit n Knoten?

Accepted Answer

O(n)

Answer

O(log n)

Answer

O(n log n)

Answer

O(n^2)

Question 39

Welcher der folgenden Algorithmen verwendet Bäume als Datenstruktur:

Accepted Answer

Dijkstra-Algorithmus

Answer

Bubble-Sort-Algorithmus

Answer

Lineare Suche

Answer

Merge-Sort-Algorithmus

Question 40

Welche Eigenschaft ist für Bäume charakteristisch?

Accepted Answer

Hierarchische Struktur

Answer

Zyklische Struktur

Answer

Lineare Struktur

Answer

Gitterartige Struktur

Question 41

Welcher der folgenden Traversierungsverfahren besucht die Knoten eines binären Suchbaums in aufsteigender Reihenfolge?

Accepted Answer

In-order

Answer

Pre-order

Answer

Post-order

Answer

Level-order

Question 42

Was ist der Unterschied zwischen einem Binärbaum und einem vollständigen Binärbaum?

Accepted Answer

Ein vollständiger Binärbaum hat immer alle Ebenen gefüllt

Answer

Ein vollständiger Binärbaum hat immer eine ungerade Anzahl von Knoten

Answer

Ein vollständiger Binärbaum hat immer eine gerade Anzahl von Ebenen

Answer

Ein vollständiger Binärbaum hat immer eine maximale Höhe

Question 43

Welche der folgenden Datenstrukturen ermöglicht die effiziente Suche und Einfügung von Daten in einer hierarchisch organisierten Struktur?

Accepted Answer

Baum

Answer

Verkettete Liste

Answer

Array

Answer

Hashtabelle

Question 44

Welche Art von Baum ist charakterisiert durch eine maximale Anzahl von zwei Kindknoten pro Knoten?

Accepted Answer

Binärbaum

Answer

AVL-Baum

Answer

Balancierter Baum

Answer

Suchbaum

Question 45

Was ist der Hauptunterschied zwischen einem Binärsuchbaum und einem AVL-Baum?

Accepted Answer

AVL-Bäume garantieren eine maximale Höhe, während Binärsuchbäume keine Höhenbeschränkung haben.

Answer

Binärsuchbäume garantieren eine maximale Höhe, während AVL-Bäume keine Höhenbeschränkung haben.

Answer

Binärsuchbäume sind immer balancierter als AVL-Bäume.

Question 46

Welche der folgenden Aussagen über Binärbäume ist richtig?

Accepted Answer

Jeder Knoten hat maximal zwei Kindknoten.

Answer

Binärbäume können nur numerische Daten speichern.

Answer

Binärbäume sind immer sortiert.

Answer

Die Höhe eines Binärbaums ist immer gleich der Anzahl seiner Knoten.

Question 47

Welche Datenstruktur ermöglicht die effiziente Suche anhand eines Schlüssels unter Verwendung der binären Suche?

Accepted Answer

Binärer Suchbaum

Answer

Hash-Tabelle

Answer

Verkettete Liste

Answer

Heap

Question 48

Was ist die Laufzeitkomplexität für das Einfügen eines Knotens in einen AVL-Baum?

Accepted Answer

O(log₂ n)

Answer

O(n)

Answer

O(n²)

Answer

O(1)

Question 49

Welche Eigenschaft ist charakteristisch für einen vollständigen Binärbaum?

Accepted Answer

Jeder interne Knoten hat genau zwei Kindknoten

Answer

Die Anzahl der internen Knoten ist immer größer als die Anzahl der Blätter

Answer

Die Höhe des Baumes ist immer minimal

Question 50

Welcher Algorithmus eignet sich am besten, um die Höhe eines Binärbaums zu berechnen?

Accepted Answer

Rekursive Tiefensuche

Answer

Topologische Sortierung

Answer

Breitensuche

Answer

Kruskal-Algorithmus

Question 51

Was unterscheidet AVL-Bäume grundsätzlich von Binärbäumen?

Accepted Answer

AVL-Bäume sind selbst-ausgleichend und garantieren eine O(log₂ n) Laufzeitkomplexität für Suchoperationen, während Binärbäume möglicherweise unausgeglichen sind und eine O(n) Laufzeitkomplexität aufweisen können

Answer

AVL-Bäume speichern numerische Werte, während Binärbäume Zeichenfolgen speichern

Question 52

Welche Operation lässt sich in einem Binärbaum nicht effizient durchführen?

Accepted Answer

Suchen eines Elements anhand seines Index

Answer

Löschen eines Elements

Answer

Einfügen eines Elements

Answer

Überprüfen, ob der Baum leer ist

Question 53

Welche Aussage über die maximale Höhe eines AVL-Baums mit n Knoten ist korrekt?

Accepted Answer

Sie beträgt etwa 1,44 log₂(n) + O(1)

Answer

Sie ist immer kleiner als n

Answer

Sie ist proportional zu n

Answer

Sie kann variieren, abhängig von der Einfügereihenfolge der Knoten

Question 54

Welcher Suchbaumtyp weist die schlechteste Time-Space-Kompromittierung auf?

Accepted Answer

Binärer Suchbaum mit mehrfachen Schlüsseln pro Knoten

Answer

AVL-Baum

Answer

Rot-Schwarz-Baum

Answer

B-Baum

Question 55

Welche der folgenden Aussagen zu Binärbäumen ist **falsch**?

Accepted Answer

Jeder Knoten in einem Binärbaum hat genau zwei Kinder.

Answer

Ein Binärbaum kann leer sein.

Answer

Ein Binärbaum kann maximal ein Wurzelknoten haben.

Answer

Die Tiefe eines Binärbaums ist die Anzahl der Kanten vom Wurzelknoten zum tiefsten Blatt.

Question 56

Welche Laufzeitkomplexität hat das Einfügen eines Knotens in einen **sortierten** Binärbaum im schlimmsten Fall?

Accepted Answer

O(n)

Answer

O(log n)

Answer

O(h)

Answer

O(1)

Question 57

Welche der folgenden Datenstrukturen ist **kein** Suchbaum?

Accepted Answer

Heap

Answer

B-Baum

Answer

Binärer Suchbaum (BST)

Answer

AVL-Baum

Question 58

Welches Problem wird durch AVL-Bäume gelöst?

Accepted Answer

Die Gefahr von Ungleichgewichten in Binärbäumen, die zu einer schlechten Suchleistung führen.

Answer

Überlastung des Speichers durch Binärbäume.

Answer

Redundante Daten in Binärbäumen.

Question 59

Welche Operationen werden in einem AVL-Baum durchgeführt, um die Balance nach einer Einfüge- oder Lösch-Operation wiederherzustellen?

Accepted Answer

Rotationen

Answer

Hashing.

Answer

Einfügen neuer Knoten.

Answer

Löschen von Knoten.

Question 60

Welche Laufzeitkomplexität hat das Suchen eines Knotens in einem **ausgeglichenen** AVL-Baum im Durchschnitt?

Accepted Answer

O(log n)

Answer

O(1)

Answer

O(n log n)

Answer

O(n)

Question 61

Welche der folgenden Traversierungsmethoden wird häufig zum Durchlaufen aller Knoten in einem Binärbaum verwendet?

Accepted Answer

Preorder-Traversierung

Answer

Bubblesort

Answer

Hashing

Answer

Quicksort

Question 62

Welches Merkmal zeichnet einen **vollständigen** Binärbaum aus?

Accepted Answer

Alle Ebenen außer der letzten sind vollständig gefüllt, und die Knoten der letzten Ebene sind so weit wie möglich nach links ausgerichtet.

Answer

Jeder Knoten hat genau zwei Kinder.

Answer

Alle Knoten haben den gleichen Abstand zur Wurzel.

Question 63

Welche der folgenden Anwendungen profitiert **besonders** von der Verwendung von Bäumen?

Accepted Answer

Speichern von Daten in einer Datenbank

Answer

Kommunizieren über ein Netzwerk.

Answer

Speichern von Text in einem Texteditor

Answer

Verarbeiten von Musikdateien.

Question 64

In welchem Szenario ist ein **Heap** eine geeignetere Datenstruktur als ein Binärsuchbaum?

Accepted Answer

Wenn die effiziente Suche nach dem kleinsten oder größten Element im Baum erforderlich ist.

Answer

Wenn die effiziente Suche nach einem bestimmten Element erforderlich ist.

Answer

Wenn die effiziente Einfügung und Löschung von Elementen an beliebiger Stelle im Baum erforderlich ist.