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

Was kennzeichnet einen Binärbaum?

  1. ADer Baum hat genau zwei Ebenen
  2. BJeder Knoten speichert eine Binärzahl
  3. CJeder Knoten hat höchstens zwei Kindknoten
  4. DJeder Knoten hat genau zwei Kindknoten
3.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 mit mehr Kanten als Knoten
  4. DEin Graph, der auf der Festplatte gespeichert ist
4.Mittel

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

  1. ADas Finden kürzester Wege
  2. BDas Sortieren von Zahlen
  3. CDas Speichern von Matrizen
  4. DPräfixsuchen wie Autovervollständigung
5.Mittel

Wo liegt in einem binären Heap, der in einem Array ab Index 0 gespeichert ist, der Elternknoten des Knotens mit Index i?

  1. ABei Index ⌊(i − 1) / 2⌋
  2. BBei Index 2i + 1
  3. CBei Index i − 1
  4. DBei Index ⌊i / 2⌋ + 1
6.Mittel

Bei welchem Verfahren zur Kollisionsauflösung werden kollidierende Schlüssel in einer Liste im selben Bucket gespeichert?

  1. AQuadratisches Sondieren (Quadratic Probing)
  2. BVerkettung (Separate Chaining)
  3. CLineares Sondieren (Linear Probing)
  4. DDoppeltes Hashing (Double Hashing)
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 Linksrotation am unbalancierten Knoten
  2. BEine Linksrotation am Kind, dann eine Rechtsrotation am Knoten
  3. CUmfärben des Knotens und seines Kindes
  4. DEine einfache Rechtsrotation am unbalancierten Knoten
8.Schwer

Welche Garantie geben die Regeln eines Rot-Schwarz-Baums für die Höhe eines Baums mit n Schlüsseln?

  1. ADie Höhe beträgt höchstens n / 2
  2. BDie Höhe beträgt genau log2 n
  3. CDie Höhe beträgt höchstens log2 n + 1
  4. DDie Höhe beträgt höchstens 2 log2(n + 1)

Lösungsschlüssel

  1. 1. C · Die Anzahl gespeicherter Elemente geteilt durch die Anzahl der Buckets
  2. 2. C · Jeder Knoten hat höchstens zwei Kindknoten
  3. 3. B · Ein Graph, in dem jede Kante einen Zahlenwert wie Kosten oder Entfernung hat
  4. 4. D · Präfixsuchen wie Autovervollständigung
  5. 5. A · Bei Index ⌊(i − 1) / 2⌋
  6. 6. B · Verkettung (Separate Chaining)
  7. 7. D · Eine einfache Rechtsrotation am unbalancierten Knoten
  8. 8. D · Die Höhe beträgt höchstens 2 log2(n + 1)

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