Arbeitsblatt Datenstrukturen mit Lösungen

Was wird bei der Darstellung eines Graphen als Adjazenzliste für jeden Knoten gespeichert?

1. ADer kürzeste Weg zu jedem anderen Knoten
2. BEine Zeile aus V booleschen Werten
3. CEine Liste seiner Nachbarknoten
4. DDie Gesamtzahl der Kanten im Graphen

Die Tiefe eines Knotens in einem Baum ist:

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

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

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

Was gilt für die Adjazenzmatrix eines ungerichteten Graphen?

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

Was ist der größtmögliche Füllgrad einer Hashtabelle mit offener Adressierung?

1. A1
2. B2
3. CEs gibt kein Maximum
4. D0,5

Eine Queue wird mit zwei Stacks implementiert: push auf einen „in“-Stack und pop von einem „out“-Stack, der aus „in“ nachgefüllt wird, wenn er leer ist. Wie hoch sind die amortisierten Kosten pro Operation?

1. AO(1)
2. BO(log n)
3. CO(n²)
4. DO(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 einfach verkettete Liste der Fensterelemente
2. BEin für jedes Fenster neu aufgebauter Min-Heap
3. CEine Deque mit Indizes in absteigender Reihenfolge der Werte
4. DEin sortiertes Array, das durch Verschieben aktualisiert wird

Was ist der Hauptvorteil einer Skip-Liste gegenüber einer sortierten verketteten Liste?

1. AGarantierte Suche in O(1), weil jeder Knoten einen Zeiger auf jeden anderen Knoten speichert
2. BErwartete Suche in O(log n) durch mehrere Ebenen von Vorwärtszeigern
3. CSie benötigt keinen zusätzlichen Speicher
4. DSie speichert Schlüssel ungeordnet