Arbeitsblatt Datenstrukturen mit Lösungen

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

1. AStack
2. BQueue
3. CPrioritätswarteschlange
4. DHashtabelle

Was ist ein Blatt in einem Baum?

1. AEin Knoten mit genau einem Kindknoten
2. BDer Knoten mit dem größten Wert
3. CEin Knoten ohne Elternknoten
4. DEin Knoten ohne Kindknoten

Was speichert eine Map (Dictionary)?

1. ANur Werte in Einfügereihenfolge
2. BNach Größe sortierte Werte
3. CSchlüssel-Wert-Paare mit eindeutigen Schlüsseln
4. DPaare gleicher Schlüssel

Wie viele Knoten hat ein perfekter Binärbaum der Höhe h, wenn die Höhe in Kanten gezählt wird?

1. A2h + 1
2. B2^h
3. Ch²
4. D2^h+1 − 1

Wie groß ist die Höhe eines binären Suchbaums mit n Knoten im schlechtesten Fall, wenn die Schlüssel in sortierter Reihenfolge eingefügt werden?

1. An (er wird zu einer verketteten Liste)
2. B1
3. C√n
4. Dlog₂ n

Wie findest du den kleinsten Schlüssel in einem binären Suchbaum?

1. AVon der Wurzel aus den linken Kindern folgen, bis es kein linkes Kind mehr gibt
2. BJedes Blatt besuchen und vergleichen
3. CVon der Wurzel aus den rechten Kindern folgen, bis es kein rechtes Kind mehr gibt
4. DNur die Wurzel ansehen

Welche Laufzeit hat die Breitensuche auf einem Graphen mit V Knoten, der als Adjazenzmatrix gespeichert ist?

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

Die Zeitkomplexität von decrease-key in einem binären Heap (bei bekannter Position des Elements) beträgt:

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