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

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

  1. ALinker Teilbaum, dann rechter Teilbaum, dann Knoten
  2. BKnoten, dann linker Teilbaum, dann rechter Teilbaum
  3. CLinker Teilbaum, dann Knoten, dann rechter Teilbaum
  4. DRechter Teilbaum, dann Knoten, dann linker Teilbaum
2.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. CLinker Teilbaum, dann Knoten, dann rechter Teilbaum
  4. DEbene für Ebene von oben
3.Leicht

Was ist das kennzeichnende Merkmal einer Menge (Set) als abstrakter Datentyp?

  1. ASie speichert Schlüssel-Wert-Paare
  2. BSie speichert Elemente ohne Duplikate
  3. CSie speichert Elemente in sortierter Reihenfolge
  4. DSie erlaubt nur an einem Ende Zugriff
4.Mittel

Warum kann ein binärer Heap ganz ohne Zeiger in einem Array gespeichert werden?

  1. AAlle Schlüssel in einem Heap sind gleich
  2. BArrays halten Schlüssel automatisch sortiert, sodass keine Zeiger nötig sind
  3. CEr ist ein vollständiger Binärbaum, daher folgen die Positionen einfachen Indexformeln
  4. DHeaps enthalten nie mehr als 100 Elemente
5.Mittel

Wie viel Speicher benötigt eine Adjazenzmatrix für einen Graphen mit V Knoten?

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

Wozu dient ein Sentinel-Knoten (Dummy-Knoten) in einer verketteten Liste?

  1. AEr vereinfacht den Code, weil Sonderfälle am Kopf oder Ende wegfallen
  2. BEr hält die Liste sortiert
  3. CUm zu verhindern, dass die Liste über eine feste Höchstzahl von Knoten hinauswächst
  4. DEr speichert die Anzahl der Elemente
7.Schwer

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

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

Welche Aussage über Heapsort ist richtig?

  1. AEr läuft bei jeder Eingabe in O(n)
  2. BEr braucht einen binären Suchbaum als zusätzlichen Speicher und verbraucht daher O(n) zusätzlichen Speicher
  3. CEr ist stabil und braucht O(n) zusätzlichen Speicher
  4. DEr sortiert in place in O(n log n) im schlechtesten Fall, ist aber nicht stabil

Lösungsschlüssel

  1. 1. A · Linker Teilbaum, dann rechter Teilbaum, dann Knoten
  2. 2. A · Knoten, dann linker Teilbaum, dann rechter Teilbaum
  3. 3. B · Sie speichert Elemente ohne Duplikate
  4. 4. C · Er ist ein vollständiger Binärbaum, daher folgen die Positionen einfachen Indexformeln
  5. 5. D · O(V²)
  6. 6. A · Er vereinfacht den Code, weil Sonderfälle am Kopf oder Ende wegfallen
  7. 7. D · Das Leeren des Platzes könnte die Sondierungsfolge für andere Schlüssel unterbrechen
  8. 8. D · Er sortiert in place in O(n log n) im schlechtesten Fall, ist aber nicht stabil

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