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

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

  1. AGrößer als der Wert des Knotens
  2. BIn zufälliger Reihenfolge
  3. CGleich dem Wert des Knotens
  4. DKleiner als der Wert des Knotens
2.Leicht

Ein Graph besteht aus:

  1. ANur einer Wurzel und Blättern
  2. BKnoten (Ecken), die durch Kanten verbunden sind
  3. CZeilen und Spalten
  4. DNur Schlüsseln und Hashwerten
3.Leicht

Was ist die Max-Heap-Eigenschaft?

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

Wie viel Speicher benötigt eine Adjazenzliste für einen Graphen mit V Knoten und E Kanten?

  1. AO(E²)
  2. BO(V + E)
  3. CO(V × E)
  4. DO(V²)
5.Mittel

Welche Datenstruktur nutzt ein laufendes Programm, um aktive Funktionsaufrufe und ihre lokalen Variablen zu verwalten?

  1. AEinen binären Suchbaum der Frames
  2. BDen Aufrufstack (Call Stack)
  3. CDie Heap-Speicher-Queue
  4. DEine Hashtabelle der Funktionen
6.Mittel

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

  1. AEbenenweiser Reihenfolge (Level-Order)
  2. BAufsteigend sortierter Reihenfolge
  3. CImmer absteigender Reihenfolge
  4. DEinfügereihenfolge
7.Schwer

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

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

Kahns Algorithmus zur topologischen Sortierung entfernt wiederholt Knoten mit Eingangsgrad 0. Welche Struktur hält diese Knoten?

  1. AEin nach Ausgangsgrad geordneter Max-Heap
  2. BEine Queue (oder beliebige Sammlung) der Knoten mit Eingangsgrad 0
  3. CEin Stack aller besuchten Kanten
  4. DEine Adjazenzmatrix, die festhält, welche Knoten bereits entfernt wurden

Lösungsschlüssel

  1. 1. D · Kleiner als der Wert des Knotens
  2. 2. B · Knoten (Ecken), die durch Kanten verbunden sind
  3. 3. D · Der Schlüssel jedes Elternknotens ist größer oder gleich den Schlüsseln seiner Kinder
  4. 4. B · O(V + E)
  5. 5. B · Den Aufrufstack (Call Stack)
  6. 6. B · Aufsteigend sortierter Reihenfolge
  7. 7. A · Er fasst Ketten von Knoten mit nur einem Kind zu einer mit einer Zeichenkette beschrifteten Kante zusammen
  8. 8. B · Eine Queue (oder beliebige Sammlung) der Knoten mit Eingangsgrad 0

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