Arbeitsblatt Datenstrukturen mit Lösungen

Was macht eine Hashfunktion in einer Hashtabelle?

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

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

1. AWarteschlange (Queue)
2. BBinärbaum
3. CStapel (Stack)
4. DHeap

Wie werden die Elemente eines Arrays im Speicher abgelegt?

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

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. A4 2 5 1 3
2. B4 5 2 3 1
3. C1 2 4 5 3
4. D5 4 3 2 1

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

1. AJeder Knoten ist rot oder schwarz gefärbt
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. DAlle Blätter liegen in genau derselben Tiefe

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

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

Mit welcher Struktur lässt sich das Maximum jedes Fensters der Größe k in einem Array insgesamt in O(n) berechnen?

1. AEin für jedes Fenster neu aufgebauter Min-Heap
2. BEine einfach verkettete Liste der Fensterelemente
3. CEine Deque mit Indizes in absteigender Reihenfolge der Werte
4. DEin sortiertes Array, das durch Verschieben aktualisiert wird

Was macht ein Splay-Baum nach jedem Zugriff?

1. AEr rotiert den zugegriffenen Knoten bis zur Wurzel hoch
2. BEr färbt die Knoten auf dem Suchpfad um
3. CEr baut den ganzen Baum in balancierter Form neu auf
4. DEr verschiebt den zugegriffenen Knoten zu einem Blatt