Arbeitsblatt Datenstrukturen mit Lösungen

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

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

Was enthält in einer einfach verketteten Liste der next-Zeiger des letzten Knotens?

1. ADie Adresse des vorherigen Knotens
2. BDie Adresse des ersten Knotens
3. CDie Anzahl der Knoten in der Liste
4. DNull (keinen Knoten)

Die Höhe eines Baums wird üblicherweise definiert als:

1. ADie Anzahl der Kanten auf dem längsten Pfad von der Wurzel zu einem Blatt
2. BDie Anzahl der Kindknoten der Wurzel
3. CDie Anzahl der Blätter im Baum
4. DDie Gesamtzahl der Knoten im Baum, einschließlich der Wurzel und jedes Blatts

Wo liegt in einem binären Heap, der in einem Array ab Index 0 gespeichert ist, der Elternknoten des Knotens mit Index i?

1. ABei Index 2i + 1
2. BBei Index i − 1
3. CBei Index ⌊i / 2⌋ + 1
4. DBei Index ⌊(i − 1) / 2⌋

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

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

Wie wird in einer zirkulären Queue, die in einem Array der Kapazität n gespeichert ist, die nächste Position nach Index i berechnet?

1. A(i − 1) mod n
2. Bi + 1
3. C(i + 1) mod n
4. D2i + 1

Welche Eigenschaft muss ein Rot-Schwarz-Baum erfüllen?

1. AJeder Knoten muss rot sein
2. BRote Knoten müssen rote Kindknoten haben, sodass rote Knoten immer ununterbrochene Ketten bis zu den Blättern bilden
3. CDie Wurzel muss rot sein
4. DJeder Pfad von einem Knoten zu seinen Nachfahren-Blättern enthält gleich viele schwarze Knoten

Warum könnte ein Server seine Hashfunktion zufällig aus einer universellen Familie wählen?

1. ADamit die Hashtabelle sortiert ist
2. BDamit es sehr unwahrscheinlich ist, dass ein Angreifer viele Schlüssel wählen kann, die alle kollidieren
3. CUm zu garantieren, dass nie zwei Schlüssel kollidieren, welche Schlüssel ein Angreifer auch sendet
4. DDamit die Tabelle nicht mehr vergrößert werden muss