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 Datenstruktur wird für eine Level-Order-Traversierung eines Baums verwendet?

  1. AStack
  2. BQueue
  3. CHashtabelle
  4. DPrioritätswarteschlange
2.Leicht

Wo befindet sich das kleinste Element eines binären Min-Heaps?

  1. AIn irgendeinem Blatt, das gesucht werden muss
  2. BIm linkesten Blatt
  3. CAn der letzten Array-Position
  4. DIn der Wurzel
3.Leicht

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

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

Eine Anwendung braucht schnelle Suchen, muss aber auch Schlüssel sortiert auflisten und Bereichsabfragen beantworten. Welche Struktur passt am besten?

  1. AEin Stack
  2. BEin balancierter binärer Suchbaum
  3. CEine Hashtabelle
  4. DEine unsortierte verkettete Liste
5.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 3
  3. CIndex 6
  4. DIndex 4
6.Mittel

Eine Queue wird mit zwei Stacks implementiert: push auf einen „in“-Stack und pop von einem „out“-Stack, der aus „in“ nachgefüllt wird, wenn er leer ist. Wie hoch sind die amortisierten Kosten pro Operation?

  1. AO(n)
  2. BO(log n)
  3. CO(1)
  4. DO(n²)
7.Schwer

Kahns Algorithmus zur topologischen Sortierung entfernt wiederholt Knoten mit Eingangsgrad 0. Welche Struktur hält diese Knoten?

  1. AEine Adjazenzmatrix, die festhält, welche Knoten bereits entfernt wurden
  2. BEin nach Ausgangsgrad geordneter Max-Heap
  3. CEin Stack aller besuchten Kanten
  4. DEine Queue (oder beliebige Sammlung) der Knoten mit Eingangsgrad 0
8.Schwer

Wie lange dauert die Suche nach einem beliebigen Schlüssel in einem binären Min-Heap mit n Elementen?

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

Lösungsschlüssel

  1. 1. B · Queue
  2. 2. D · In der Wurzel
  3. 3. A · Sie gibt das oberste Element zurück, ohne es zu entfernen
  4. 4. B · Ein balancierter binärer Suchbaum
  5. 5. D · Index 4
  6. 6. C · O(1)
  7. 7. D · Eine Queue (oder beliebige Sammlung) der Knoten mit Eingangsgrad 0
  8. 8. B · O(n)

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