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

In einem binären Suchbaum sind die Werte im linken Teilbaum eines Knotens:

  1. AGrößer als der Wert des Knotens
  2. BGleich dem Wert des Knotens
  3. CKleiner als der Wert des Knotens
  4. DIn zufälliger Reihenfolge
2.Leicht

Was enthält in einer einfach verketteten Liste der next-Zeiger des letzten Knotens?

  1. ANull (keinen Knoten)
  2. BDie Adresse des ersten Knotens
  3. CDie Anzahl der Knoten in der Liste
  4. DDie Adresse des vorherigen Knotens
3.Leicht

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

  1. ALinker Teilbaum, dann Knoten, dann rechter Teilbaum
  2. BEbene für Ebene von oben
  3. CKnoten, dann linker Teilbaum, dann rechter Teilbaum
  4. DLinker Teilbaum, dann rechter Teilbaum, dann Knoten
4.Mittel

Welche Datenstruktur nutzt ein laufendes Programm, um aktive Funktionsaufrufe und ihre lokalen Variablen zu verwalten?

  1. AEinen binären Suchbaum der Frames
  2. BEine Hashtabelle der Funktionen
  3. CDie Heap-Speicher-Queue
  4. DDen Aufrufstack (Call Stack)
5.Mittel

Ein Straßennetz hat 100,000 Kreuzungen, die jeweils mit etwa 4 anderen verbunden sind. Welche Darstellung ist am besten geeignet?

  1. AEin binärer Heap der Kanten
  2. BAdjazenzmatrix
  3. CEin einziges sortiertes Array der Knoten
  4. DAdjazenzliste
6.Mittel

Eine Queue wird mit zwei Stacks implementiert: push auf einen „in“-Stack und pop von einem „out“-Stack, der aus „in“ nachgefüllt wird, wenn er leer ist. Wie hoch sind die amortisierten Kosten pro Operation?

  1. AO(n)
  2. BO(n²)
  3. CO(1)
  4. DO(log n)
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 einfache Rechtsrotation am Knoten
  2. BEine Rechtsrotation am linken Kind, dann eine Linksrotation am Knoten
  3. CEine Linksrotation am linken Kind, dann eine Rechtsrotation am Knoten
  4. DEine einfache Linksrotation am Knoten
8.Schwer

Was macht ein Splay-Baum nach jedem Zugriff?

  1. AEr rotiert den zugegriffenen Knoten bis zur Wurzel hoch
  2. BEr verschiebt den zugegriffenen Knoten zu einem Blatt
  3. CEr baut den ganzen Baum in balancierter Form neu auf
  4. DEr färbt die Knoten auf dem Suchpfad um

Lösungsschlüssel

  1. 1. C · Kleiner als der Wert des Knotens
  2. 2. A · Null (keinen Knoten)
  3. 3. C · Knoten, dann linker Teilbaum, dann rechter Teilbaum
  4. 4. D · Den Aufrufstack (Call Stack)
  5. 5. D · Adjazenzliste
  6. 6. C · O(1)
  7. 7. C · Eine Linksrotation am linken Kind, dann eine Rechtsrotation am Knoten
  8. 8. A · Er rotiert den zugegriffenen Knoten bis zur Wurzel hoch

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