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 ist ein gerichteter Graph?

  1. AEin Graph, dessen Kanten alle Gewichte haben
  2. BEin Graph, dessen Kanten eine Richtung von einem Knoten zu einem anderen haben
  3. CEin Graph, der keine Zyklen hat
  4. DEin Graph, in dem je zwei verschiedene Knoten durch eine Kante verbunden sind
2.Leicht

Ein Graph besteht aus:

  1. AKnoten (Ecken), die durch Kanten verbunden sind
  2. BNur Schlüsseln und Hashwerten
  3. CNur einer Wurzel und Blättern
  4. DZeilen und Spalten
3.Leicht

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

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

Wie funktioniert extract-min in einem binären Min-Heap?

  1. ADas letzte Element in die Wurzel verschieben und nach unten wandern lassen
  2. BDie Wurzel entfernen und alle Elemente um eine Stelle nach links verschieben
  3. CAlle Blätter nach dem neuen Minimum durchsuchen
  4. DDas letzte Element des Arrays entfernen
5.Mittel

Wie wird ein neues Element in einen binären Heap eingefügt?

  1. AAn der sortierten Position einfügen, indem alle größeren Elemente um eine Stelle nach rechts verschoben werden
  2. BAns Ende des Arrays setzen und nach oben wandern lassen (sift-up), solange es die Heap-Eigenschaft verletzt
  3. CDen ganzen Heap von Grund auf neu aufbauen
  4. DIn die Wurzel setzen und nach unten wandern lassen
6.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 Post-Order-Traversierung?

  1. A5 4 3 2 1
  2. B4 2 5 1 3
  3. C1 2 4 5 3
  4. D4 5 2 3 1
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(1 + α), wobei α = n / m
  2. BO(log n)
  3. CO(m)
  4. DO(n)
8.Schwer

Wie kannst du mit O(1) zusätzlichem Speicher erkennen, ob eine einfach verkettete Liste einen Zyklus enthält?

  1. ADie Liste sortieren und nach Duplikaten suchen
  2. BDie Knoten zählen, bis die Zahl das Längenfeld der Liste übersteigt
  3. CJeden besuchten Knoten in einem Hash-Set speichern
  4. DEinen Zeiger um einen Schritt und einen anderen um zwei Schritte bewegen und prüfen, ob sie sich treffen

Lösungsschlüssel

  1. 1. B · Ein Graph, dessen Kanten eine Richtung von einem Knoten zu einem anderen haben
  2. 2. A · Knoten (Ecken), die durch Kanten verbunden sind
  3. 3. C · Die Anzahl gespeicherter Elemente geteilt durch die Anzahl der Buckets
  4. 4. A · Das letzte Element in die Wurzel verschieben und nach unten wandern lassen
  5. 5. B · Ans Ende des Arrays setzen und nach oben wandern lassen (sift-up), solange es die Heap-Eigenschaft verletzt
  6. 6. D · 4 5 2 3 1
  7. 7. A · O(1 + α), wobei α = n / m
  8. 8. D · Einen Zeiger um einen Schritt und einen anderen um zwei Schritte bewegen und prüfen, ob sie sich treffen

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