Arbeitsblatt Datenstrukturen mit Lösungen

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

1. AStapel (Stack)
2. BWarteschlange (Queue)
3. CHashtabelle
4. DVerkettete Liste

Eine Hashtabelle speichert Daten als:

1. ABaum mit geordneten Schlüsseln
2. BSchlüssel-Wert-Paare, die über eine Hashfunktion gefunden werden
3. CAusschließlich sortierte Liste
4. DZeichenkette fester Länge

Was macht eine Hashfunktion in einer Hashtabelle?

1. ASie sortiert die Schlüssel 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 verschlüsselt die Werte in der Tabelle

Wie viele Knoten hat ein perfekter Binärbaum der Höhe h, wenn die Höhe in Kanten gezählt wird?

1. A2h + 1
2. B2^h+1 − 1
3. Ch²
4. D2^h

Eine In-Order-Traversierung eines binären Suchbaums besucht die Schlüssel in:

1. AImmer absteigender Reihenfolge
2. BAufsteigend sortierter Reihenfolge
3. CEbenenweiser Reihenfolge (Level-Order)
4. DEinfügereihenfolge

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 2 5 1 3
3. C4 5 2 3 1
4. D5 4 3 2 1

Die Schlüssel 5, 3, 8, 1 werden in dieser Reihenfolge in einen leeren, arraybasierten binären Min-Heap eingefügt. Wie sieht das Array am Ende aus?

1. A[1, 3, 5, 8]
2. B[1, 3, 8, 5]
3. C[3, 1, 8, 5]
4. D[1, 5, 8, 3]

Welche Operationen unterstützt ein Fenwick-Baum (Binary Indexed Tree) über einem Array von n Zahlen in O(log n)?

1. AFinden des Medians in O(1)
2. BPräfixsummen-Abfragen und Aktualisierungen einzelner Elemente
3. CEinfügen von Elementen an beliebiger Position
4. DSortieren des Arrays und binäre Suche