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 kostet bei einem Array O(1), bei einer einfach verketteten Liste aber O(n)?

  1. AEntfernen des Kopfelements
  2. BEinfügen am Kopf
  3. CLesen des ersten Elements
  4. DZugriff auf das Element an Index i
2.Leicht

Wie heißt die Stack-Operation, die ein Element oben hinzufügt?

  1. AEnqueue
  2. BPeek
  3. CPush
  4. DPop
3.Leicht

Was ist in einem ungerichteten Graphen der Grad eines Knotens?

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

Du hast eine Referenz auf einen Knoten in der Mitte einer Liste. In welcher Liste kannst du ihn in O(1) entfernen?

  1. AIn einem sortierten Array
  2. BIn einem dynamischen Array
  3. CIn einer doppelt verketteten Liste
  4. DIn einer einfach verketteten Liste
5.Mittel

Was passiert, wenn eine Hashtabelle nach Überschreiten eines Füllgrad-Schwellenwerts ein Rehashing durchführt?

  1. ADie ältesten Schlüssel werden gelöscht, um Platz zu schaffen
  2. BNur die kollidierenden Schlüssel kommen in eine neue Überlaufliste am Ende der Tabelle
  3. CEine größere Tabelle wird angelegt und jeder Schlüssel neu eingefügt
  4. DDie vorhandenen Schlüssel werden an Ort und Stelle sortiert
6.Mittel

Eine Anwendung braucht schnelle Suchen, muss aber auch Schlüssel sortiert auflisten und Bereichsabfragen beantworten. Welche Struktur passt am besten?

  1. AEine unsortierte verkettete Liste
  2. BEin Stack
  3. CEin balancierter binärer Suchbaum
  4. DEine Hashtabelle
7.Schwer

Welche Operationen unterstützt ein Fenwick-Baum (Binary Indexed Tree) über einem Array von n Zahlen in O(log n)?

  1. AEinfügen von Elementen an beliebiger Position
  2. BFinden des Medians in O(1)
  3. CPräfixsummen-Abfragen und Aktualisierungen einzelner Elemente
  4. DSortieren des Arrays und binäre Suche
8.Schwer

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

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

Lösungsschlüssel

  1. 1. D · Zugriff auf das Element an Index i
  2. 2. C · Push
  3. 3. A · Die Anzahl der mit ihm verbundenen Kanten
  4. 4. C · In einer doppelt verketteten Liste
  5. 5. C · Eine größere Tabelle wird angelegt und jeder Schlüssel neu eingefügt
  6. 6. C · Ein balancierter binärer Suchbaum
  7. 7. C · Präfixsummen-Abfragen und Aktualisierungen einzelner Elemente
  8. 8. A · 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.