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 Datenstruktur arbeitet nach dem Prinzip „last in, first out“ (LIFO)?

  1. AVerkettete Liste
  2. BStapel (Stack)
  3. CWarteschlange (Queue)
  4. DHashtabelle
2.Leicht

Was ist ein Zyklus in einem Graphen?

  1. AEin Knoten ohne Kanten
  2. BEin Pfad, der jeden Knoten besucht
  3. CEine Kante mit dem Gewicht null
  4. DEin Pfad, der am selben Knoten beginnt und endet
3.Leicht

Welche Datenstruktur eignet sich am besten für die „Rückgängig“-Funktion (Undo) in einem Texteditor?

  1. AWarteschlange (Queue)
  2. BStapel (Stack)
  3. CHash-Set
  4. DGraph
4.Mittel

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

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

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

  1. AEbenenweiser Reihenfolge (Level-Order)
  2. BAufsteigend sortierter Reihenfolge
  3. CEinfügereihenfolge
  4. DImmer absteigender Reihenfolge
6.Mittel

AVL-Bäume und Rot-Schwarz-Bäume garantieren:

  1. AEine Höhe von O(log n) durch Rebalancierung
  2. BDass kein Knoten zwei Kindknoten hat
  3. CSuche in konstanter Zeit in jedem Fall
  4. DDass die Schlüssel in Einfügereihenfolge gespeichert werden
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. AEin für jedes Fenster neu aufgebauter Min-Heap
  2. BEine Deque mit Indizes in absteigender Reihenfolge der Werte
  3. CEine einfach verkettete Liste der Fensterelemente
  4. DEin sortiertes Array, das durch Verschieben aktualisiert wird
8.Schwer

Was macht ein Splay-Baum nach jedem Zugriff?

  1. AEr färbt die Knoten auf dem Suchpfad um
  2. BEr verschiebt den zugegriffenen Knoten zu einem Blatt
  3. CEr rotiert den zugegriffenen Knoten bis zur Wurzel hoch
  4. DEr baut den ganzen Baum in balancierter Form neu auf

Lösungsschlüssel

  1. 1. B · Stapel (Stack)
  2. 2. D · Ein Pfad, der am selben Knoten beginnt und endet
  3. 3. B · Stapel (Stack)
  4. 4. C · O(L), unabhängig davon, wie viele Wörter gespeichert sind
  5. 5. B · Aufsteigend sortierter Reihenfolge
  6. 6. A · Eine Höhe von O(log n) durch Rebalancierung
  7. 7. B · Eine Deque mit Indizes in absteigender Reihenfolge der Werte
  8. 8. C · Er rotiert den zugegriffenen Knoten bis zur Wurzel hoch

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