Arbeitsblatt Datenstrukturen mit Lösungen

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 Blätter im Baum
3. CDie Gesamtzahl der Knoten im Baum, einschließlich der Wurzel und jedes Blatts
4. DDie Anzahl der Kindknoten der Wurzel

Welche Operation kostet bei einem Array O(1), bei einer einfach verketteten Liste aber O(n)?

1. AEinfügen am Kopf
2. BLesen des ersten Elements
3. CEntfernen des Kopfelements
4. DZugriff auf das Element an Index i

In welcher Reihenfolge besucht eine Post-Order-Traversierung eines Binärbaums die Knoten?

1. AKnoten, dann linker Teilbaum, dann rechter Teilbaum
2. BLinker Teilbaum, dann rechter Teilbaum, dann Knoten
3. CRechter Teilbaum, dann Knoten, dann linker Teilbaum
4. DLinker Teilbaum, dann Knoten, dann rechter Teilbaum

Warum kann ein binärer Heap ganz ohne Zeiger in einem Array gespeichert werden?

1. AEr ist ein vollständiger Binärbaum, daher folgen die Positionen einfachen Indexformeln
2. BAlle Schlüssel in einem Heap sind gleich
3. CHeaps enthalten nie mehr als 100 Elemente
4. DArrays halten Schlüssel automatisch sortiert, sodass keine Zeiger nötig sind

Eine Hashtabelle der Größe 7 verwendet h(k) = k mod 7 und lineares Sondieren. Wo wird 17 gespeichert, nachdem 10 eingefügt wurde?

1. AIndex 0
2. BIndex 6
3. CIndex 3
4. DIndex 4

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

1. AImmer absteigender Reihenfolge
2. BEbenenweiser Reihenfolge (Level-Order)
3. CEinfügereihenfolge
4. DAufsteigend sortierter Reihenfolge

Wie hoch sind ohne Union by Rank und Pfadkompression die Kosten eines einzelnen find im schlechtesten Fall in einer Union-Find-Struktur mit n Elementen?

1. AO(1)
2. BO(n)
3. CO(α(n))
4. DO(log n)

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

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