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 Zyklus in einem Graphen?

  1. AEin Knoten ohne Kanten
  2. BEine Kante mit dem Gewicht null
  3. CEin Pfad, der am selben Knoten beginnt und endet
  4. DEin Pfad, der jeden Knoten besucht
2.Leicht

Was ist ein gewichteter Graph?

  1. AEin Graph, in dem manche Knoten schwerer sind als andere, weil sie mehr Kanten haben
  2. BEin Graph, in dem jede Kante einen Zahlenwert wie Kosten oder Entfernung hat
  3. CEin Graph, der auf der Festplatte gespeichert ist
  4. DEin Graph mit mehr Kanten als Knoten
3.Leicht

Die Höhe eines Baums wird üblicherweise definiert als:

  1. ADie Anzahl der Blätter im Baum
  2. BDie Gesamtzahl der Knoten im Baum, einschließlich der Wurzel und jedes Blatts
  3. CDie Anzahl der Kindknoten der Wurzel
  4. DDie Anzahl der Kanten auf dem längsten Pfad von der Wurzel zu einem Blatt
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 + 1 und i + 2
  2. B2i + 1 und 2i + 2
  3. Ci/2 und i/2 + 1
  4. D2i und 2i + 1
5.Mittel

Ein Binärbaum hat die Wurzel 1 mit linkem Kind 2 und rechtem Kind 3; Knoten 2 hat die Kinder 4 (links) und 5 (rechts). Wie lautet die Post-Order-Traversierung?

  1. A4 2 5 1 3
  2. B1 2 4 5 3
  3. C5 4 3 2 1
  4. D4 5 2 3 1
6.Mittel

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

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

Welche Operationen unterstützt ein Fenwick-Baum (Binary Indexed Tree) über einem Array von n Zahlen in O(log n)?

  1. ASortieren des Arrays und binäre Suche
  2. BEinfügen von Elementen an beliebiger Position
  3. CFinden des Medians in O(1)
  4. DPräfixsummen-Abfragen und Aktualisierungen einzelner Elemente
8.Schwer

Die Schlüssel 5, 3, 8, 1 werden in dieser Reihenfolge in einen leeren, arraybasierten binären Min-Heap eingefügt. Wie sieht das Array am Ende aus?

  1. A[1, 5, 8, 3]
  2. B[3, 1, 8, 5]
  3. C[1, 3, 8, 5]
  4. D[1, 3, 5, 8]

Lösungsschlüssel

  1. 1. C · Ein Pfad, der am selben Knoten beginnt und endet
  2. 2. B · Ein Graph, in dem jede Kante einen Zahlenwert wie Kosten oder Entfernung hat
  3. 3. D · Die Anzahl der Kanten auf dem längsten Pfad von der Wurzel zu einem Blatt
  4. 4. B · 2i + 1 und 2i + 2
  5. 5. D · 4 5 2 3 1
  6. 6. A · Das letzte Element in die Wurzel verschieben und nach unten wandern lassen
  7. 7. D · Präfixsummen-Abfragen und Aktualisierungen einzelner Elemente
  8. 8. C · [1, 3, 8, 5]

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