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 bisherigen Kollisionen
  2. BDie Zeit, um die Tabelle von der Festplatte zu laden
  3. CDie Anzahl der Buckets geteilt durch die durchschnittliche Länge der gespeicherten Schlüssel
  4. DDie Anzahl gespeicherter Elemente geteilt durch die Anzahl der Buckets
2.Leicht

In welcher Reihenfolge besucht eine Pre-Order-Traversierung eines Binärbaums die Knoten?

  1. ALinker Teilbaum, dann Knoten, dann rechter Teilbaum
  2. BLinker Teilbaum, dann rechter Teilbaum, dann Knoten
  3. CKnoten, dann linker Teilbaum, dann rechter Teilbaum
  4. DEbene für Ebene von oben
3.Leicht

Was ist die Max-Heap-Eigenschaft?

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

Wie wird ein neues Element in einen binären Heap eingefügt?

  1. AIn die Wurzel setzen und nach unten wandern lassen
  2. BAns Ende des Arrays setzen und nach oben wandern lassen (sift-up), solange es die Heap-Eigenschaft verletzt
  3. CAn der sortierten Position einfügen, indem alle größeren Elemente um eine Stelle nach rechts verschoben werden
  4. DDen ganzen Heap von Grund auf neu aufbauen
5.Mittel

Welche Datenstruktur verwendet die Tiefensuche (DFS) in der iterativen Variante?

  1. ANur eine Hashtabelle
  2. BEinen Stack
  3. CEine Queue
  4. DEinen Heap
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. BEr speichert die Anzahl der Elemente
  3. CEr hält die Liste sortiert
  4. DUm zu verhindern, dass die Liste über eine feste Höchstzahl von Knoten hinauswächst
7.Schwer

Durch das Einfügen eines Schlüssels in einen AVL-Baum wird der linke Teilbaum eines Knotens zu hoch, und der neue Schlüssel landete im linken Teilbaum seines linken Kindes (Links-links-Fall). Welche Korrektur wird angewendet?

  1. AEine einfache Rechtsrotation am unbalancierten Knoten
  2. BEine einfache Linksrotation am unbalancierten Knoten
  3. CUmfärben des Knotens und seines Kindes
  4. DEine Linksrotation am Kind, dann eine Rechtsrotation am Knoten
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. BDie Knoten zählen, bis die Zahl das Längenfeld der Liste übersteigt
  3. CDie Liste sortieren und nach Duplikaten suchen
  4. DJeden besuchten Knoten in einem Hash-Set speichern

Lösungsschlüssel

  1. 1. D · Die Anzahl gespeicherter Elemente geteilt durch die Anzahl der Buckets
  2. 2. C · Knoten, dann linker Teilbaum, dann rechter Teilbaum
  3. 3. C · Der Schlüssel jedes Elternknotens ist größer oder gleich den Schlüsseln seiner Kinder
  4. 4. B · Ans Ende des Arrays setzen und nach oben wandern lassen (sift-up), solange es die Heap-Eigenschaft verletzt
  5. 5. B · Einen Stack
  6. 6. A · Er vereinfacht den Code, weil Sonderfälle am Kopf oder Ende wegfallen
  7. 7. A · Eine einfache Rechtsrotation am unbalancierten Knoten
  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.