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 ist ein gerichteter Graph?

  1. AEin Graph, der keine Zyklen hat
  2. BEin Graph, in dem je zwei verschiedene Knoten durch eine Kante verbunden sind
  3. CEin Graph, dessen Kanten alle Gewichte haben
  4. DEin Graph, dessen Kanten eine Richtung von einem Knoten zu einem anderen haben
2.Leicht

Was ist ein Blatt in einem Baum?

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

Was ist in einem ungerichteten Graphen der Grad eines Knotens?

  1. ADie Anzahl der mit ihm verbundenen Kanten
  2. BDie Länge des längsten Pfades, der von ihm ausgeht
  3. CDie Anzahl der Knoten im Graphen
  4. DSeine Position in der Adjazenzliste
4.Mittel

In einem binären Min-Heap, der in einem Array gespeichert ist (Index beginnt bei 0), liegen die Kinder des Knotens mit Index i bei:

  1. Ai/2 und i/2 + 1
  2. B2i und 2i + 1
  3. Ci + 1 und i + 2
  4. D2i + 1 und 2i + 2
5.Mittel

Wie viel Speicher benötigt eine Adjazenzliste für einen Graphen mit V Knoten und E Kanten?

  1. AO(V × E)
  2. BO(E²)
  3. CO(V + E)
  4. DO(V²)
6.Mittel

Bei welchem Verfahren zur Kollisionsauflösung werden kollidierende Schlüssel in einer Liste im selben Bucket gespeichert?

  1. AVerkettung (Separate Chaining)
  2. BDoppeltes Hashing (Double Hashing)
  3. CQuadratisches Sondieren (Quadratic Probing)
  4. DLineares Sondieren (Linear Probing)
7.Schwer

Im BST mit Wurzel 50, linkem Teilbaum 30 (Kinder 20, 40) und rechtem Teilbaum 70 (Kinder 60, 80) wird die Wurzel mithilfe des In-Order-Nachfolgers gelöscht. Welcher Schlüssel wird die neue Wurzel?

  1. A70
  2. B80
  3. C60
  4. D40
8.Schwer

Welche Eigenschaft muss ein Rot-Schwarz-Baum erfüllen?

  1. AJeder Pfad von einem Knoten zu seinen Nachfahren-Blättern enthält gleich viele schwarze Knoten
  2. BRote Knoten müssen rote Kindknoten haben, sodass rote Knoten immer ununterbrochene Ketten bis zu den Blättern bilden
  3. CDie Wurzel muss rot sein
  4. DJeder Knoten muss rot sein

Lösungsschlüssel

  1. 1. D · Ein Graph, dessen Kanten eine Richtung von einem Knoten zu einem anderen haben
  2. 2. A · Ein Knoten ohne Kindknoten
  3. 3. A · Die Anzahl der mit ihm verbundenen Kanten
  4. 4. D · 2i + 1 und 2i + 2
  5. 5. C · O(V + E)
  6. 6. A · Verkettung (Separate Chaining)
  7. 7. C · 60
  8. 8. A · Jeder Pfad von einem Knoten zu seinen Nachfahren-Blättern enthält gleich viele schwarze Knoten

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