Arbeitsblatt Datenstrukturen mit Lösungen

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

1. ALesen des letzten Elements per Index
2. BZugriff auf das 5. Element
3. CEinfügen am Anfang
4. DBestimmen der Länge eines Arrays fester Größe

Was ist eine Deque (double-ended queue)?

1. AEine nach Priorität sortierte Queue
2. BEine Struktur, die Einfügen und Entfernen an beiden Enden erlaubt
3. CEine Queue, die nur hinten das Entfernen erlaubt
4. DZwei getrennte Queues, die sich ein Array teilen

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

1. AHashtabelle
2. BStack
3. CQueue
4. DPrioritätswarteschlange

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. A4 2 5 1 3
2. B1 2 4 5 3
3. C5 4 3 2 1
4. D4 5 2 3 1

Wie funktioniert extract-min in einem binären Min-Heap?

1. ADas letzte Element des Arrays entfernen
2. BDie Wurzel entfernen und alle Elemente um eine Stelle nach links verschieben
3. CDas letzte Element in die Wurzel verschieben und nach unten wandern lassen
4. DAlle Blätter nach dem neuen Minimum durchsuchen

Wie lange dauert es, mit einer Adjazenzmatrix zu prüfen, ob die Kante (u, v) existiert?

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

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

1. APre-Order allein
2. BPre-Order und Post-Order
3. CLevel-Order allein
4. DPre-Order und In-Order

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