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

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

  1. AVerkettete Liste
  2. BWarteschlange (Queue)
  3. CStapel (Stack)
  4. DHashtabelle
2.Leicht

Was speichert eine Map (Dictionary)?

  1. ASchlüssel-Wert-Paare mit eindeutigen Schlüsseln
  2. BNach Größe sortierte Werte
  3. CNur Werte in Einfügereihenfolge
  4. DPaare gleicher Schlüssel
3.Leicht

Was wird bei der Darstellung eines Graphen als Adjazenzliste für jeden Knoten gespeichert?

  1. ADer kürzeste Weg zu jedem anderen Knoten
  2. BEine Zeile aus V booleschen Werten
  3. CDie Gesamtzahl der Kanten im Graphen
  4. DEine Liste seiner Nachbarknoten
4.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(1), weil der Index bekannt ist
  3. CO(n), weil die nachfolgenden Elemente verschoben werden müssen
  4. DO(log n), wegen der binären Suche
5.Mittel

Welchen Wert hat der Postfix-Ausdruck 3 4 + 2 * ?

  1. A11
  2. B14
  3. C10
  4. D24
6.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. BEine größere Tabelle wird angelegt und jeder Schlüssel neu eingefügt
  3. CNur die kollidierenden Schlüssel kommen in eine neue Überlaufliste am Ende der Tabelle
  4. DDie ältesten Schlüssel werden gelöscht, um Platz zu schaffen
7.Schwer

Ein Bloom-Filter kann die Frage „Ist dieses Element in der Menge?“ beantworten mit:

  1. AMöglichen falsch-positiven, aber keinen falsch-negativen Ergebnissen
  2. BImmer exakten Antworten
  3. CMöglichen falsch-negativen, aber keinen falsch-positiven Ergebnissen
  4. DAntworten nur für Zahlen
8.Schwer

Wie hoch ist unter der Annahme des einfachen gleichverteilten Hashings die erwartete Suchzeit in einer Hashtabelle mit Chaining, n Schlüsseln und m Buckets?

  1. AO(n)
  2. BO(log n)
  3. CO(1 + α), wobei α = n / m
  4. DO(m)

Lösungsschlüssel

  1. 1. C · Stapel (Stack)
  2. 2. A · Schlüssel-Wert-Paare mit eindeutigen Schlüsseln
  3. 3. D · Eine Liste seiner Nachbarknoten
  4. 4. C · O(n), weil die nachfolgenden Elemente verschoben werden müssen
  5. 5. B · 14
  6. 6. B · Eine größere Tabelle wird angelegt und jeder Schlüssel neu eingefügt
  7. 7. A · Möglichen falsch-positiven, aber keinen falsch-negativen Ergebnissen
  8. 8. C · O(1 + α), wobei α = n / m

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