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 arbeitet nach dem Prinzip „last in, first out“ (LIFO)?

  1. AStapel (Stack)
  2. BHashtabelle
  3. CVerkettete Liste
  4. DWarteschlange (Queue)
2.Leicht

Welche Operation kostet bei einem Array O(1), bei einer einfach verketteten Liste aber O(n)?

  1. AEinfügen am Kopf
  2. BZugriff auf das Element an Index i
  3. CLesen des ersten Elements
  4. DEntfernen des Kopfelements
3.Leicht

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

  1. AIm linkesten Blatt
  2. BIn der Wurzel
  3. CAn der letzten Array-Position
  4. DIn irgendeinem Blatt, das gesucht werden muss
4.Mittel

In einem binären Min-Heap, der in einem Array gespeichert ist (Index beginnt bei 0), liegen die Kinder des Knotens mit Index i bei:

  1. Ai/2 und i/2 + 1
  2. Bi + 1 und i + 2
  3. C2i + 1 und 2i + 2
  4. D2i und 2i + 1
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 ⌊i / 2⌋ + 1
  2. BBei Index ⌊(i − 1) / 2⌋
  3. CBei Index i − 1
  4. DBei Index 2i + 1
6.Mittel

Wie viel Speicher benötigt eine Adjazenzliste für einen Graphen mit V Knoten und E Kanten?

  1. AO(E²)
  2. BO(V + E)
  3. CO(V × E)
  4. DO(V²)
7.Schwer

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

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

Die Zeitkomplexität von decrease-key in einem binären Heap (bei bekannter Position des Elements) beträgt:

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

Lösungsschlüssel

  1. 1. A · Stapel (Stack)
  2. 2. B · Zugriff auf das Element an Index i
  3. 3. B · In der Wurzel
  4. 4. C · 2i + 1 und 2i + 2
  5. 5. B · Bei Index ⌊(i − 1) / 2⌋
  6. 6. B · O(V + E)
  7. 7. A · O(n)
  8. 8. C · O(log n)

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