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

Was bedeutet es, wenn eine Operation in O(1) Zeit läuft?

  1. ASie verarbeitet genau ein Element pro Sekunde Laufzeit
  2. BSie dauert immer genau eine Sekunde
  3. CIhre Laufzeit wächst nicht mit der Eingabegröße
  4. DSie kann nur einmal ausgeführt werden
2.Leicht

Was ist ein Brute-Force-Algorithmus?

  1. AEiner, der alle möglichen Lösungskandidaten ausprobiert
  2. BEiner, der eine Antwort zufällig rät
  3. CEiner, der auf vielen Prozessoren läuft
  4. DEiner, der immer Rekursion verwendet
3.Leicht

Wie nennt man ein Wachstum von O(2ⁿ)?

  1. ALinear
  2. BExponentiell
  3. CPolynomiell
  4. DLogarithmisch
4.Mittel

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

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

Welche Zeitkomplexität hat: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Welche Zeitkomplexität hat der Bellman-Ford-Algorithmus auf einem Graphen mit V Knoten und E Kanten?

  1. AO(V + E)
  2. BO(V³ × E)
  3. CO(E log V)
  4. DO(V × E)
7.Schwer

Die Karatsuba-Multiplikation erfüllt T(n) = 3T(n/2) + O(n). Was ist die Lösung?

  1. AΘ(n3)
  2. BΘ(n²)
  3. CΘ(n log n)
  4. DΘ(nlog₂ 3), etwa n1,585
8.Schwer

Welche Zeit- und Speicherkosten hat die Berechnung der n-ten Fibonacci-Zahl mit einer Schleife, die nur die letzten beiden Werte behält?

  1. AO(log n) Zeit und O(n) Speicher
  2. BO(2ⁿ) Zeit und O(1) Speicher
  3. CO(n) Zeit und O(1) Speicher
  4. DO(n) Zeit und O(n) Speicher

Lösungsschlüssel

  1. 1. C · Ihre Laufzeit wächst nicht mit der Eingabegröße
  2. 2. A · Einer, der alle möglichen Lösungskandidaten ausprobiert
  3. 3. B · Exponentiell
  4. 4. C · Ω(n log n)
  5. 5. C · O(n log n)
  6. 6. D · O(V × E)
  7. 7. D · Θ(nlog₂ 3), etwa n1,585
  8. 8. C · O(n) Zeit und O(1) Speicher

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