Arbeitsblatt Datenstrukturen mit Lösungen

Wie viele Kanten hat ein Baum mit n Knoten?

1. An + 1
2. Bn
3. C2n
4. Dn − 1

Was macht eine Hashfunktion in einer Hashtabelle?

1. ASie verschlüsselt die Werte in der Tabelle
2. BSie bildet einen Schlüssel auf einen Index in der Tabelle ab
3. CSie zählt, wie viele Schlüssel gespeichert sind
4. DSie sortiert die Schlüssel in der Tabelle

Wie werden die Elemente eines Arrays im Speicher abgelegt?

1. AAn zufälligen, per Hash gewählten Stellen
2. BIn einem Baum aus Speicherseiten
3. CVerstreut, über Zeiger verbunden
4. DIn einem zusammenhängenden Block, eins nach dem anderen

Ein Binärbaum hat die Wurzel 1 mit linkem Kind 2 und rechtem Kind 3; Knoten 2 hat die Kinder 4 (links) und 5 (rechts). Wie lautet die Post-Order-Traversierung?

1. A1 2 4 5 3
2. B4 5 2 3 1
3. C4 2 5 1 3
4. D5 4 3 2 1

Welche Balancebedingung hält ein AVL-Baum an jedem Knoten ein?

1. AAlle Blätter liegen in genau derselben Tiefe
2. BDie Höhen des linken und rechten Teilbaums unterscheiden sich höchstens um 1
3. CBeide Teilbäume jedes Knotens enthalten genau gleich viele Knoten
4. DJeder Knoten ist rot oder schwarz gefärbt

Mit welcher Datenstruktur prüft man, ob die Klammern in "{[()]}" ausgeglichen sind?

1. AMit einer Hashtabelle
2. BMit einem Stack
3. CMit einem binären Suchbaum
4. DMit einer Queue

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

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

Ein Objekt wird als Schlüssel in einer Hashmap gespeichert, danach wird ein Feld geändert, das in seine Hashfunktion eingeht. Was ist die wahrscheinliche Folge?

1. ADie Map verschiebt den Schlüssel automatisch in seinen neuen Bucket
2. BDie Map wirft im Moment der Feldänderung einen Fehler
3. CNichts ändert sich, weil der Hash eines Schlüssels nur einmal beim Programmstart berechnet wird
4. DDie Suche nach dem Objekt kann fehlschlagen, weil es im Bucket seines alten Hashs liegt