Arbeitsblatt Datenstrukturen mit Lösungen

Die Tiefe eines Knotens in einem Baum ist:

1. ADie Anzahl der Kanten von der Wurzel bis zu diesem Knoten
2. BDie Anzahl der Kanten von diesem Knoten bis zum tiefsten Blatt
3. CDie Anzahl der Kindknoten dieses Knotens
4. DDie Anzahl der Knoten in seinem Teilbaum

Wie viele Kanten hat ein Baum mit n Knoten?

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

Was ist eine Kollision in einer Hashtabelle?

1. AEin Schlüssel lässt sich überhaupt nicht hashen
2. BZwei gleiche Schlüssel werden doppelt gespeichert
3. CZwei verschiedene Schlüssel werden auf denselben Index abgebildet
4. DDer Tabelle geht der Speicher aus

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 3
2. BIndex 6
3. CIndex 4
4. DIndex 0

Wie wird in einer zirkulären Queue, die in einem Array der Kapazität n gespeichert ist, die nächste Position nach Index i berechnet?

1. A(i + 1) mod n
2. B2i + 1
3. C(i − 1) mod n
4. Di + 1

Wo liegt in einem binären Heap, der in einem Array ab Index 0 gespeichert ist, der Elternknoten des Knotens mit Index i?

1. ABei Index ⌊i / 2⌋ + 1
2. BBei Index 2i + 1
3. CBei Index ⌊(i − 1) / 2⌋
4. DBei Index i − 1

Wie hoch ist unter der Annahme des einfachen gleichverteilten Hashings die erwartete Suchzeit in einer Hashtabelle mit Chaining, n Schlüsseln und m Buckets?

1. AO(1 + α), wobei α = n / m
2. BO(n)
3. CO(m)
4. DO(log n)

Wie hoch sind Zeit- und zusätzlicher Speicherbedarf, wenn man eine einfach verkettete Liste an Ort und Stelle umkehrt?

1. AO(n) Zeit und O(1) zusätzlicher Speicher
2. BO(n log n) Zeit und O(1) zusätzlicher Speicher
3. CO(n) Zeit und O(n) zusätzlicher Speicher
4. DO(1) Zeit und O(1) zusätzlicher Speicher