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

Ein Graph besteht aus:

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

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

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

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

  1. AQueue
  2. BHashtabelle
  3. CPrioritätswarteschlange
  4. DStack
4.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. BNur die kollidierenden Schlüssel kommen in eine neue Überlaufliste am Ende der Tabelle
  3. CDie ältesten Schlüssel werden gelöscht, um Platz zu schaffen
  4. DEine größere Tabelle wird angelegt und jeder Schlüssel neu eingefügt
5.Mittel

Warum ist das Durchlaufen eines Arrays in der Praxis oft viel schneller als das einer gleich langen verketteten Liste?

  1. AArray-Elemente liegen zusammenhängend und nutzen daher den CPU-Cache gut aus
  2. BArrays brauchen weniger Instruktionen zum Vergleichen von Werten
  3. CVerkettete Listen speichern Elemente immer auf der Festplatte
  4. DDas Durchlaufen eines Arrays ist insgesamt O(1), das einer verketteten Liste O(n)
6.Mittel

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

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

Ein Segmentbaum (Segment Tree) wird typischerweise verwendet, um:

  1. AZeichenketten alphabetisch zu sortieren, indem jedes Präfix in einem eigenen Baumknoten gespeichert wird
  2. BBereichsabfragen (z. B. Bereichssummen) und Aktualisierungen in O(log n) zu beantworten
  3. CDie Kanten eines Graphen zu speichern
  4. DEinen Stack zu implementieren
8.Schwer

Im BST mit Wurzel 50, linkem Teilbaum 30 (Kinder 20, 40) und rechtem Teilbaum 70 (Kinder 60, 80) wird die Wurzel mithilfe des In-Order-Nachfolgers gelöscht. Welcher Schlüssel wird die neue Wurzel?

  1. A40
  2. B60
  3. C80
  4. D70

Lösungsschlüssel

  1. 1. D · Knoten (Ecken), die durch Kanten verbunden sind
  2. 2. D · Sie gibt das oberste Element zurück, ohne es zu entfernen
  3. 3. A · Queue
  4. 4. D · Eine größere Tabelle wird angelegt und jeder Schlüssel neu eingefügt
  5. 5. A · Array-Elemente liegen zusammenhängend und nutzen daher den CPU-Cache gut aus
  6. 6. B · O(n), weil die nachfolgenden Elemente verschoben werden müssen
  7. 7. B · Bereichsabfragen (z. B. Bereichssummen) und Aktualisierungen in O(log n) zu beantworten
  8. 8. B · 60

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