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 Struktur wird typischerweise zur Implementierung einer Prioritätswarteschlange verwendet?

  1. AEin Heap
  2. BEine Zeichenkette
  3. CEine ungeordnete einfach verkettete Liste
  4. DEin Stack
2.Leicht

In einem binären Suchbaum sind die Werte im linken Teilbaum eines Knotens:

  1. AGleich dem Wert des Knotens
  2. BIn zufälliger Reihenfolge
  3. CKleiner als der Wert des Knotens
  4. DGrößer als der Wert des Knotens
3.Leicht

Was enthält jeder Knoten einer doppelt verketteten Liste?

  1. ADaten und zwei Zeiger, einen auf den nächsten Knoten und einen auf den Knoten danach
  2. BDaten, einen Zeiger auf den nächsten Knoten und einen Zeiger auf den vorherigen Knoten
  3. CZwei Kopien der Daten und einen Zeiger
  4. DDaten und nur einen Zeiger auf den nächsten Knoten
4.Mittel

Wie lange dauert es, mit einer Adjazenzmatrix zu prüfen, ob die Kante (u, v) existiert?

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

Was kostet das Einfügen eines Elements in der Mitte eines Arrays mit n Elementen?

  1. AO(log n), wegen der binären Suche
  2. BO(n), weil die nachfolgenden Elemente verschoben werden müssen
  3. CO(1), weil der Index bekannt ist
  4. DO(n²), weil jedes Element n-mal verschoben wird
6.Mittel

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

  1. AEs gibt kein Maximum
  2. B0,5
  3. C1
  4. D2
7.Schwer

Du musst aus einem Strom von n Zahlen die k kleinsten Werte mit O(k) Speicher behalten. Welcher Ansatz schafft das in O(n log k) Zeit?

  1. AEin Min-Heap mit allen n Werten, aus dem am Ende die k kleinsten entnommen werden
  2. BEin sortiertes Array aller n Werte
  3. CEin Max-Heap der Größe k, dessen Wurzel ersetzt wird, wenn ein kleinerer Wert ankommt
  4. DEine FIFO-Queue der letzten k Werte
8.Schwer

Ein AVL-Knoten ist unbalanciert, weil der rechte Teilbaum seines linken Kindes zu hoch wurde (Links-rechts-Fall). Welche Korrektur wird angewendet?

  1. AEine einfache Rechtsrotation am Knoten
  2. BEine Linksrotation am linken Kind, dann eine Rechtsrotation am Knoten
  3. CEine einfache Linksrotation am Knoten
  4. DEine Rechtsrotation am linken Kind, dann eine Linksrotation am Knoten

Lösungsschlüssel

  1. 1. A · Ein Heap
  2. 2. C · Kleiner als der Wert des Knotens
  3. 3. B · Daten, einen Zeiger auf den nächsten Knoten und einen Zeiger auf den vorherigen Knoten
  4. 4. B · O(1)
  5. 5. B · O(n), weil die nachfolgenden Elemente verschoben werden müssen
  6. 6. C · 1
  7. 7. C · Ein Max-Heap der Größe k, dessen Wurzel ersetzt wird, wenn ein kleinerer Wert ankommt
  8. 8. B · Eine Linksrotation am linken Kind, dann eine Rechtsrotation am Knoten

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