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

In einer einfach verketteten Liste enthält jeder Knoten:

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

Welche Operation ist in einem Array langsam, am Kopf einer verketteten Liste aber schnell?

  1. AEinfügen am Anfang
  2. BLesen des letzten Elements per Index
  3. CBestimmen der Länge eines Arrays fester Größe
  4. DZugriff auf das 5. Element
3.Leicht

Wie heißt die Queue-Operation, die das Element vorne entfernt?

  1. AEnqueue
  2. BDequeue
  3. CInsert
  4. DPush
4.Mittel

Was passiert, wenn eine Hashtabelle nach Überschreiten eines Füllgrad-Schwellenwerts ein Rehashing durchführt?

  1. AEine größere Tabelle wird angelegt und jeder Schlüssel neu eingefügt
  2. BDie ältesten Schlüssel werden gelöscht, um Platz zu schaffen
  3. CDie vorhandenen Schlüssel werden an Ort und Stelle sortiert
  4. DNur die kollidierenden Schlüssel kommen in eine neue Überlaufliste am Ende der Tabelle
5.Mittel

Wie wird in einer zirkulären Queue, die in einem Array der Kapazität n gespeichert ist, die nächste Position nach Index i berechnet?

  1. A(i + 1) mod n
  2. B(i − 1) mod n
  3. Ci + 1
  4. D2i + 1
6.Mittel

Eine In-Order-Traversierung eines binären Suchbaums besucht die Schlüssel in:

  1. AAufsteigend sortierter Reihenfolge
  2. BImmer absteigender Reihenfolge
  3. CEbenenweiser Reihenfolge (Level-Order)
  4. DEinfügereihenfolge
7.Schwer

Mit welcher Struktur lässt sich das Maximum jedes Fensters der Größe k in einem Array insgesamt in O(n) berechnen?

  1. AEine Deque mit Indizes in absteigender Reihenfolge der Werte
  2. BEin sortiertes Array, das durch Verschieben aktualisiert wird
  3. CEine einfach verkettete Liste der Fensterelemente
  4. DEin für jedes Fenster neu aufgebauter Min-Heap
8.Schwer

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

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

Lösungsschlüssel

  1. 1. C · Daten und eine Referenz auf den nächsten Knoten
  2. 2. A · Einfügen am Anfang
  3. 3. B · Dequeue
  4. 4. A · Eine größere Tabelle wird angelegt und jeder Schlüssel neu eingefügt
  5. 5. A · (i + 1) mod n
  6. 6. A · Aufsteigend sortierter Reihenfolge
  7. 7. A · Eine Deque mit Indizes in absteigender Reihenfolge der Werte
  8. 8. D · Er fasst Ketten von Knoten mit nur einem Kind zu einer mit einer Zeichenkette beschrifteten Kante zusammen

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