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 enthält jeder Knoten einer doppelt verketteten Liste?

  1. ADaten und zwei Zeiger, einen auf den nächsten Knoten und einen auf den Knoten danach
  2. BZwei Kopien der Daten und einen Zeiger
  3. CDaten, einen Zeiger auf den nächsten Knoten und einen Zeiger auf den vorherigen Knoten
  4. DDaten und nur einen Zeiger auf den nächsten Knoten
2.Leicht

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

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

Was sind Geschwisterknoten in einem Baum?

  1. AKnoten ohne Kindknoten
  2. BKnoten in gleicher Tiefe in verschiedenen Teilbäumen
  3. CEin Knoten und sein Elternknoten
  4. DKnoten mit demselben Elternknoten
4.Mittel

Wie wird ein neues Element in einen binären Heap eingefügt?

  1. AIn die Wurzel setzen und nach unten wandern lassen
  2. BDen ganzen Heap von Grund auf neu aufbauen
  3. CAns Ende des Arrays setzen und nach oben wandern lassen (sift-up), solange es die Heap-Eigenschaft verletzt
  4. DAn der sortierten Position einfügen, indem alle größeren Elemente um eine Stelle nach rechts verschoben werden
5.Mittel

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

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

Wie lange dauert es, mit einer Adjazenzmatrix zu prüfen, ob die Kante (u, v) existiert?

  1. AO(1)
  2. BO(V)
  3. CO(log V)
  4. DO(E)
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 höchstens log2 n + 1
  2. BDie Höhe beträgt genau log2 n
  3. CDie Höhe beträgt höchstens n / 2
  4. DDie Höhe beträgt höchstens 2 log2(n + 1)
8.Schwer

In einem Ringpuffer kann front == rear entweder leer oder voll bedeuten. Wie unterscheidet man das üblicherweise?

  1. AFront und rear in derselben Variablen speichern
  2. BDie Puffergröße zu einer Zweierpotenz machen
  3. CDen Puffer immer leeren, wenn front gleich rear ist, sodass der Zustand leer ist
  4. DEinen separaten Elementzähler führen oder immer einen Platz frei lassen

Lösungsschlüssel

  1. 1. C · Daten, einen Zeiger auf den nächsten Knoten und einen Zeiger auf den vorherigen Knoten
  2. 2. B · Sie gibt das oberste Element zurück, ohne es zu entfernen
  3. 3. D · Knoten mit demselben Elternknoten
  4. 4. C · Ans Ende des Arrays setzen und nach oben wandern lassen (sift-up), solange es die Heap-Eigenschaft verletzt
  5. 5. A · O(V + E)
  6. 6. A · O(1)
  7. 7. D · Die Höhe beträgt höchstens 2 log2(n + 1)
  8. 8. D · Einen separaten Elementzähler führen oder immer einen Platz frei lassen

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