Arbeitsblatt Datenstrukturen mit Lösungen

Welche Struktur wird typischerweise zur Implementierung einer Prioritätswarteschlange verwendet?

1. AEine ungeordnete einfach verkettete Liste
2. BEine Zeichenkette
3. CEin Heap
4. DEin Stack

Wie heißt die Stack-Operation, die ein Element oben hinzufügt?

1. APush
2. BPop
3. CPeek
4. DEnqueue

Wie werden die Elemente eines Arrays im Speicher abgelegt?

1. AVerstreut, über Zeiger verbunden
2. BIn einem zusammenhängenden Block, eins nach dem anderen
3. CIn einem Baum aus Speicherseiten
4. DAn zufälligen, per Hash gewählten Stellen

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

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

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

Ein Ringpuffer (Circular Buffer) wird häufig verwendet, um Folgendes zu implementieren:

1. AEinen binären Suchbaum
2. BEine Graphtraversierung
3. CEine Warteschlange fester Größe
4. DEine Hashfunktion

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. BSie speichert Schlüssel ungeordnet
3. CSie benötigt keinen zusätzlichen Speicher
4. DErwartete Suche in O(log n) durch mehrere Ebenen von Vorwärtszeigern

Welches Paar von Traversierungen bestimmt immer einen eindeutigen Binärbaum mit verschiedenen Schlüsseln?

1. APre-Order allein
2. BLevel-Order allein
3. CPre-Order und In-Order
4. DPre-Order und Post-Order