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 bewirkt die Operation peek (oder top) bei einem Stack?

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

Was wird bei der Darstellung eines Graphen als Adjazenzliste für jeden Knoten gespeichert?

  1. AEine Zeile aus V booleschen Werten
  2. BDer kürzeste Weg zu jedem anderen Knoten
  3. CDie Gesamtzahl der Kanten im Graphen
  4. DEine Liste seiner Nachbarknoten
3.Leicht

Was ist der Füllgrad (Load Factor) einer Hashtabelle?

  1. ADie Anzahl der bisherigen Kollisionen
  2. BDie Zeit, um die Tabelle von der Festplatte zu laden
  3. CDie Anzahl gespeicherter Elemente geteilt durch die Anzahl der Buckets
  4. DDie Anzahl der Buckets geteilt durch die durchschnittliche Länge der gespeicherten Schlüssel
4.Mittel

Wie lange dauert die Suche nach einem Wort der Länge L in einem Trie mit festem Alphabet?

  1. AO(n), wobei n die Anzahl der Wörter ist
  2. BO(log n), wobei n die Anzahl der Wörter ist
  3. CO(L), unabhängig davon, wie viele Wörter gespeichert sind
  4. DO(L × n)
5.Mittel

Ein Binärbaum hat die Wurzel 1 mit linkem Kind 2 und rechtem Kind 3; Knoten 2 hat die Kinder 4 (links) und 5 (rechts). Wie lautet die Pre-Order-Traversierung?

  1. A1 2 4 5 3
  2. B4 2 5 1 3
  3. C1 2 3 4 5
  4. D4 5 2 3 1
6.Mittel

Wie wird in einer zirkulären Queue, die in einem Array der Kapazität n gespeichert ist, die nächste Position nach Index i berechnet?

  1. A2i + 1
  2. Bi + 1
  3. C(i + 1) mod n
  4. D(i − 1) mod n
7.Schwer

Wie hoch ist unter der Annahme des einfachen gleichverteilten Hashings die erwartete Suchzeit in einer Hashtabelle mit Chaining, n Schlüsseln und m Buckets?

  1. AO(log n)
  2. BO(n)
  3. CO(m)
  4. DO(1 + α), wobei α = n / m
8.Schwer

Welche Laufzeit hat die Breitensuche auf einem Graphen mit V Knoten, der als Adjazenzmatrix gespeichert ist?

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

Lösungsschlüssel

  1. 1. D · Sie gibt das oberste Element zurück, ohne es zu entfernen
  2. 2. D · Eine Liste seiner Nachbarknoten
  3. 3. C · Die Anzahl gespeicherter Elemente geteilt durch die Anzahl der Buckets
  4. 4. C · O(L), unabhängig davon, wie viele Wörter gespeichert sind
  5. 5. A · 1 2 4 5 3
  6. 6. C · (i + 1) mod n
  7. 7. D · O(1 + α), wobei α = n / m
  8. 8. B · O(V²)

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