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 Operation ist in einem Array langsam, am Kopf einer verketteten Liste aber schnell?

  1. ABestimmen der Länge eines Arrays fester Größe
  2. BZugriff auf das 5. Element
  3. CLesen des letzten Elements per Index
  4. DEinfügen am Anfang
2.Leicht

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

  1. AInsert
  2. BDequeue
  3. CPush
  4. DEnqueue
3.Leicht

Ein Graph besteht aus:

  1. AZeilen und Spalten
  2. BNur einer Wurzel und Blättern
  3. CNur Schlüsseln und Hashwerten
  4. DKnoten (Ecken), die durch Kanten verbunden sind
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. BIn die Wurzel setzen und nach unten wandern lassen
  3. CAns Ende des Arrays setzen und nach oben wandern lassen (sift-up), solange es die Heap-Eigenschaft verletzt
  4. DDen ganzen Heap von Grund auf neu aufbauen
5.Mittel

Ein Ringpuffer (Circular Buffer) wird häufig verwendet, um Folgendes zu implementieren:

  1. AEine Hashfunktion
  2. BEinen binären Suchbaum
  3. CEine Graphtraversierung
  4. DEine Warteschlange fester Größe
6.Mittel

Die Schlüssel 50, 30, 70, 20, 40 werden in dieser Reihenfolge in einen leeren binären Suchbaum eingefügt. Was ist das linke Kind von 30?

  1. A70
  2. B50
  3. C20
  4. D40
7.Schwer

Du musst aus einem Strom von n Zahlen die k kleinsten Werte mit O(k) Speicher behalten. Welcher Ansatz schafft das in O(n log k) Zeit?

  1. AEin Min-Heap mit allen n Werten, aus dem am Ende die k kleinsten entnommen werden
  2. BEin sortiertes Array aller n Werte
  3. CEine FIFO-Queue der letzten k Werte
  4. DEin Max-Heap der Größe k, dessen Wurzel ersetzt wird, wenn ein kleinerer Wert ankommt
8.Schwer

Im BST mit Wurzel 50, linkem Teilbaum 30 (Kinder 20, 40) und rechtem Teilbaum 70 (Kinder 60, 80) wird die Wurzel mithilfe des In-Order-Nachfolgers gelöscht. Welcher Schlüssel wird die neue Wurzel?

  1. A40
  2. B80
  3. C60
  4. D70

Lösungsschlüssel

  1. 1. D · Einfügen am Anfang
  2. 2. B · Dequeue
  3. 3. D · Knoten (Ecken), die durch Kanten verbunden sind
  4. 4. C · Ans Ende des Arrays setzen und nach oben wandern lassen (sift-up), solange es die Heap-Eigenschaft verletzt
  5. 5. D · Eine Warteschlange fester Größe
  6. 6. C · 20
  7. 7. D · Ein Max-Heap der Größe k, dessen Wurzel ersetzt wird, wenn ein kleinerer Wert ankommt
  8. 8. C · 60

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