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 eignet sich am besten für die „Rückgängig“-Funktion (Undo) in einem Texteditor?

  1. AHash-Set
  2. BGraph
  3. CWarteschlange (Queue)
  4. DStapel (Stack)
2.Leicht

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

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

Die Tiefe eines Knotens in einem Baum ist:

  1. ADie Anzahl der Knoten in seinem Teilbaum
  2. BDie Anzahl der Kindknoten dieses Knotens
  3. CDie Anzahl der Kanten von der Wurzel bis zu diesem Knoten
  4. DDie Anzahl der Kanten von diesem Knoten bis zum tiefsten Blatt
4.Mittel

Was kostet das Einfügen eines Elements in der Mitte eines Arrays mit n Elementen?

  1. AO(n), weil die nachfolgenden Elemente verschoben werden müssen
  2. BO(log n), wegen der binären Suche
  3. CO(1), weil der Index bekannt ist
  4. DO(n²), weil jedes Element n-mal verschoben wird
5.Mittel

Eine Hashtabelle der Größe 7 verwendet h(k) = k mod 7 und lineares Sondieren. Wo wird 17 gespeichert, nachdem 10 eingefügt wurde?

  1. AIndex 0
  2. BIndex 3
  3. CIndex 4
  4. DIndex 6
6.Mittel

Was ist der größtmögliche Füllgrad einer Hashtabelle mit offener Adressierung?

  1. A2
  2. B0,5
  3. C1
  4. DEs gibt kein Maximum
7.Schwer

Ein dynamisches Array verdoppelt sich, wenn es voll ist. Warum verkleinern es viele Implementierungen erst, wenn es zu einem Viertel gefüllt ist, und nicht schon bei halber Füllung?

  1. AUm das Array sortiert zu halten
  2. BWeil Halbieren bei halber Füllung Elemente verlieren würde
  3. CWeil der Speicherverwalter Speicher nur in Vierteln eines Blocks freigeben kann
  4. DUm wiederholtes Umdimensionieren zu vermeiden, wenn sich push und pop nahe der Grenze abwechseln
8.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. CZeichenketten alphabetisch zu sortieren, indem jedes Präfix in einem eigenen Baumknoten gespeichert wird
  4. DEinen Stack zu implementieren

Lösungsschlüssel

  1. 1. D · Stapel (Stack)
  2. 2. D · Die Anzahl gespeicherter Elemente geteilt durch die Anzahl der Buckets
  3. 3. C · Die Anzahl der Kanten von der Wurzel bis zu diesem Knoten
  4. 4. A · O(n), weil die nachfolgenden Elemente verschoben werden müssen
  5. 5. C · Index 4
  6. 6. C · 1
  7. 7. D · Um wiederholtes Umdimensionieren zu vermeiden, wenn sich push und pop nahe der Grenze abwechseln
  8. 8. B · Bereichsabfragen (z. B. Bereichssummen) und Aktualisierungen in O(log n) zu beantworten

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