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. AStapel (Stack)
  2. BWarteschlange (Queue)
  3. CHashtabelle
  4. DVerkettete Liste
2.Leicht

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

  1. AWarteschlange (Queue)
  2. BHeap
  3. CStapel (Stack)
  4. DBinärbaum
3.Leicht

In einem binären Suchbaum sind die Werte im linken Teilbaum eines Knotens:

  1. AIn zufälliger Reihenfolge
  2. BGrößer als der Wert des Knotens
  3. CGleich dem Wert des Knotens
  4. DKleiner als der Wert des Knotens
4.Mittel

Warum kann ein binärer Heap ganz ohne Zeiger in einem Array gespeichert werden?

  1. AEr ist ein vollständiger Binärbaum, daher folgen die Positionen einfachen Indexformeln
  2. BAlle Schlüssel in einem Heap sind gleich
  3. CHeaps enthalten nie mehr als 100 Elemente
  4. DArrays halten Schlüssel automatisch sortiert, sodass keine Zeiger nötig sind
5.Mittel

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

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

Eine Hashtabelle der Größe 7 verwendet h(k) = k mod 7 und lineares Sondieren. Wo wird 17 gespeichert, nachdem 10 eingefügt wurde?

  1. AIndex 0
  2. BIndex 4
  3. CIndex 6
  4. DIndex 3
7.Schwer

Welche Eigenschaft muss ein Rot-Schwarz-Baum erfüllen?

  1. ADie Wurzel muss rot sein
  2. BRote Knoten müssen rote Kindknoten haben, sodass rote Knoten immer ununterbrochene Ketten bis zu den Blättern bilden
  3. CJeder Knoten muss rot sein
  4. DJeder Pfad von einem Knoten zu seinen Nachfahren-Blättern enthält gleich viele schwarze Knoten
8.Schwer

In einem Ringpuffer kann front == rear entweder leer oder voll bedeuten. Wie unterscheidet man das üblicherweise?

  1. ADie Puffergröße zu einer Zweierpotenz machen
  2. BFront und rear in derselben Variablen speichern
  3. CEinen separaten Elementzähler führen oder immer einen Platz frei lassen
  4. DDen Puffer immer leeren, wenn front gleich rear ist, sodass der Zustand leer ist

Lösungsschlüssel

  1. 1. A · Stapel (Stack)
  2. 2. A · Warteschlange (Queue)
  3. 3. D · Kleiner als der Wert des Knotens
  4. 4. A · Er ist ein vollständiger Binärbaum, daher folgen die Positionen einfachen Indexformeln
  5. 5. D · O(L), unabhängig davon, wie viele Wörter gespeichert sind
  6. 6. B · Index 4
  7. 7. D · Jeder Pfad von einem Knoten zu seinen Nachfahren-Blättern enthält gleich viele schwarze Knoten
  8. 8. C · Einen separaten Elementzähler führen oder immer einen Platz frei lassen

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