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

Ein Algorithmus mit zwei verschachtelten Schleifen, die jeweils n-mal durchlaufen werden, hat typischerweise welche Komplexität?

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

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

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

Was ist log₂ 1024?

  1. A32
  2. B10
  3. C512
  4. D12
4.Mittel

Wie viele Ebenen hat die Rekursion von Mergesort bei einem Array mit n Elementen?

  1. AEtwa n / 2
  2. BEtwa n
  3. CEtwa √n
  4. DEtwa log₂ n
5.Mittel

Welche Aussage über eine rekursive Funktion ohne erreichbaren Basisfall ist richtig?

  1. ASie läuft in O(1) Zeit
  2. BSie ruft sich immer weiter selbst auf, bis der Aufrufstack überläuft
  3. CSie gibt automatisch 0 zurück
  4. DDer Compiler wandelt sie immer in eine Schleife um, die sicher endet
6.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²)
7.Schwer

Nach dem Master-Theorem hat T(n) = 8T(n/2) + O(n²) die Lösung:

  1. AΘ(n³)
  2. BΘ(n² log n)
  3. CΘ(n log n)
  4. DΘ(n²)
8.Schwer

Das 0/1-Rucksackproblem benötigt mit dynamischer Programmierung O(nW) Zeit. Warum nennt man das pseudopolynomiell?

  1. AWeil er nur für W = 0 funktioniert
  2. BW ist eine Zahl, daher ist die Laufzeit exponentiell in der Anzahl der Bits, mit denen W geschrieben wird
  3. CWeil der Algorithmus randomisiert ist und seine Laufzeit je nach Eingabe schwankt
  4. DWeil n immer klein ist

Lösungsschlüssel

  1. 1. D · O(n²)
  2. 2. B · Ihre Laufzeit wächst nicht mit der Eingabegröße
  3. 3. B · 10
  4. 4. D · Etwa log₂ n
  5. 5. B · Sie ruft sich immer weiter selbst auf, bis der Aufrufstack überläuft
  6. 6. B · Ω(n log n)
  7. 7. A · Θ(n³)
  8. 8. B · W ist eine Zahl, daher ist die Laufzeit exponentiell in der Anzahl der Bits, mit denen W geschrieben wird

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