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 der Füllgrad (Load Factor) einer Hashtabelle?

  1. ADie Anzahl der Buckets geteilt durch die durchschnittliche Länge der gespeicherten Schlüssel
  2. BDie Zeit, um die Tabelle von der Festplatte zu laden
  3. CDie Anzahl der bisherigen Kollisionen
  4. DDie Anzahl gespeicherter Elemente geteilt durch die Anzahl der Buckets
2.Leicht

Welche Struktur wird typischerweise zur Implementierung einer Prioritätswarteschlange verwendet?

  1. AEin Stack
  2. BEin Heap
  3. CEine ungeordnete einfach verkettete Liste
  4. DEine Zeichenkette
3.Leicht

Was kennzeichnet einen Binärbaum?

  1. AJeder Knoten hat genau zwei Kindknoten
  2. BJeder Knoten hat höchstens zwei Kindknoten
  3. CDer Baum hat genau zwei Ebenen
  4. DJeder Knoten speichert eine Binärzahl
4.Mittel

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

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

Du hast eine Referenz auf einen Knoten in der Mitte einer Liste. In welcher Liste kannst du ihn in O(1) entfernen?

  1. AIn einer einfach verketteten Liste
  2. BIn einer doppelt verketteten Liste
  3. CIn einem sortierten Array
  4. DIn einem dynamischen Array
6.Mittel

Warum ist das Durchlaufen eines Arrays in der Praxis oft viel schneller als das einer gleich langen verketteten Liste?

  1. ADas Durchlaufen eines Arrays ist insgesamt O(1), das einer verketteten Liste O(n)
  2. BArrays brauchen weniger Instruktionen zum Vergleichen von Werten
  3. CArray-Elemente liegen zusammenhängend und nutzen daher den CPU-Cache gut aus
  4. DVerkettete Listen speichern Elemente immer auf der Festplatte
7.Schwer

Wie hoch ist unter der Annahme des einfachen gleichverteilten Hashings die erwartete Suchzeit in einer Hashtabelle mit Chaining, n Schlüsseln und m Buckets?

  1. AO(log n)
  2. BO(m)
  3. CO(n)
  4. DO(1 + α), wobei α = n / m
8.Schwer

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

  1. AEinen Stack zu implementieren
  2. BDie Kanten eines Graphen zu speichern
  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

Lösungsschlüssel

  1. 1. D · Die Anzahl gespeicherter Elemente geteilt durch die Anzahl der Buckets
  2. 2. B · Ein Heap
  3. 3. B · Jeder Knoten hat höchstens zwei Kindknoten
  4. 4. C · O(n), weil die nachfolgenden Elemente verschoben werden müssen
  5. 5. B · In einer doppelt verketteten Liste
  6. 6. C · Array-Elemente liegen zusammenhängend und nutzen daher den CPU-Cache gut aus
  7. 7. D · O(1 + α), wobei α = n / m
  8. 8. C · Bereichsabfragen (z. B. Bereichssummen) und Aktualisierungen in O(log n) zu beantworten

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