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 Pre-Order-Traversierung eines Binärbaums die Knoten?

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

Wie heißt die Stack-Operation, die ein Element oben hinzufügt?

  1. APeek
  2. BPush
  3. CPop
  4. DEnqueue
3.Leicht

Was ist in einem ungerichteten Graphen der Grad eines Knotens?

  1. ASeine Position in der Adjazenzliste
  2. BDie Länge des längsten Pfades, der von ihm ausgeht
  3. CDie Anzahl der Knoten im Graphen
  4. DDie Anzahl der mit ihm verbundenen Kanten
4.Mittel

Was ist der größtmögliche Füllgrad einer Hashtabelle mit offener Adressierung?

  1. A0,5
  2. B2
  3. C1
  4. DEs gibt kein Maximum
5.Mittel

Wo liegt in einem binären Heap, der in einem Array ab Index 0 gespeichert ist, der Elternknoten des Knotens mit Index i?

  1. ABei Index 2i + 1
  2. BBei Index ⌊i / 2⌋ + 1
  3. CBei Index i − 1
  4. DBei Index ⌊(i − 1) / 2⌋
6.Mittel

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

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

Ein dynamisches Array verdoppelt sich, wenn es voll ist. Warum verkleinern es viele Implementierungen erst, wenn es zu einem Viertel gefüllt ist, und nicht schon bei halber Füllung?

  1. AUm wiederholtes Umdimensionieren zu vermeiden, wenn sich push und pop nahe der Grenze abwechseln
  2. BWeil Halbieren bei halber Füllung Elemente verlieren würde
  3. CUm das Array sortiert zu halten
  4. DWeil der Speicherverwalter Speicher nur in Vierteln eines Blocks freigeben kann
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 · Knoten, dann linker Teilbaum, dann rechter Teilbaum
  2. 2. B · Push
  3. 3. D · Die Anzahl der mit ihm verbundenen Kanten
  4. 4. C · 1
  5. 5. D · Bei Index ⌊(i − 1) / 2⌋
  6. 6. A · Er ist ein vollständiger Binärbaum, daher folgen die Positionen einfachen Indexformeln
  7. 7. A · Um wiederholtes Umdimensionieren zu vermeiden, wenn sich push und pop nahe der Grenze abwechseln
  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.