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 die Max-Heap-Eigenschaft?

  1. ADie Schlüssel sind von links nach rechts sortiert
  2. BDer Schlüssel jedes Elternknotens ist größer oder gleich den Schlüsseln seiner Kinder
  3. CAlle Blätter enthalten den maximalen Schlüssel
  4. DDer Schlüssel jedes linken Kindes ist größer oder gleich dem Schlüssel seines rechten Geschwisterknotens
2.Leicht

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

  1. AKleiner als der Wert des Knotens
  2. BGleich dem Wert des Knotens
  3. CGrößer als der Wert des Knotens
  4. DIn zufälliger Reihenfolge
3.Leicht

Was bewirkt die Operation peek (oder top) bei einem Stack?

  1. ASie entfernt alle Elemente aus dem Stack
  2. BSie entfernt das oberste Element und gibt es zurück
  3. CSie gibt das unterste Element des Stacks zurück
  4. DSie gibt das oberste Element zurück, ohne es zu entfernen
4.Mittel

Was gilt für die Adjazenzmatrix eines ungerichteten Graphen?

  1. AIhre Hauptdiagonale enthält immer Einsen
  2. BSie ist immer eine obere Dreiecksmatrix
  3. CJede Zeile hat genau eine 1
  4. DSie ist symmetrisch zur Hauptdiagonale
5.Mittel

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

  1. AEine größere Tabelle wird angelegt und jeder Schlüssel neu eingefügt
  2. BDie vorhandenen Schlüssel werden an Ort und Stelle sortiert
  3. CDie ältesten Schlüssel werden gelöscht, um Platz zu schaffen
  4. DNur die kollidierenden Schlüssel kommen in eine neue Überlaufliste am Ende der Tabelle
6.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
7.Schwer

Wie verbessert ein Radix-Baum (komprimierter Trie) einen einfachen Trie?

  1. AEr speichert jedes Wort in einer Hashtabelle an der Wurzel statt in einzelnen Knoten
  2. BEr sortiert die Kinder jedes Knotens nach Häufigkeit
  3. CEr behält nur den ersten Buchstaben jedes Worts
  4. DEr fasst Ketten von Knoten mit nur einem Kind zu einer mit einer Zeichenkette beschrifteten Kante zusammen
8.Schwer

Du willst für jedes Element eines Arrays das nächstgrößere Element rechts davon finden, insgesamt in O(n). Welche Struktur hilft?

  1. AEine Hashtabelle aller Elemente
  2. BEine Queue, die jedes Elementpaar enthält
  3. CEin binärer Suchbaum, der für jedes Element neu aufgebaut wird
  4. DEin Stack, der Elemente hält, die noch auf ihre Antwort warten

Lösungsschlüssel

  1. 1. B · Der Schlüssel jedes Elternknotens ist größer oder gleich den Schlüsseln seiner Kinder
  2. 2. A · Kleiner als der Wert des Knotens
  3. 3. D · Sie gibt das oberste Element zurück, ohne es zu entfernen
  4. 4. D · Sie ist symmetrisch zur Hauptdiagonale
  5. 5. A · Eine größere Tabelle wird angelegt und jeder Schlüssel neu eingefügt
  6. 6. C · O(L), unabhängig davon, wie viele Wörter gespeichert sind
  7. 7. D · Er fasst Ketten von Knoten mit nur einem Kind zu einer mit einer Zeichenkette beschrifteten Kante zusammen
  8. 8. D · Ein Stack, der Elemente hält, die noch auf ihre Antwort warten

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