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 ein gerichteter Graph?

  1. AEin Graph, dessen Kanten alle Gewichte haben
  2. BEin Graph, der keine Zyklen hat
  3. CEin Graph, dessen Kanten eine Richtung von einem Knoten zu einem anderen haben
  4. DEin Graph, in dem je zwei verschiedene Knoten durch eine Kante verbunden sind
2.Leicht

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

  1. AKnoten, dann linker Teilbaum, dann rechter Teilbaum
  2. BLinker Teilbaum, dann Knoten, dann rechter Teilbaum
  3. CRechter Teilbaum, dann Knoten, dann linker Teilbaum
  4. DLinker Teilbaum, dann rechter Teilbaum, dann Knoten
3.Leicht

Was ist ein Zyklus in einem Graphen?

  1. AEine Kante mit dem Gewicht null
  2. BEin Pfad, der am selben Knoten beginnt und endet
  3. CEin Knoten ohne Kanten
  4. DEin Pfad, der jeden Knoten besucht
4.Mittel

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

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

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

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

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

  1. AEinen Stack
  2. BEine Queue
  3. CNur eine Hashtabelle
  4. DEinen Heap
7.Schwer

Wie verbessert ein Radix-Baum (komprimierter Trie) einen einfachen Trie?

  1. AEr sortiert die Kinder jedes Knotens nach Häufigkeit
  2. BEr fasst Ketten von Knoten mit nur einem Kind zu einer mit einer Zeichenkette beschrifteten Kante zusammen
  3. CEr behält nur den ersten Buchstaben jedes Worts
  4. DEr speichert jedes Wort in einer Hashtabelle an der Wurzel statt in einzelnen Knoten
8.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. BUmfärben des Knotens und seines Kindes
  3. CEine einfache Linksrotation am unbalancierten Knoten
  4. DEine Linksrotation am Kind, dann eine Rechtsrotation am Knoten

Lösungsschlüssel

  1. 1. C · Ein Graph, dessen Kanten eine Richtung von einem Knoten zu einem anderen haben
  2. 2. D · Linker Teilbaum, dann rechter Teilbaum, dann Knoten
  3. 3. B · Ein Pfad, der am selben Knoten beginnt und endet
  4. 4. A · Ans Ende des Arrays setzen und nach oben wandern lassen (sift-up), solange es die Heap-Eigenschaft verletzt
  5. 5. C · Ein balancierter binärer Suchbaum
  6. 6. A · Einen Stack
  7. 7. B · Er fasst Ketten von Knoten mit nur einem Kind zu einer mit einer Zeichenkette beschrifteten Kante zusammen
  8. 8. A · Eine einfache Rechtsrotation am unbalancierten Knoten

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