Arbeitsblatt Algorithmen & Komplexität mit Lösungen

Kostenloses Arbeitsblatt Algorithmen & Komplexität 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 Zeitkomplexität hat die Tiefensuche auf einem Graphen, der als Adjazenzlisten gespeichert ist?

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

Der Zugriff auf ein Array-Element über seinen Index benötigt:

  1. AO(1)
  2. BO(n)
  3. CO(n²)
  4. DO(log n)
3.Leicht

Was beschreibt die Average-Case-Laufzeit?

  1. ADie erwartete Laufzeit bezüglich einer gegebenen Verteilung der Eingaben der Größe n
  2. BDie Laufzeit für eine Eingabe durchschnittlicher Länge
  3. CDen Mittelwert zwischen den Laufzeiten im Best Case und im Worst Case
  4. DDie Laufzeit auf dem am weitesten verbreiteten Computer
4.Mittel

Was ist die Lösung der Rekursionsgleichung T(n) = T(n − 1) + O(1)?

  1. AO(n)
  2. BO(2ⁿ)
  3. CO(log n)
  4. DO(n²)
5.Mittel

Die untere Schranke für vergleichsbasiertes Sortieren im Worst Case ist:

  1. AΩ(log n)
  2. BΩ(n log n)
  3. CΩ(n²)
  4. DΩ(n)
6.Mittel

Warum bringt dynamische Programmierung bei Mergesort keine echte Beschleunigung?

  1. AMergesort ist bereits O(n)
  2. BDynamische Programmierung funktioniert nur bei Graphenproblemen, nicht bei Arrays
  3. CMergesort hat keine rekursive Struktur
  4. DSeine Teilprobleme überlappen sich nicht, also gibt es nichts wiederzuverwenden
7.Schwer

Der Held-Karp-Algorithmus der dynamischen Programmierung löst das Problem des Handlungsreisenden exakt. Welche Laufzeit hat er für n Städte?

  1. AO(n² 2ⁿ)
  2. BO(2n²)
  3. CO(n³)
  4. DO(n!)
8.Schwer

Wie erkennt der Bellman-Ford-Algorithmus einen vom Startknoten erreichbaren Kreis mit negativem Gewicht?

  1. ANach V − 1 Runden prüft er, ob sich noch eine Kante relaxieren lässt
  2. BEr prüft, ob irgendeine Kante ein negatives Gewicht hat
  3. CEr zählt die Kreise mit einer Tiefensuche
  4. DEr führt den Dijkstra-Algorithmus zweimal aus und vergleicht die beiden Distanzergebnisse

Lösungsschlüssel

  1. 1. D · O(V + E)
  2. 2. A · O(1)
  3. 3. A · Die erwartete Laufzeit bezüglich einer gegebenen Verteilung der Eingaben der Größe n
  4. 4. A · O(n)
  5. 5. B · Ω(n log n)
  6. 6. D · Seine Teilprobleme überlappen sich nicht, also gibt es nichts wiederzuverwenden
  7. 7. A · O(n² 2ⁿ)
  8. 8. A · Nach V − 1 Runden prüft er, ob sich noch eine Kante relaxieren lässt

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