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 enthält jeder Knoten einer doppelt verketteten Liste?

  1. AZwei Kopien der Daten und einen Zeiger
  2. BDaten, einen Zeiger auf den nächsten Knoten und einen Zeiger auf den vorherigen Knoten
  3. CDaten und zwei Zeiger, einen auf den nächsten Knoten und einen auf den Knoten danach
  4. DDaten und nur einen Zeiger auf den nächsten Knoten
2.Leicht

In einer einfach verketteten Liste enthält jeder Knoten:

  1. ADaten und Referenzen auf alle anderen Knoten
  2. BDaten und einen Index
  3. CNur Daten
  4. DDaten und eine Referenz auf den nächsten Knoten
3.Leicht

Was sind Geschwisterknoten in einem Baum?

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

Welche Datenstruktur nutzt ein laufendes Programm, um aktive Funktionsaufrufe und ihre lokalen Variablen zu verwalten?

  1. ADen Aufrufstack (Call Stack)
  2. BEinen binären Suchbaum der Frames
  3. CEine Hashtabelle der Funktionen
  4. DDie Heap-Speicher-Queue
5.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
6.Mittel

Welche Zeitkomplexität hat die Suche nach einem Schlüssel in einem balancierten binären Suchbaum?

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

Warum kann man Elemente aus einem Standard-Bloom-Filter nicht einfach durch Löschen ihrer Bits entfernen?

  1. ABits in einem Bloom-Filter können nach der Erstellung nicht geändert werden
  2. BBloom-Filter speichern die vollständigen Elemente, die nach dem Hashen nicht wiedergefunden werden können
  3. CLöschen würde die Falsch-positiv-Rate auf 100 % erhöhen
  4. DDiese Bits können auch zu anderen Elementen gehören, was falsch-negative Ergebnisse verursachen würde
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(m)
  2. BO(1 + α), wobei α = n / m
  3. CO(log n)
  4. DO(n)

Lösungsschlüssel

  1. 1. B · Daten, einen Zeiger auf den nächsten Knoten und einen Zeiger auf den vorherigen Knoten
  2. 2. D · Daten und eine Referenz auf den nächsten Knoten
  3. 3. C · Knoten mit demselben Elternknoten
  4. 4. A · Den Aufrufstack (Call Stack)
  5. 5. B · Ein balancierter binärer Suchbaum
  6. 6. B · O(log n)
  7. 7. D · Diese Bits können auch zu anderen Elementen gehören, was falsch-negative Ergebnisse verursachen würde
  8. 8. B · O(1 + α), wobei α = n / m

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