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 enthält in einer einfach verketteten Liste der next-Zeiger des letzten Knotens?

  1. ADie Adresse des vorherigen Knotens
  2. BDie Anzahl der Knoten in der Liste
  3. CNull (keinen Knoten)
  4. DDie Adresse des ersten Knotens
2.Leicht

Was ist eine Deque (double-ended queue)?

  1. AEine Struktur, die Einfügen und Entfernen an beiden Enden erlaubt
  2. BEine Queue, die nur hinten das Entfernen erlaubt
  3. CEine nach Priorität sortierte Queue
  4. DZwei getrennte Queues, die sich ein Array teilen
3.Leicht

Welche Datenstruktur arbeitet nach dem Prinzip „first in, first out“ (FIFO)?

  1. AStapel (Stack)
  2. BWarteschlange (Queue)
  3. CBinärbaum
  4. DHeap
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. BDen ganzen Heap von Grund auf neu aufbauen
  3. CAns Ende des Arrays setzen und nach oben wandern lassen (sift-up), solange es die Heap-Eigenschaft verletzt
  4. DIn die Wurzel setzen und nach unten wandern lassen
5.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. B5 4 3 2 1
  3. C4 5 2 3 1
  4. D1 2 4 5 3
6.Mittel

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

  1. ADie Heap-Speicher-Queue
  2. BDen Aufrufstack (Call Stack)
  3. CEine Hashtabelle der Funktionen
  4. DEinen binären Suchbaum der Frames
7.Schwer

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

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

Warum könnte ein Server seine Hashfunktion zufällig aus einer universellen Familie wählen?

  1. ADamit die Tabelle nicht mehr vergrößert werden muss
  2. BUm zu garantieren, dass nie zwei Schlüssel kollidieren, welche Schlüssel ein Angreifer auch sendet
  3. CDamit es sehr unwahrscheinlich ist, dass ein Angreifer viele Schlüssel wählen kann, die alle kollidieren
  4. DDamit die Hashtabelle sortiert ist

Lösungsschlüssel

  1. 1. C · Null (keinen Knoten)
  2. 2. A · Eine Struktur, die Einfügen und Entfernen an beiden Enden erlaubt
  3. 3. B · Warteschlange (Queue)
  4. 4. C · Ans Ende des Arrays setzen und nach oben wandern lassen (sift-up), solange es die Heap-Eigenschaft verletzt
  5. 5. C · 4 5 2 3 1
  6. 6. B · Den Aufrufstack (Call Stack)
  7. 7. B · Eine Queue (oder beliebige Sammlung) der Knoten mit Eingangsgrad 0
  8. 8. C · Damit es sehr unwahrscheinlich ist, dass ein Angreifer viele Schlüssel wählen kann, die alle kollidieren

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