Arbeitsblatt Datenstrukturen mit Lösungen

Welche Datenstruktur arbeitet nach dem Prinzip „first in, first out“ (FIFO)?

1. AWarteschlange (Queue)
2. BHeap
3. CStapel (Stack)
4. DBinärbaum

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

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

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

1. AKnoten, dann linker Teilbaum, dann rechter Teilbaum
2. BRechter Teilbaum, dann Knoten, dann linker Teilbaum
3. CLinker Teilbaum, dann rechter Teilbaum, dann Knoten
4. DLinker Teilbaum, dann Knoten, dann rechter Teilbaum

Ein Knoten in einem binären Suchbaum hat einen rechten Teilbaum. Wo liegt sein In-Order-Nachfolger?

1. AAm linkesten Knoten seines rechten Teilbaums
2. BImmer bei seinem rechten Kind
3. CImmer bei seinem Elternknoten
4. DAm rechtesten Knoten seines linken Teilbaums

Wie viel Speicher benötigt eine Adjazenzmatrix für einen Graphen mit V Knoten?

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

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

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

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

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(1) Zeit und O(1) zusätzlicher Speicher
4. DO(n) Zeit und O(n) zusätzlicher Speicher