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 einer einfach verketteten Liste enthält jeder Knoten:

  1. ADaten und eine Referenz auf den nächsten Knoten
  2. BDaten und einen Index
  3. CNur Daten
  4. DDaten und Referenzen auf alle anderen Knoten
2.Leicht

Wo befindet sich das kleinste Element eines binären Min-Heaps?

  1. AIn irgendeinem Blatt, das gesucht werden muss
  2. BIn der Wurzel
  3. CIm linkesten Blatt
  4. DAn der letzten Array-Position
3.Leicht

Wie heißt die Queue-Operation, die das Element vorne entfernt?

  1. AEnqueue
  2. BInsert
  3. CDequeue
  4. DPush
4.Mittel

Was kostet das Einfügen eines Elements in der Mitte eines Arrays mit n Elementen?

  1. AO(n), weil die nachfolgenden Elemente verschoben werden müssen
  2. BO(log n), wegen der binären Suche
  3. CO(1), weil der Index bekannt ist
  4. DO(n²), weil jedes Element n-mal verschoben wird
5.Mittel

Warum kann ein binärer Heap ganz ohne Zeiger in einem Array gespeichert werden?

  1. AAlle Schlüssel in einem Heap sind gleich
  2. BArrays halten Schlüssel automatisch sortiert, sodass keine Zeiger nötig sind
  3. CEr ist ein vollständiger Binärbaum, daher folgen die Positionen einfachen Indexformeln
  4. DHeaps enthalten nie mehr als 100 Elemente
6.Mittel

Wie funktioniert extract-min in einem binären Min-Heap?

  1. AAlle Blätter nach dem neuen Minimum durchsuchen
  2. BDas letzte Element in die Wurzel verschieben und nach unten wandern lassen
  3. CDie Wurzel entfernen und alle Elemente um eine Stelle nach links verschieben
  4. DDas letzte Element des Arrays entfernen
7.Schwer

Ein Bloom-Filter kann die Frage „Ist dieses Element in der Menge?“ beantworten mit:

  1. AMöglichen falsch-positiven, aber keinen falsch-negativen Ergebnissen
  2. BAntworten nur für Zahlen
  3. CMöglichen falsch-negativen, aber keinen falsch-positiven Ergebnissen
  4. DImmer exakten Antworten
8.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. A80
  2. B60
  3. C70
  4. D40

Lösungsschlüssel

  1. 1. A · Daten und eine Referenz auf den nächsten Knoten
  2. 2. B · In der Wurzel
  3. 3. C · Dequeue
  4. 4. A · O(n), weil die nachfolgenden Elemente verschoben werden müssen
  5. 5. C · Er ist ein vollständiger Binärbaum, daher folgen die Positionen einfachen Indexformeln
  6. 6. B · Das letzte Element in die Wurzel verschieben und nach unten wandern lassen
  7. 7. A · Möglichen falsch-positiven, aber keinen falsch-negativen Ergebnissen
  8. 8. B · 60

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