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

  1. AKnoten ohne Kindknoten
  2. BKnoten in gleicher Tiefe in verschiedenen Teilbäumen
  3. CEin Knoten und sein Elternknoten
  4. DKnoten mit demselben Elternknoten
2.Leicht

Die Höhe eines Baums wird üblicherweise definiert als:

  1. ADie Anzahl der Kanten auf dem längsten Pfad von der Wurzel zu einem Blatt
  2. BDie Anzahl der Blätter im Baum
  3. CDie Gesamtzahl der Knoten im Baum, einschließlich der Wurzel und jedes Blatts
  4. DDie Anzahl der Kindknoten der Wurzel
3.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. CEbene für Ebene von oben
  4. DKnoten, dann linker Teilbaum, dann rechter Teilbaum
4.Mittel

Welche Zeitkomplexität hat die Suche nach einem Schlüssel in einem balancierten binären Suchbaum?

  1. AO(log n)
  2. BO(n)
  3. CO(n log n)
  4. DO(1)
5.Mittel

Wie viel Speicher benötigt eine Adjazenzliste für einen Graphen mit V Knoten und E Kanten?

  1. AO(V²)
  2. BO(V + E)
  3. CO(E²)
  4. DO(V × E)
6.Mittel

Eine Queue wird mit zwei Stacks implementiert: push auf einen „in“-Stack und pop von einem „out“-Stack, der aus „in“ nachgefüllt wird, wenn er leer ist. Wie hoch sind die amortisierten Kosten pro Operation?

  1. AO(n²)
  2. BO(log n)
  3. CO(n)
  4. DO(1)
7.Schwer

Warum wird in einer Hashtabelle mit offener Adressierung beim Löschen oft eine „Tombstone“-Markierung verwendet?

  1. ADas Leeren des Platzes könnte die Sondierungsfolge für andere Schlüssel unterbrechen
  2. BGelöschte Schlüssel müssen aus Sicherheitsgründen für immer aufbewahrt werden, sodass Plätze nie wiederverwendet werden können
  3. CTombstones beschleunigen das Hashing
  4. DDadurch wird die Tabelle sortiert
8.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

Lösungsschlüssel

  1. 1. D · Knoten mit demselben Elternknoten
  2. 2. A · Die Anzahl der Kanten auf dem längsten Pfad von der Wurzel zu einem Blatt
  3. 3. D · Knoten, dann linker Teilbaum, dann rechter Teilbaum
  4. 4. A · O(log n)
  5. 5. B · O(V + E)
  6. 6. D · O(1)
  7. 7. A · Das Leeren des Platzes könnte die Sondierungsfolge für andere Schlüssel unterbrechen
  8. 8. A · Er fasst Ketten von Knoten mit nur einem Kind zu einer mit einer Zeichenkette beschrifteten Kante zusammen

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