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

Wie werden die Elemente eines Arrays im Speicher abgelegt?

  1. AVerstreut, über Zeiger verbunden
  2. BIn einem Baum aus Speicherseiten
  3. CIn einem zusammenhängenden Block, eins nach dem anderen
  4. DAn zufälligen, per Hash gewählten Stellen
2.Leicht

Welche Operation kostet bei einem Array O(1), bei einer einfach verketteten Liste aber O(n)?

  1. ALesen des ersten Elements
  2. BEinfügen am Kopf
  3. CEntfernen des Kopfelements
  4. DZugriff auf das Element an Index i
3.Leicht

Was wird bei der Darstellung eines Graphen als Adjazenzliste für jeden Knoten gespeichert?

  1. AEine Liste seiner Nachbarknoten
  2. BDie Gesamtzahl der Kanten im Graphen
  3. CEine Zeile aus V booleschen Werten
  4. DDer kürzeste Weg zu jedem anderen Knoten
4.Mittel

Welche Datenstruktur verwendet die Tiefensuche (DFS) in der iterativen Variante?

  1. AEinen Stack
  2. BEine Queue
  3. CNur eine Hashtabelle
  4. DEinen Heap
5.Mittel

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

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

Was gilt für die Adjazenzmatrix eines ungerichteten Graphen?

  1. AIhre Hauptdiagonale enthält immer Einsen
  2. BSie ist immer eine obere Dreiecksmatrix
  3. CJede Zeile hat genau eine 1
  4. DSie ist symmetrisch zur Hauptdiagonale
7.Schwer

Ein Segmentbaum (Segment Tree) wird typischerweise verwendet, um:

  1. ADie Kanten eines Graphen zu speichern
  2. BBereichsabfragen (z. B. Bereichssummen) und Aktualisierungen in O(log n) zu beantworten
  3. CZeichenketten alphabetisch zu sortieren, indem jedes Präfix in einem eigenen Baumknoten gespeichert wird
  4. DEinen Stack zu implementieren
8.Schwer

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

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

Lösungsschlüssel

  1. 1. C · In einem zusammenhängenden Block, eins nach dem anderen
  2. 2. D · Zugriff auf das Element an Index i
  3. 3. A · Eine Liste seiner Nachbarknoten
  4. 4. A · Einen Stack
  5. 5. A · Er vereinfacht den Code, weil Sonderfälle am Kopf oder Ende wegfallen
  6. 6. D · Sie ist symmetrisch zur Hauptdiagonale
  7. 7. B · Bereichsabfragen (z. B. Bereichssummen) und Aktualisierungen in O(log n) zu beantworten
  8. 8. C · 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.