Arbeitsblatt Datenstrukturen mit Lösungen

Was sind Geschwisterknoten in einem Baum?

1. AKnoten mit demselben Elternknoten
2. BKnoten in gleicher Tiefe in verschiedenen Teilbäumen
3. CEin Knoten und sein Elternknoten
4. DKnoten ohne Kindknoten

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

1. AIn zufälliger Reihenfolge
2. BGrößer als der Wert des Knotens
3. CKleiner als der Wert des Knotens
4. DGleich dem Wert des Knotens

Welche Datenstruktur arbeitet nach dem Prinzip „first in, first out“ (FIFO)?

1. AHeap
2. BStapel (Stack)
3. CBinärbaum
4. DWarteschlange (Queue)

Warum ist das Durchlaufen eines Arrays in der Praxis oft viel schneller als das einer gleich langen verketteten Liste?

1. ADas Durchlaufen eines Arrays ist insgesamt O(1), das einer verketteten Liste O(n)
2. BVerkettete Listen speichern Elemente immer auf der Festplatte
3. CArray-Elemente liegen zusammenhängend und nutzen daher den CPU-Cache gut aus
4. DArrays brauchen weniger Instruktionen zum Vergleichen von Werten

Wie viel Speicher benötigt eine Adjazenzliste für einen Graphen mit V Knoten und E Kanten?

1. AO(V × E)
2. BO(V + E)
3. CO(E²)
4. DO(V²)

Was ist der größtmögliche Füllgrad einer Hashtabelle mit offener Adressierung?

1. A2
2. BEs gibt kein Maximum
3. C1
4. D0,5

Welches Paar von Traversierungen bestimmt immer einen eindeutigen Binärbaum mit verschiedenen Schlüsseln?

1. APre-Order und Post-Order
2. BLevel-Order allein
3. CPre-Order allein
4. DPre-Order und In-Order

Ein AVL-Knoten ist unbalanciert, weil der rechte Teilbaum seines linken Kindes zu hoch wurde (Links-rechts-Fall). Welche Korrektur wird angewendet?

1. AEine Linksrotation am linken Kind, dann eine Rechtsrotation am Knoten
2. BEine einfache Linksrotation am Knoten
3. CEine einfache Rechtsrotation am Knoten
4. DEine Rechtsrotation am linken Kind, dann eine Linksrotation am Knoten