Arbeitsblatt Datenstrukturen mit Lösungen

Welche Datenstruktur eignet sich am besten für die „Rückgängig“-Funktion (Undo) in einem Texteditor?

1. AGraph
2. BWarteschlange (Queue)
3. CHash-Set
4. DStapel (Stack)

Die Tiefe eines Knotens in einem Baum ist:

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

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

1. ARechter Teilbaum, dann Knoten, dann linker Teilbaum
2. BLinker Teilbaum, dann Knoten, dann rechter Teilbaum
3. CKnoten, dann linker Teilbaum, dann rechter Teilbaum
4. DLinker Teilbaum, dann rechter Teilbaum, dann Knoten

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. Bi + 1
3. C(i − 1) mod n
4. D2i + 1

Ein Binärbaum hat die Wurzel 1 mit linkem Kind 2 und rechtem Kind 3; Knoten 2 hat die Kinder 4 (links) und 5 (rechts). Wie lautet die Post-Order-Traversierung?

1. A5 4 3 2 1
2. B4 2 5 1 3
3. C4 5 2 3 1
4. D1 2 4 5 3

Du hast eine Referenz auf einen Knoten in der Mitte einer Liste. In welcher Liste kannst du ihn in O(1) entfernen?

1. AIn einer doppelt verketteten Liste
2. BIn einem dynamischen Array
3. CIn einem sortierten Array
4. DIn einer einfach verketteten 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(log n)
2. BO(n)
3. CO(1)
4. DO(α(n))

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

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