Arbeitsblatt Datenstrukturen mit Lösungen

Kostenloses Arbeitsblatt Datenstrukturen zum Ausdrucken: 8 Aufgaben von leicht bis Prüfungsniveau, mit Lösungsschlüssel. Drucke es aus oder speichere es als PDF.

Neues ArbeitsblattOnline mit Tipps üben

Für Lehrkräfte: kostenlos ausdrucken, kopieren und im Unterricht verwenden. Jedes neue Arbeitsblatt hat neue Werte und einen eigenen Lösungsschlüssel. Über einen Link zu ExamProblems auf Ihrer Kursseite freuen wir uns.

Name: ____________________   Datum: ____________

1.Leicht

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

  1. AWarteschlange (Queue)
  2. BHash-Set
  3. CGraph
  4. DStapel (Stack)
2.Leicht

Was speichert eine Map (Dictionary)?

  1. ANur Werte in Einfügereihenfolge
  2. BSchlüssel-Wert-Paare mit eindeutigen Schlüsseln
  3. CPaare gleicher Schlüssel
  4. DNach Größe sortierte Werte
3.Leicht

In einer einfach verketteten Liste enthält jeder Knoten:

  1. ADaten und Referenzen auf alle anderen Knoten
  2. BDaten und eine Referenz auf den nächsten Knoten
  3. CDaten und einen Index
  4. DNur Daten
4.Mittel

Eine Hashtabelle der Größe 7 verwendet h(k) = k mod 7 und lineares Sondieren. Wo wird 17 gespeichert, nachdem 10 eingefügt wurde?

  1. AIndex 0
  2. BIndex 6
  3. CIndex 3
  4. DIndex 4
5.Mittel

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. Alog₂ n
  2. Bn (er wird zu einer verketteten Liste)
  3. C1
  4. D√n
6.Mittel

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

Das Löschen eines Knotens mit zwei Kindknoten aus einem binären Suchbaum erfolgt üblicherweise durch:

  1. AVertauschen mit der Wurzel
  2. BDen darunterliegenden Teilbaum von Grund auf neu aufbauen und jeden darin enthaltenen Schlüssel erneut einfügen
  3. CErsetzen durch seinen In-Order-Nachfolger (oder -Vorgänger) und Löschen dieses Knotens
  4. DEntfernen des gesamten Teilbaums
8.Schwer

Wie hoch ist unter der Annahme des einfachen gleichverteilten Hashings die erwartete Suchzeit in einer Hashtabelle mit Chaining, n Schlüsseln und m Buckets?

  1. AO(1 + α), wobei α = n / m
  2. BO(n)
  3. CO(m)
  4. DO(log n)

Lösungsschlüssel

  1. 1. D · Stapel (Stack)
  2. 2. B · Schlüssel-Wert-Paare mit eindeutigen Schlüsseln
  3. 3. B · Daten und eine Referenz auf den nächsten Knoten
  4. 4. D · Index 4
  5. 5. B · n (er wird zu einer verketteten Liste)
  6. 6. C · 4 5 2 3 1
  7. 7. C · Ersetzen durch seinen In-Order-Nachfolger (oder -Vorgänger) und Löschen dieses Knotens
  8. 8. A · O(1 + α), wobei α = n / m

Vollständige Schritt-für-Schritt-Lösungen: Übe dieses Thema auf examproblems.com.