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 wird bei der Darstellung eines Graphen als Adjazenzliste für jeden Knoten gespeichert?

  1. ADie Gesamtzahl der Kanten im Graphen
  2. BEine Zeile aus V booleschen Werten
  3. CDer kürzeste Weg zu jedem anderen Knoten
  4. DEine Liste seiner Nachbarknoten
2.Leicht

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

  1. AWarteschlange (Queue)
  2. BStapel (Stack)
  3. CHashtabelle
  4. DVerkettete Liste
3.Leicht

Die Tiefe eines Knotens in einem Baum ist:

  1. ADie Anzahl der Kindknoten dieses Knotens
  2. BDie Anzahl der Kanten von diesem Knoten bis zum tiefsten Blatt
  3. CDie Anzahl der Knoten in seinem Teilbaum
  4. DDie Anzahl der Kanten von der Wurzel bis zu diesem Knoten
4.Mittel

Was kostet das Einfügen eines Elements in der Mitte eines Arrays mit n Elementen?

  1. AO(1), weil der Index bekannt ist
  2. BO(n²), weil jedes Element n-mal verschoben wird
  3. CO(log n), wegen der binären Suche
  4. DO(n), weil die nachfolgenden Elemente verschoben werden müssen
5.Mittel

Wie findest du den kleinsten Schlüssel in einem binären Suchbaum?

  1. AJedes Blatt besuchen und vergleichen
  2. BVon der Wurzel aus den linken Kindern folgen, bis es kein linkes Kind mehr gibt
  3. CNur die Wurzel ansehen
  4. DVon der Wurzel aus den rechten Kindern folgen, bis es kein rechtes Kind mehr gibt
6.Mittel

In einem binären Min-Heap, der in einem Array gespeichert ist (Index beginnt bei 0), liegen die Kinder des Knotens mit Index i bei:

  1. A2i + 1 und 2i + 2
  2. B2i und 2i + 1
  3. Ci + 1 und i + 2
  4. Di/2 und i/2 + 1
7.Schwer

Welche Garantie geben die Regeln eines Rot-Schwarz-Baums für die Höhe eines Baums mit n Schlüsseln?

  1. ADie Höhe beträgt genau log2 n
  2. BDie Höhe beträgt höchstens n / 2
  3. CDie Höhe beträgt höchstens log2 n + 1
  4. DDie Höhe beträgt höchstens 2 log2(n + 1)
8.Schwer

Warum könnte ein Server seine Hashfunktion zufällig aus einer universellen Familie wählen?

  1. ADamit die Hashtabelle sortiert ist
  2. BDamit es sehr unwahrscheinlich ist, dass ein Angreifer viele Schlüssel wählen kann, die alle kollidieren
  3. CDamit die Tabelle nicht mehr vergrößert werden muss
  4. DUm zu garantieren, dass nie zwei Schlüssel kollidieren, welche Schlüssel ein Angreifer auch sendet

Lösungsschlüssel

  1. 1. D · Eine Liste seiner Nachbarknoten
  2. 2. B · Stapel (Stack)
  3. 3. D · Die Anzahl der Kanten von der Wurzel bis zu diesem Knoten
  4. 4. D · O(n), weil die nachfolgenden Elemente verschoben werden müssen
  5. 5. B · Von der Wurzel aus den linken Kindern folgen, bis es kein linkes Kind mehr gibt
  6. 6. A · 2i + 1 und 2i + 2
  7. 7. D · Die Höhe beträgt höchstens 2 log2(n + 1)
  8. 8. B · Damit es sehr unwahrscheinlich ist, dass ein Angreifer viele Schlüssel wählen kann, die alle kollidieren

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