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 Blatt in einem Baum?

  1. AEin Knoten ohne Kindknoten
  2. BEin Knoten mit genau einem Kindknoten
  3. CEin Knoten ohne Elternknoten
  4. DDer Knoten mit dem größten Wert
2.Leicht

Was ist ein Zyklus in einem Graphen?

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

Welche Datenstruktur arbeitet nach dem Prinzip „first in, first out“ (FIFO)?

  1. AStapel (Stack)
  2. BBinärbaum
  3. CWarteschlange (Queue)
  4. DHeap
4.Mittel

Wie findest du den kleinsten Schlüssel in einem binären Suchbaum?

  1. AVon der Wurzel aus den linken Kindern folgen, bis es kein linkes Kind mehr gibt
  2. BNur die Wurzel ansehen
  3. CVon der Wurzel aus den rechten Kindern folgen, bis es kein rechtes Kind mehr gibt
  4. DJedes Blatt besuchen und vergleichen
5.Mittel

Ein Knoten in einem binären Suchbaum hat einen rechten Teilbaum. Wo liegt sein In-Order-Nachfolger?

  1. AAm linkesten Knoten seines rechten Teilbaums
  2. BImmer bei seinem Elternknoten
  3. CImmer bei seinem rechten Kind
  4. DAm rechtesten Knoten seines linken Teilbaums
6.Mittel

Was passiert, wenn eine Hashtabelle nach Überschreiten eines Füllgrad-Schwellenwerts ein Rehashing durchführt?

  1. ADie vorhandenen Schlüssel werden an Ort und Stelle sortiert
  2. BDie ältesten Schlüssel werden gelöscht, um Platz zu schaffen
  3. CNur die kollidierenden Schlüssel kommen in eine neue Überlaufliste am Ende der Tabelle
  4. DEine größere Tabelle wird angelegt und jeder Schlüssel neu eingefügt
7.Schwer

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

  1. AEr fasst Ketten von Knoten mit nur einem Kind zu einer mit einer Zeichenkette beschrifteten Kante zusammen
  2. BEr behält nur den ersten Buchstaben jedes Worts
  3. CEr sortiert die Kinder jedes Knotens nach Häufigkeit
  4. DEr speichert jedes Wort in einer Hashtabelle an der Wurzel statt in einzelnen Knoten
8.Schwer

Die Union-Find-Struktur (Disjoint Set) mit Union by Rank und Pfadkompression hat amortisierte Kosten pro Operation von:

  1. AGenau O(log n)
  2. BO(n)
  3. CO(α(n)), der inversen Ackermann-Funktion, die praktisch konstant ist
  4. DO(n²)

Lösungsschlüssel

  1. 1. A · Ein Knoten ohne Kindknoten
  2. 2. D · Ein Pfad, der am selben Knoten beginnt und endet
  3. 3. C · Warteschlange (Queue)
  4. 4. A · Von der Wurzel aus den linken Kindern folgen, bis es kein linkes Kind mehr gibt
  5. 5. A · Am linkesten Knoten seines rechten Teilbaums
  6. 6. D · Eine größere Tabelle wird angelegt und jeder Schlüssel neu eingefügt
  7. 7. A · Er fasst Ketten von Knoten mit nur einem Kind zu einer mit einer Zeichenkette beschrifteten Kante zusammen
  8. 8. C · O(α(n)), der inversen Ackermann-Funktion, die praktisch konstant ist

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