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 das Finden des größten Werts in einem unsortierten Array mit n Zahlen?

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

Eine Schleife beginnt mit i = 1 und verdoppelt i in jeder Iteration, bis i > n ist. Wie viele Iterationen durchläuft sie?

  1. AEtwa n²
  2. BEtwa n
  3. CEtwa n / 2
  4. DEtwa log₂ n
3.Leicht

Ein O(n²)-Algorithmus braucht für n = 1000 eine Sekunde. Wie lange braucht er etwa für n = 2000?

  1. A4 Sekunden
  2. B8 Sekunden
  3. C2 Sekunden
  4. D1 Sekunde
4.Mittel

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

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

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

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

Wie viel Stack-Speicher braucht eine einfache rekursive Fakultätsfunktion fact(n) = n × fact(n − 1)?

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

Welche Laufzeit hat der Dijkstra-Algorithmus mit einem binären Heap auf einem Graphen mit V Knoten und E Kanten?

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

Ein Problem ist NP-vollständig, wenn es:

  1. AIn NP liegt und sich jedes NP-Problem in Polynomialzeit darauf reduzieren lässt
  2. BAußerhalb von NP liegt, aber schwerer als alle NP-Probleme ist, wie das Halteproblem
  3. CUnmöglich zu lösen ist
  4. DIn Polynomialzeit lösbar ist

Lösungsschlüssel

  1. 1. C · O(n)
  2. 2. D · Etwa log₂ n
  3. 3. A · 4 Sekunden
  4. 4. D · O(V × E)
  5. 5. A · O(log n)
  6. 6. C · O(n)
  7. 7. B · O((V + E) log V)
  8. 8. A · In NP liegt und sich jedes NP-Problem in Polynomialzeit darauf reduzieren lässt

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