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 das kennzeichnende Merkmal einer Menge (Set) als abstrakter Datentyp?

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

In einer einfach verketteten Liste enthält jeder Knoten:

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

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

  1. ADie Anzahl gespeicherter Elemente geteilt durch die Anzahl der Buckets
  2. BDie Anzahl der Buckets geteilt durch die durchschnittliche Länge der gespeicherten Schlüssel
  3. CDie Zeit, um die Tabelle von der Festplatte zu laden
  4. DDie Anzahl der bisherigen Kollisionen
4.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. BAns Ende des Arrays setzen und nach oben wandern lassen (sift-up), solange es die Heap-Eigenschaft verletzt
  3. CIn die Wurzel setzen und nach unten wandern lassen
  4. DDen ganzen Heap von Grund auf neu aufbauen
5.Mittel

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

  1. ADie Heap-Speicher-Queue
  2. BEinen binären Suchbaum der Frames
  3. CDen Aufrufstack (Call Stack)
  4. DEine Hashtabelle der Funktionen
6.Mittel

Was gilt für die Adjazenzmatrix eines ungerichteten Graphen?

  1. ASie ist immer eine obere Dreiecksmatrix
  2. BSie ist symmetrisch zur Hauptdiagonale
  3. CIhre Hauptdiagonale enthält immer Einsen
  4. DJede Zeile hat genau eine 1
7.Schwer

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

  1. AEr speichert jedes Wort in einer Hashtabelle an der Wurzel statt in einzelnen Knoten
  2. BEr behält nur den ersten Buchstaben jedes Worts
  3. CEr fasst Ketten von Knoten mit nur einem Kind zu einer mit einer Zeichenkette beschrifteten Kante zusammen
  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. BEine Queue (oder beliebige Sammlung) der Knoten mit Eingangsgrad 0
  3. CEin nach Ausgangsgrad geordneter Max-Heap
  4. DEin Stack aller besuchten Kanten

Lösungsschlüssel

  1. 1. D · Sie speichert Elemente ohne Duplikate
  2. 2. A · Daten und eine Referenz auf den nächsten Knoten
  3. 3. A · Die Anzahl gespeicherter Elemente geteilt durch die Anzahl der Buckets
  4. 4. B · Ans Ende des Arrays setzen und nach oben wandern lassen (sift-up), solange es die Heap-Eigenschaft verletzt
  5. 5. C · Den Aufrufstack (Call Stack)
  6. 6. B · Sie ist symmetrisch zur Hauptdiagonale
  7. 7. C · Er fasst Ketten von Knoten mit nur einem Kind zu einer mit einer Zeichenkette beschrifteten Kante zusammen
  8. 8. B · Eine Queue (oder beliebige Sammlung) der Knoten mit Eingangsgrad 0

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