Arbeitsblatt Datenstrukturen mit Lösungen

In einem binären Suchbaum sind die Werte im linken Teilbaum eines Knotens:

1. AGrößer als der Wert des Knotens
2. BIn zufälliger Reihenfolge
3. CGleich dem Wert des Knotens
4. DKleiner als der Wert des Knotens

Was speichert eine Map (Dictionary)?

1. APaare gleicher Schlüssel
2. BNur Werte in Einfügereihenfolge
3. CSchlüssel-Wert-Paare mit eindeutigen Schlüsseln
4. DNach Größe sortierte Werte

Welche Datenstruktur eignet sich am besten für die „Rückgängig“-Funktion (Undo) in einem Texteditor?

1. AHash-Set
2. BGraph
3. CWarteschlange (Queue)
4. DStapel (Stack)

Welche Datenstruktur verwendet die Tiefensuche (DFS) in der iterativen Variante?

1. AEinen Heap
2. BNur eine Hashtabelle
3. CEinen Stack
4. DEine Queue

AVL-Bäume und Rot-Schwarz-Bäume garantieren:

1. ADass die Schlüssel in Einfügereihenfolge gespeichert werden
2. BDass kein Knoten zwei Kindknoten hat
3. CEine Höhe von O(log n) durch Rebalancierung
4. DSuche in konstanter Zeit in jedem Fall

Wie lange dauert es, mit einer Adjazenzmatrix zu prüfen, ob die Kante (u, v) existiert?

1. AO(1)
2. BO(log V)
3. CO(E)
4. DO(V)

Wie hoch sind ohne Union by Rank und Pfadkompression die Kosten eines einzelnen find im schlechtesten Fall in einer Union-Find-Struktur mit n Elementen?

1. AO(log n)
2. BO(n)
3. CO(α(n))
4. DO(1)

Welche Eigenschaft hält jeden B-Baum perfekt balanciert?

1. AJeder Knoten speichert einen Schlüssel
2. BJeder Knoten hat genau zwei Kinder
3. CAlle Blätter liegen in derselben Tiefe
4. DDie Schlüssel werden nur in der Wurzel gespeichert