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 Hauptunterschied zwischen einem statischen und einem dynamischen Array?

  1. AEin dynamisches Array kann wachsen, indem es in einen größeren Speicherblock umzieht
  2. BEin statisches Array erlaubt einen langsameren Indexzugriff
  3. CEin dynamisches Array speichert seine Elemente in verketteten Knoten, damit es einzeln wachsen kann
  4. DEin statisches Array kann nur Zahlen speichern
2.Leicht

In einem binären Suchbaum sind die Werte im linken Teilbaum eines Knotens:

  1. AKleiner als der Wert des Knotens
  2. BGleich dem Wert des Knotens
  3. CIn zufälliger Reihenfolge
  4. DGrößer als der Wert des Knotens
3.Leicht

Was ist das kennzeichnende Merkmal einer Menge (Set) als abstrakter Datentyp?

  1. ASie speichert Schlüssel-Wert-Paare
  2. BSie speichert Elemente ohne Duplikate
  3. CSie erlaubt nur an einem Ende Zugriff
  4. DSie speichert Elemente in sortierter Reihenfolge
4.Mittel

Eine Queue wird mit zwei Stacks implementiert: push auf einen „in“-Stack und pop von einem „out“-Stack, der aus „in“ nachgefüllt wird, wenn er leer ist. Wie hoch sind die amortisierten Kosten pro Operation?

  1. AO(n²)
  2. BO(1)
  3. CO(log n)
  4. DO(n)
5.Mittel

Mit welcher Datenstruktur prüft man, ob die Klammern in "{[()]}" ausgeglichen sind?

  1. AMit einer Hashtabelle
  2. BMit einem binären Suchbaum
  3. CMit einem Stack
  4. DMit einer Queue
6.Mittel

Ein Trie (Präfixbaum) ist besonders effizient für:

  1. ADas Finden kürzester Wege
  2. BDas Sortieren von Zahlen
  3. CPräfixsuchen wie Autovervollständigung
  4. DDas Speichern von Matrizen
7.Schwer

Du musst aus einem Strom von n Zahlen die k kleinsten Werte mit O(k) Speicher behalten. Welcher Ansatz schafft das in O(n log k) Zeit?

  1. AEine FIFO-Queue der letzten k Werte
  2. BEin Min-Heap mit allen n Werten, aus dem am Ende die k kleinsten entnommen werden
  3. CEin Max-Heap der Größe k, dessen Wurzel ersetzt wird, wenn ein kleinerer Wert ankommt
  4. DEin sortiertes Array aller n Werte
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, 3, 8, 5]
  2. B[3, 1, 8, 5]
  3. C[1, 3, 5, 8]
  4. D[1, 5, 8, 3]

Lösungsschlüssel

  1. 1. A · Ein dynamisches Array kann wachsen, indem es in einen größeren Speicherblock umzieht
  2. 2. A · Kleiner als der Wert des Knotens
  3. 3. B · Sie speichert Elemente ohne Duplikate
  4. 4. B · O(1)
  5. 5. C · Mit einem Stack
  6. 6. C · Präfixsuchen wie Autovervollständigung
  7. 7. C · Ein Max-Heap der Größe k, dessen Wurzel ersetzt wird, wenn ein kleinerer Wert ankommt
  8. 8. A · [1, 3, 8, 5]

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