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 ein gewichteter Graph?

  1. AEin Graph, in dem manche Knoten schwerer sind als andere, weil sie mehr Kanten haben
  2. BEin Graph, in dem jede Kante einen Zahlenwert wie Kosten oder Entfernung hat
  3. CEin Graph, der auf der Festplatte gespeichert ist
  4. DEin Graph mit mehr Kanten als Knoten
2.Leicht

Was ist in einem ungerichteten Graphen der Grad eines Knotens?

  1. ADie Anzahl der mit ihm verbundenen Kanten
  2. BDie Anzahl der Knoten im Graphen
  3. CDie Länge des längsten Pfades, der von ihm ausgeht
  4. DSeine Position in der Adjazenzliste
3.Leicht

Was ist ein Blatt in einem Baum?

  1. AEin Knoten ohne Kindknoten
  2. BDer Knoten mit dem größten Wert
  3. CEin Knoten mit genau einem Kindknoten
  4. DEin Knoten ohne Elternknoten
4.Mittel

Wie lange dauert die Suche nach einem Wort der Länge L in einem Trie mit festem Alphabet?

  1. AO(n), wobei n die Anzahl der Wörter ist
  2. BO(L × n)
  3. CO(log n), wobei n die Anzahl der Wörter ist
  4. DO(L), unabhängig davon, wie viele Wörter gespeichert sind
5.Mittel

Ein Straßennetz hat 100,000 Kreuzungen, die jeweils mit etwa 4 anderen verbunden sind. Welche Darstellung ist am besten geeignet?

  1. AEin einziges sortiertes Array der Knoten
  2. BAdjazenzmatrix
  3. CAdjazenzliste
  4. DEin binärer Heap der Kanten
6.Mittel

In einem binären Min-Heap, der in einem Array gespeichert ist (Index beginnt bei 0), liegen die Kinder des Knotens mit Index i bei:

  1. A2i + 1 und 2i + 2
  2. B2i und 2i + 1
  3. Ci + 1 und i + 2
  4. Di/2 und i/2 + 1
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 sortiertes Array aller n Werte
  2. BEin Max-Heap der Größe k, dessen Wurzel ersetzt wird, wenn ein kleinerer Wert ankommt
  3. CEin Min-Heap mit allen n Werten, aus dem am Ende die k kleinsten entnommen werden
  4. DEine FIFO-Queue der letzten k Werte
8.Schwer

Das Löschen eines Knotens mit zwei Kindknoten aus einem binären Suchbaum erfolgt üblicherweise durch:

  1. AVertauschen mit der Wurzel
  2. BErsetzen durch seinen In-Order-Nachfolger (oder -Vorgänger) und Löschen dieses Knotens
  3. CDen darunterliegenden Teilbaum von Grund auf neu aufbauen und jeden darin enthaltenen Schlüssel erneut einfügen
  4. DEntfernen des gesamten Teilbaums

Lösungsschlüssel

  1. 1. B · Ein Graph, in dem jede Kante einen Zahlenwert wie Kosten oder Entfernung hat
  2. 2. A · Die Anzahl der mit ihm verbundenen Kanten
  3. 3. A · Ein Knoten ohne Kindknoten
  4. 4. D · O(L), unabhängig davon, wie viele Wörter gespeichert sind
  5. 5. C · Adjazenzliste
  6. 6. A · 2i + 1 und 2i + 2
  7. 7. B · Ein Max-Heap der Größe k, dessen Wurzel ersetzt wird, wenn ein kleinerer Wert ankommt
  8. 8. B · Ersetzen durch seinen In-Order-Nachfolger (oder -Vorgänger) und Löschen dieses Knotens

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