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 kennzeichnet einen Binärbaum?

  1. AJeder Knoten speichert eine Binärzahl
  2. BJeder Knoten hat höchstens zwei Kindknoten
  3. CDer Baum hat genau zwei Ebenen
  4. DJeder Knoten hat genau zwei Kindknoten
2.Leicht

Was bewirkt die Operation peek (oder top) bei einem Stack?

  1. ASie entfernt alle Elemente aus dem Stack
  2. BSie gibt das oberste Element zurück, ohne es zu entfernen
  3. CSie entfernt das oberste Element und gibt es zurück
  4. DSie gibt das unterste Element des Stacks zurück
3.Leicht

Was ist der Hauptunterschied zwischen einem statischen und einem dynamischen Array?

  1. AEin statisches Array erlaubt einen langsameren Indexzugriff
  2. BEin statisches Array kann nur Zahlen speichern
  3. CEin dynamisches Array speichert seine Elemente in verketteten Knoten, damit es einzeln wachsen kann
  4. DEin dynamisches Array kann wachsen, indem es in einen größeren Speicherblock umzieht
4.Mittel

AVL-Bäume und Rot-Schwarz-Bäume garantieren:

  1. ADass kein Knoten zwei Kindknoten hat
  2. BSuche in konstanter Zeit in jedem Fall
  3. CDass die Schlüssel in Einfügereihenfolge gespeichert werden
  4. DEine Höhe von O(log n) durch Rebalancierung
5.Mittel

Du hast eine Referenz auf einen Knoten in der Mitte einer Liste. In welcher Liste kannst du ihn in O(1) entfernen?

  1. AIn einem sortierten Array
  2. BIn einer doppelt verketteten Liste
  3. CIn einer einfach verketteten Liste
  4. DIn einem dynamischen Array
6.Mittel

Welchen abstrakten Datentyp verwendet Dijkstras Algorithmus, um den nächsten zu verarbeitenden Knoten zu wählen?

  1. AEine Menge ohne Ordnung
  2. BEine FIFO-Queue
  3. CEinen Stack
  4. DEine Min-Prioritätswarteschlange
7.Schwer

Wie hoch sind ohne Union by Rank und Pfadkompression die Kosten eines einzelnen find im schlechtesten Fall in einer Union-Find-Struktur mit n Elementen?

  1. AO(log n)
  2. BO(α(n))
  3. CO(n)
  4. DO(1)
8.Schwer

Welche Operationen unterstützt ein Fenwick-Baum (Binary Indexed Tree) über einem Array von n Zahlen in O(log n)?

  1. AEinfügen von Elementen an beliebiger Position
  2. BPräfixsummen-Abfragen und Aktualisierungen einzelner Elemente
  3. CSortieren des Arrays und binäre Suche
  4. DFinden des Medians in O(1)

Lösungsschlüssel

  1. 1. B · Jeder Knoten hat höchstens zwei Kindknoten
  2. 2. B · Sie gibt das oberste Element zurück, ohne es zu entfernen
  3. 3. D · Ein dynamisches Array kann wachsen, indem es in einen größeren Speicherblock umzieht
  4. 4. D · Eine Höhe von O(log n) durch Rebalancierung
  5. 5. B · In einer doppelt verketteten Liste
  6. 6. D · Eine Min-Prioritätswarteschlange
  7. 7. C · O(n)
  8. 8. B · Präfixsummen-Abfragen und Aktualisierungen einzelner Elemente

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