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 „first in, first out“ (FIFO)?

  1. ABinärbaum
  2. BHeap
  3. CStapel (Stack)
  4. DWarteschlange (Queue)
2.Leicht

Was ist das kennzeichnende Merkmal einer Menge (Set) als abstrakter Datentyp?

  1. ASie speichert Elemente ohne Duplikate
  2. BSie erlaubt nur an einem Ende Zugriff
  3. CSie speichert Schlüssel-Wert-Paare
  4. DSie speichert Elemente in sortierter Reihenfolge
3.Leicht

Was sind Geschwisterknoten in einem Baum?

  1. AKnoten in gleicher Tiefe in verschiedenen Teilbäumen
  2. BKnoten ohne Kindknoten
  3. CKnoten mit demselben Elternknoten
  4. DEin Knoten und sein Elternknoten
4.Mittel

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

  1. AEin balancierter binärer Suchbaum
  2. BEin Stack
  3. CEine unsortierte verkettete Liste
  4. DEine Hashtabelle
5.Mittel

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

  1. AAlle Blätter nach dem neuen Minimum durchsuchen
  2. BDie Wurzel entfernen und alle Elemente um eine Stelle nach links verschieben
  3. CDas letzte Element in die Wurzel verschieben und nach unten wandern lassen
  4. DDas letzte Element des Arrays entfernen
6.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. BIn die Wurzel setzen und nach unten wandern lassen
  3. CDen ganzen Heap von Grund auf neu aufbauen
  4. DAns Ende des Arrays setzen und nach oben wandern lassen (sift-up), solange es die Heap-Eigenschaft verletzt
7.Schwer

Ein Objekt wird als Schlüssel in einer Hashmap gespeichert, danach wird ein Feld geändert, das in seine Hashfunktion eingeht. Was ist die wahrscheinliche Folge?

  1. ADie Suche nach dem Objekt kann fehlschlagen, weil es im Bucket seines alten Hashs liegt
  2. BNichts ändert sich, weil der Hash eines Schlüssels nur einmal beim Programmstart berechnet wird
  3. CDie Map verschiebt den Schlüssel automatisch in seinen neuen Bucket
  4. DDie Map wirft im Moment der Feldänderung einen Fehler
8.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(n)
  2. BO(log n)
  3. CO(1 + α), wobei α = n / m
  4. DO(m)

Lösungsschlüssel

  1. 1. D · Warteschlange (Queue)
  2. 2. A · Sie speichert Elemente ohne Duplikate
  3. 3. C · Knoten mit demselben Elternknoten
  4. 4. A · Ein balancierter binärer Suchbaum
  5. 5. C · Das letzte Element in die Wurzel verschieben und nach unten wandern lassen
  6. 6. D · Ans Ende des Arrays setzen und nach oben wandern lassen (sift-up), solange es die Heap-Eigenschaft verletzt
  7. 7. A · Die Suche nach dem Objekt kann fehlschlagen, weil es im Bucket seines alten Hashs liegt
  8. 8. C · O(1 + α), wobei α = n / m

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