Arbeitsblatt Datenstrukturen mit Lösungen

Was ist eine Kollision in einer Hashtabelle?

1. AZwei verschiedene Schlüssel werden auf denselben Index abgebildet
2. BDer Tabelle geht der Speicher aus
3. CEin Schlüssel lässt sich überhaupt nicht hashen
4. DZwei gleiche Schlüssel werden doppelt gespeichert

Welche Operation ist in einem Array langsam, am Kopf einer verketteten Liste aber schnell?

1. ABestimmen der Länge eines Arrays fester Größe
2. BLesen des letzten Elements per Index
3. CZugriff auf das 5. Element
4. DEinfügen am Anfang

In einer einfach verketteten Liste enthält jeder Knoten:

1. ANur Daten
2. BDaten und Referenzen auf alle anderen Knoten
3. CDaten und eine Referenz auf den nächsten Knoten
4. DDaten und einen Index

Was gilt für die Adjazenzmatrix eines ungerichteten Graphen?

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

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 − 1) / 2⌋
2. BBei Index ⌊i / 2⌋ + 1
3. CBei Index 2i + 1
4. DBei Index i − 1

Eine Anwendung braucht schnelle Suchen, muss aber auch Schlüssel sortiert auflisten und Bereichsabfragen beantworten. Welche Struktur passt am besten?

1. AEin balancierter binärer Suchbaum
2. BEine Hashtabelle
3. CEin Stack
4. DEine unsortierte verkettete Liste

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(α(n))
2. BO(1)
3. CO(n)
4. DO(log n)

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

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