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 die Max-Heap-Eigenschaft?

  1. ADie Schlüssel sind von links nach rechts sortiert
  2. BDer Schlüssel jedes linken Kindes ist größer oder gleich dem Schlüssel seines rechten Geschwisterknotens
  3. CAlle Blätter enthalten den maximalen Schlüssel
  4. DDer Schlüssel jedes Elternknotens ist größer oder gleich den Schlüsseln seiner Kinder
2.Leicht

Was kennzeichnet einen Binärbaum?

  1. AJeder Knoten hat genau zwei Kindknoten
  2. BDer Baum hat genau zwei Ebenen
  3. CJeder Knoten hat höchstens zwei Kindknoten
  4. DJeder Knoten speichert eine Binärzahl
3.Leicht

Was ist eine Kollision in einer Hashtabelle?

  1. AZwei gleiche Schlüssel werden doppelt gespeichert
  2. BDer Tabelle geht der Speicher aus
  3. CZwei verschiedene Schlüssel werden auf denselben Index abgebildet
  4. DEin Schlüssel lässt sich überhaupt nicht hashen
4.Mittel

Ein Knoten in einem binären Suchbaum hat einen rechten Teilbaum. Wo liegt sein In-Order-Nachfolger?

  1. AImmer bei seinem rechten Kind
  2. BImmer bei seinem Elternknoten
  3. CAm rechtesten Knoten seines linken Teilbaums
  4. DAm linkesten Knoten seines rechten Teilbaums
5.Mittel

Eine Anwendung braucht schnelle Suchen, muss aber auch Schlüssel sortiert auflisten und Bereichsabfragen beantworten. Welche Struktur passt am besten?

  1. AEin balancierter binärer Suchbaum
  2. BEine Hashtabelle
  3. CEin Stack
  4. DEine unsortierte verkettete Liste
6.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
7.Schwer

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

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

Wie kannst du mit O(1) zusätzlichem Speicher erkennen, ob eine einfach verkettete Liste einen Zyklus enthält?

  1. AEinen Zeiger um einen Schritt und einen anderen um zwei Schritte bewegen und prüfen, ob sie sich treffen
  2. BJeden besuchten Knoten in einem Hash-Set speichern
  3. CDie Liste sortieren und nach Duplikaten suchen
  4. DDie Knoten zählen, bis die Zahl das Längenfeld der Liste übersteigt

Lösungsschlüssel

  1. 1. D · Der Schlüssel jedes Elternknotens ist größer oder gleich den Schlüsseln seiner Kinder
  2. 2. C · Jeder Knoten hat höchstens zwei Kindknoten
  3. 3. C · Zwei verschiedene Schlüssel werden auf denselben Index abgebildet
  4. 4. D · Am linkesten Knoten seines rechten Teilbaums
  5. 5. A · Ein balancierter binärer Suchbaum
  6. 6. A · Er vereinfacht den Code, weil Sonderfälle am Kopf oder Ende wegfallen
  7. 7. C · Bereichsabfragen (z. B. Bereichssummen) und Aktualisierungen in O(log n) zu beantworten
  8. 8. A · Einen Zeiger um einen Schritt und einen anderen um zwei Schritte bewegen und prüfen, ob sie sich treffen

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