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 gerichteter Graph?

  1. AEin Graph, in dem je zwei verschiedene Knoten durch eine Kante verbunden sind
  2. BEin Graph, dessen Kanten alle Gewichte haben
  3. CEin Graph, dessen Kanten eine Richtung von einem Knoten zu einem anderen haben
  4. DEin Graph, der keine Zyklen hat
2.Leicht

Welche Datenstruktur wird für eine Level-Order-Traversierung eines Baums verwendet?

  1. AHashtabelle
  2. BQueue
  3. CPrioritätswarteschlange
  4. DStack
3.Leicht

Ein Graph besteht aus:

  1. AKnoten (Ecken), die durch Kanten verbunden sind
  2. BNur Schlüsseln und Hashwerten
  3. CNur einer Wurzel und Blättern
  4. DZeilen und Spalten
4.Mittel

Wie funktioniert extract-min in einem binären Min-Heap?

  1. ADas letzte Element des Arrays entfernen
  2. BDie Wurzel entfernen und alle Elemente um eine Stelle nach links verschieben
  3. CAlle Blätter nach dem neuen Minimum durchsuchen
  4. DDas letzte Element in die Wurzel verschieben und nach unten wandern lassen
5.Mittel

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

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

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

  1. ASuche in konstanter Zeit in jedem Fall
  2. BDass die Schlüssel in Einfügereihenfolge gespeichert werden
  3. CDass kein Knoten zwei Kindknoten hat
  4. DEine Höhe von O(log n) durch Rebalancierung
7.Schwer

Warum kann man Elemente aus einem Standard-Bloom-Filter nicht einfach durch Löschen ihrer Bits entfernen?

  1. ADiese Bits können auch zu anderen Elementen gehören, was falsch-negative Ergebnisse verursachen würde
  2. BLöschen würde die Falsch-positiv-Rate auf 100 % erhöhen
  3. CBits in einem Bloom-Filter können nach der Erstellung nicht geändert werden
  4. DBloom-Filter speichern die vollständigen Elemente, die nach dem Hashen nicht wiedergefunden werden können
8.Schwer

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

  1. ASortieren des Arrays und binäre Suche
  2. BEinfügen von Elementen an beliebiger Position
  3. CFinden des Medians in O(1)
  4. DPräfixsummen-Abfragen und Aktualisierungen einzelner Elemente

Lösungsschlüssel

  1. 1. C · Ein Graph, dessen Kanten eine Richtung von einem Knoten zu einem anderen haben
  2. 2. B · Queue
  3. 3. A · Knoten (Ecken), die durch Kanten verbunden sind
  4. 4. D · Das letzte Element in die Wurzel verschieben und nach unten wandern lassen
  5. 5. C · Eine größere Tabelle wird angelegt und jeder Schlüssel neu eingefügt
  6. 6. D · Eine Höhe von O(log n) durch Rebalancierung
  7. 7. A · Diese Bits können auch zu anderen Elementen gehören, was falsch-negative Ergebnisse verursachen würde
  8. 8. D · Präfixsummen-Abfragen und Aktualisierungen einzelner Elemente

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