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 eine Kollision in einer Hashtabelle?

  1. AZwei gleiche Schlüssel werden doppelt gespeichert
  2. BDer Tabelle geht der Speicher aus
  3. CZwei verschiedene Schlüssel werden auf denselben Index abgebildet
  4. DEin Schlüssel lässt sich überhaupt nicht hashen
2.Leicht

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

  1. AZugriff auf das Element an Index i
  2. BEntfernen des Kopfelements
  3. CEinfügen am Kopf
  4. DLesen des ersten Elements
3.Leicht

Wie viele Kanten hat ein Baum mit n Knoten?

  1. An − 1
  2. B2n
  3. Cn + 1
  4. Dn
4.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. A4 2 5 1 3
  2. B1 2 4 5 3
  3. C5 4 3 2 1
  4. D4 5 2 3 1
5.Mittel

Wozu dient ein Sentinel-Knoten (Dummy-Knoten) in einer verketteten Liste?

  1. AEr vereinfacht den Code, weil Sonderfälle am Kopf oder Ende wegfallen
  2. BEr speichert die Anzahl der Elemente
  3. CEr hält die Liste sortiert
  4. DUm zu verhindern, dass die Liste über eine feste Höchstzahl von Knoten hinauswächst
6.Mittel

Wie groß ist die Höhe eines binären Suchbaums mit n Knoten im schlechtesten Fall, wenn die Schlüssel in sortierter Reihenfolge eingefügt werden?

  1. A1
  2. Bn (er wird zu einer verketteten Liste)
  3. Clog₂ n
  4. D√n
7.Schwer

Ein Segmentbaum (Segment Tree) wird typischerweise verwendet, um:

  1. ADie Kanten eines Graphen zu speichern
  2. BBereichsabfragen (z. B. Bereichssummen) und Aktualisierungen in O(log n) zu beantworten
  3. CEinen Stack zu implementieren
  4. DZeichenketten alphabetisch zu sortieren, indem jedes Präfix in einem eigenen Baumknoten gespeichert wird
8.Schwer

Warum verwenden Datenbanken für Indizes oft B+-Bäume statt einfacher B-Bäume?

  1. AAlle Datensätze liegen in verketteten Blättern, was Bereichsscans effizient macht
  2. BB+-Bäume verwenden binäre innere Knoten, was Festplattenzugriffe reduziert
  3. CB+-Bäume speichern Daten nur in der Wurzel
  4. DB+-Bäume müssen nicht balanciert sein

Lösungsschlüssel

  1. 1. C · Zwei verschiedene Schlüssel werden auf denselben Index abgebildet
  2. 2. A · Zugriff auf das Element an Index i
  3. 3. A · n − 1
  4. 4. D · 4 5 2 3 1
  5. 5. A · Er vereinfacht den Code, weil Sonderfälle am Kopf oder Ende wegfallen
  6. 6. B · n (er wird zu einer verketteten Liste)
  7. 7. B · Bereichsabfragen (z. B. Bereichssummen) und Aktualisierungen in O(log n) zu beantworten
  8. 8. A · Alle Datensätze liegen in verketteten Blättern, was Bereichsscans effizient macht

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