Arbeitsblatt Datenstrukturen mit Lösungen

Welche Datenstruktur wird für eine Level-Order-Traversierung eines Baums verwendet?

1. AStack
2. BHashtabelle
3. CQueue
4. DPrioritätswarteschlange

Wie werden die Elemente eines Arrays im Speicher abgelegt?

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

Was macht eine Hashfunktion in einer Hashtabelle?

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

Was gilt für die Adjazenzmatrix eines ungerichteten Graphen?

1. ASie ist immer eine obere Dreiecksmatrix
2. BIhre Hauptdiagonale enthält immer Einsen
3. CJede Zeile hat genau eine 1
4. DSie ist symmetrisch zur Hauptdiagonale

In einem binären Min-Heap, der in einem Array gespeichert ist (Index beginnt bei 0), liegen die Kinder des Knotens mit Index i bei:

1. Ai/2 und i/2 + 1
2. B2i und 2i + 1
3. Ci + 1 und i + 2
4. D2i + 1 und 2i + 2

AVL-Bäume und Rot-Schwarz-Bäume garantieren:

1. ASuche in konstanter Zeit in jedem Fall
2. BEine Höhe von O(log n) durch Rebalancierung
3. CDass kein Knoten zwei Kindknoten hat
4. DDass die Schlüssel in Einfügereihenfolge gespeichert werden

Welche Laufzeit hat die Breitensuche auf einem Graphen mit V Knoten, der als Adjazenzmatrix gespeichert ist?

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

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

1. ASortieren des Arrays und binäre Suche
2. BFinden des Medians in O(1)
3. CPräfixsummen-Abfragen und Aktualisierungen einzelner Elemente
4. DEinfügen von Elementen an beliebiger Position