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

Welche Operation kostet bei einem Array O(1), bei einer einfach verketteten Liste aber O(n)?

  1. AZugriff auf das Element an Index i
  2. BLesen des ersten Elements
  3. CEntfernen des Kopfelements
  4. DEinfügen am Kopf
2.Leicht

Was ist die Wurzel eines Baums?

  1. AEin beliebiger Knoten in der Mitte
  2. BEin Knoten ohne Kindknoten
  3. CDer oberste Knoten ohne Elternknoten
  4. DDer Knoten mit dem größten Wert
3.Leicht

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

  1. AKnoten, dann linker Teilbaum, dann rechter Teilbaum
  2. BLinker Teilbaum, dann rechter Teilbaum, dann Knoten
  3. CEbene für Ebene von oben
  4. DLinker Teilbaum, dann Knoten, dann rechter Teilbaum
4.Mittel

Eine Hashtabelle der Größe 7 verwendet h(k) = k mod 7 und lineares Sondieren. Wo wird 17 gespeichert, nachdem 10 eingefügt wurde?

  1. AIndex 0
  2. BIndex 6
  3. CIndex 3
  4. DIndex 4
5.Mittel

Wie wird in einer zirkulären Queue, die in einem Array der Kapazität n gespeichert ist, die nächste Position nach Index i berechnet?

  1. A(i − 1) mod n
  2. Bi + 1
  3. C2i + 1
  4. D(i + 1) mod n
6.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. BAm rechtesten Knoten seines linken Teilbaums
  3. CImmer bei seinem rechten Kind
  4. DImmer bei seinem Elternknoten
7.Schwer

Ein Bloom-Filter kann die Frage „Ist dieses Element in der Menge?“ beantworten mit:

  1. AImmer exakten Antworten
  2. BMöglichen falsch-positiven, aber keinen falsch-negativen Ergebnissen
  3. CAntworten nur für Zahlen
  4. DMöglichen falsch-negativen, aber keinen falsch-positiven Ergebnissen
8.Schwer

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

  1. ADadurch wird die Tabelle sortiert
  2. BGelöschte Schlüssel müssen aus Sicherheitsgründen für immer aufbewahrt werden, sodass Plätze nie wiederverwendet werden können
  3. CDas Leeren des Platzes könnte die Sondierungsfolge für andere Schlüssel unterbrechen
  4. DTombstones beschleunigen das Hashing

Lösungsschlüssel

  1. 1. A · Zugriff auf das Element an Index i
  2. 2. C · Der oberste Knoten ohne Elternknoten
  3. 3. A · Knoten, dann linker Teilbaum, dann rechter Teilbaum
  4. 4. D · Index 4
  5. 5. D · (i + 1) mod n
  6. 6. A · Am linkesten Knoten seines rechten Teilbaums
  7. 7. B · Möglichen falsch-positiven, aber keinen falsch-negativen Ergebnissen
  8. 8. C · Das Leeren des Platzes könnte die Sondierungsfolge für andere Schlüssel unterbrechen

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