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 macht eine Hashfunktion in einer Hashtabelle?

  1. ASie bildet einen Schlüssel auf einen Index in der Tabelle ab
  2. BSie verschlüsselt die Werte in der Tabelle
  3. CSie sortiert die Schlüssel in der Tabelle
  4. DSie zählt, wie viele Schlüssel gespeichert sind
2.Leicht

In welcher Reihenfolge besucht eine Post-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. DRechter Teilbaum, dann Knoten, dann linker Teilbaum
3.Leicht

Ein Graph besteht aus:

  1. ANur einer Wurzel und Blättern
  2. BKnoten (Ecken), die durch Kanten verbunden sind
  3. CNur Schlüsseln und Hashwerten
  4. DZeilen und Spalten
4.Mittel

Was ist der größtmögliche Füllgrad einer Hashtabelle mit offener Adressierung?

  1. A2
  2. B0,5
  3. C1
  4. DEs gibt kein Maximum
5.Mittel

Eine Anwendung braucht schnelle Suchen, muss aber auch Schlüssel sortiert auflisten und Bereichsabfragen beantworten. Welche Struktur passt am besten?

  1. AEin balancierter binärer Suchbaum
  2. BEine Hashtabelle
  3. CEine unsortierte verkettete Liste
  4. DEin Stack
6.Mittel

Wie lange dauert die Suche nach einem Wort der Länge L in einem Trie mit festem Alphabet?

  1. AO(L), unabhängig davon, wie viele Wörter gespeichert sind
  2. BO(n), wobei n die Anzahl der Wörter ist
  3. CO(L × n)
  4. DO(log n), wobei n die Anzahl der Wörter ist
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

Das Löschen eines Knotens mit zwei Kindknoten aus einem binären Suchbaum erfolgt üblicherweise durch:

  1. AEntfernen des gesamten Teilbaums
  2. BVertauschen mit der Wurzel
  3. CErsetzen durch seinen In-Order-Nachfolger (oder -Vorgänger) und Löschen dieses Knotens
  4. DDen darunterliegenden Teilbaum von Grund auf neu aufbauen und jeden darin enthaltenen Schlüssel erneut einfügen

Lösungsschlüssel

  1. 1. A · Sie bildet einen Schlüssel auf einen Index in der Tabelle ab
  2. 2. B · Linker Teilbaum, dann rechter Teilbaum, dann Knoten
  3. 3. B · Knoten (Ecken), die durch Kanten verbunden sind
  4. 4. C · 1
  5. 5. A · Ein balancierter binärer Suchbaum
  6. 6. A · O(L), unabhängig davon, wie viele Wörter gespeichert sind
  7. 7. D · Eine einfache Rechtsrotation am unbalancierten Knoten
  8. 8. C · Ersetzen durch seinen In-Order-Nachfolger (oder -Vorgänger) und Löschen dieses Knotens

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