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 der Füllgrad (Load Factor) einer Hashtabelle?

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

Was ist der Hauptunterschied zwischen einem statischen und einem dynamischen Array?

  1. AEin dynamisches Array speichert seine Elemente in verketteten Knoten, damit es einzeln wachsen kann
  2. BEin statisches Array erlaubt einen langsameren Indexzugriff
  3. CEin statisches Array kann nur Zahlen speichern
  4. DEin dynamisches Array kann wachsen, indem es in einen größeren Speicherblock umzieht
3.Leicht

Wie werden die Elemente eines Arrays im Speicher abgelegt?

  1. AVerstreut, über Zeiger verbunden
  2. BAn zufälligen, per Hash gewählten Stellen
  3. CIn einem Baum aus Speicherseiten
  4. DIn einem zusammenhängenden Block, eins nach dem anderen
4.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
5.Mittel

Ein Trie (Präfixbaum) ist besonders effizient für:

  1. ADas Finden kürzester Wege
  2. BDas Sortieren von Zahlen
  3. CPräfixsuchen wie Autovervollständigung
  4. DDas Speichern von Matrizen
6.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. BEine Hashtabelle
  3. CEin balancierter binärer Suchbaum
  4. DEine unsortierte verkettete Liste
7.Schwer

Wie verbessert ein Radix-Baum (komprimierter Trie) einen einfachen Trie?

  1. AEr fasst Ketten von Knoten mit nur einem Kind zu einer mit einer Zeichenkette beschrifteten Kante zusammen
  2. BEr speichert jedes Wort in einer Hashtabelle an der Wurzel statt in einzelnen Knoten
  3. CEr behält nur den ersten Buchstaben jedes Worts
  4. DEr sortiert die Kinder jedes Knotens nach Häufigkeit
8.Schwer

Kahns Algorithmus zur topologischen Sortierung entfernt wiederholt Knoten mit Eingangsgrad 0. Welche Struktur hält diese Knoten?

  1. AEine Adjazenzmatrix, die festhält, welche Knoten bereits entfernt wurden
  2. BEin nach Ausgangsgrad geordneter Max-Heap
  3. CEin Stack aller besuchten Kanten
  4. DEine Queue (oder beliebige Sammlung) der Knoten mit Eingangsgrad 0

Lösungsschlüssel

  1. 1. C · Die Anzahl gespeicherter Elemente geteilt durch die Anzahl der Buckets
  2. 2. D · Ein dynamisches Array kann wachsen, indem es in einen größeren Speicherblock umzieht
  3. 3. D · In einem zusammenhängenden Block, eins nach dem anderen
  4. 4. C · 1
  5. 5. C · Präfixsuchen wie Autovervollständigung
  6. 6. C · Ein balancierter binärer Suchbaum
  7. 7. A · Er fasst Ketten von Knoten mit nur einem Kind zu einer mit einer Zeichenkette beschrifteten Kante zusammen
  8. 8. D · Eine Queue (oder beliebige Sammlung) der Knoten mit Eingangsgrad 0

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