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

Was sind Geschwisterknoten in einem Baum?

  1. AKnoten ohne Kindknoten
  2. BEin Knoten und sein Elternknoten
  3. CKnoten in gleicher Tiefe in verschiedenen Teilbäumen
  4. DKnoten mit demselben Elternknoten
2.Leicht

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

  1. ARechter Teilbaum, dann Knoten, dann linker Teilbaum
  2. BKnoten, dann linker Teilbaum, dann rechter Teilbaum
  3. CLinker Teilbaum, dann rechter Teilbaum, dann Knoten
  4. DLinker Teilbaum, dann Knoten, dann rechter Teilbaum
3.Leicht

Welche Datenstruktur arbeitet nach dem Prinzip „first in, first out“ (FIFO)?

  1. AStapel (Stack)
  2. BHeap
  3. CBinärbaum
  4. DWarteschlange (Queue)
4.Mittel

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 einfach verketteten Liste
  2. BIn einer doppelt verketteten Liste
  3. CIn einem dynamischen Array
  4. DIn einem sortierten Array
5.Mittel

Ein Trie (Präfixbaum) ist besonders effizient für:

  1. ADas Finden kürzester Wege
  2. BPräfixsuchen wie Autovervollständigung
  3. CDas Sortieren von Zahlen
  4. DDas Speichern von Matrizen
6.Mittel

Wozu dient ein Sentinel-Knoten (Dummy-Knoten) in einer verketteten Liste?

  1. AEr hält die Liste sortiert
  2. BEr speichert die Anzahl der Elemente
  3. CEr vereinfacht den Code, weil Sonderfälle am Kopf oder Ende wegfallen
  4. DUm zu verhindern, dass die Liste über eine feste Höchstzahl von Knoten hinauswächst
7.Schwer

Ein AVL-Knoten ist unbalanciert, weil der rechte Teilbaum seines linken Kindes zu hoch wurde (Links-rechts-Fall). Welche Korrektur wird angewendet?

  1. AEine Linksrotation am linken Kind, dann eine Rechtsrotation am Knoten
  2. BEine einfache Rechtsrotation am Knoten
  3. CEine Rechtsrotation am linken Kind, dann eine Linksrotation am Knoten
  4. DEine einfache Linksrotation am Knoten
8.Schwer

Warum wird in einer Hashtabelle mit offener Adressierung beim Löschen oft eine „Tombstone“-Markierung verwendet?

  1. AGelöschte Schlüssel müssen aus Sicherheitsgründen für immer aufbewahrt werden, sodass Plätze nie wiederverwendet werden können
  2. BDas Leeren des Platzes könnte die Sondierungsfolge für andere Schlüssel unterbrechen
  3. CTombstones beschleunigen das Hashing
  4. DDadurch wird die Tabelle sortiert

Lösungsschlüssel

  1. 1. D · Knoten mit demselben Elternknoten
  2. 2. C · Linker Teilbaum, dann rechter Teilbaum, dann Knoten
  3. 3. D · Warteschlange (Queue)
  4. 4. B · In einer doppelt verketteten Liste
  5. 5. B · Präfixsuchen wie Autovervollständigung
  6. 6. C · Er vereinfacht den Code, weil Sonderfälle am Kopf oder Ende wegfallen
  7. 7. A · Eine Linksrotation am linken Kind, dann eine Rechtsrotation am Knoten
  8. 8. B · Das Leeren des Platzes könnte die Sondierungsfolge für andere Schlüssel unterbrechen

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