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 Notation beschreibt eine obere Schranke für das Wachstum?

  1. AGroß-O (Big O)
  2. BGroß-Omega (Big Omega)
  3. CGroß-Theta (Big Theta)
  4. DKlein-Omega (Little omega)
2.Leicht

Was beschreibt die Worst-Case-Laufzeit eines Algorithmus?

  1. ADie erwartete Laufzeit bei einer zufälligen Eingabe der Größe n
  2. BDie Laufzeit bei der kleinsten Eingabe
  3. CDie maximale Laufzeit über alle Eingaben der Größe n
  4. DDie Laufzeit auf einem langsamen Computer
3.Leicht

Welche Laufzeit hat Countingsort für n ganze Zahlen im Bereich 0 bis k?

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

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

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

Was misst die amortisierte Analyse?

  1. ADie erwarteten Kosten über zufällige Eingaben
  2. BDie Kosten der einzelnen teuersten Operation irgendwo in der Folge
  3. CDie Kosten eines Algorithmus bei der besten Eingabe
  4. DDie durchschnittlichen Kosten pro Operation über eine Worst-Case-Folge von Operationen
6.Mittel

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

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

Welche Aussage über die Klein-o-Notation ist richtig?

  1. An = o(n), da jede Funktion Klein-o von sich selbst ist
  2. B2n = o(n), weil 2n langsam wächst
  3. Cn² = o(n)
  4. Dn = o(n²), aber n ist nicht o(n)
8.Schwer

Warum kann der Dijkstra-Algorithmus falsche Ergebnisse liefern, wenn einige Kantengewichte negativ sind?

  1. ANegative Zahlen können nicht in einer Prioritätswarteschlange gespeichert werden
  2. BEr funktioniert nur auf ungerichteten Graphen
  3. CEin Knoten wird beim Entnehmen endgültig festgelegt, aber eine spätere negative Kante könnte ihm noch einen kürzeren Weg geben
  4. DEr gerät bei jeder negativen Kante in eine Endlosschleife

Lösungsschlüssel

  1. 1. A · Groß-O (Big O)
  2. 2. C · Die maximale Laufzeit über alle Eingaben der Größe n
  3. 3. D · O(n + k)
  4. 4. D · O(2ⁿ)
  5. 5. D · Die durchschnittlichen Kosten pro Operation über eine Worst-Case-Folge von Operationen
  6. 6. A · O(n log n)
  7. 7. D · n = o(n²), aber n ist nicht o(n)
  8. 8. C · Ein Knoten wird beim Entnehmen endgültig festgelegt, aber eine spätere negative Kante könnte ihm noch einen kürzeren Weg geben

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