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 Insertionsort im Worst Case?

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

Ein O(n)-Algorithmus braucht für n = 1 Million 3 Sekunden. Wie lange braucht er etwa für n = 2 Millionen?

  1. A3 Sekunden
  2. B9 Sekunden
  3. C6 Sekunden
  4. D12 Sekunden
3.Leicht

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

  1. APolynomiell
  2. BExponentiell
  3. CLinear
  4. DLogarithmisch
4.Mittel

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

  1. AO(n)
  2. BO(n log n)
  3. CO(log n)
  4. DO(n²)
5.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ⁿ)
6.Mittel

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

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

Warum erreicht die binäre Suche auf einer einfach verketteten Liste keine Laufzeit von O(log n)?

  1. ADas Erreichen des mittleren Elements kostet O(n) Schritte, da es keinen direkten Indexzugriff gibt
  2. BDie binäre Suche braucht mindestens doppelt so viel Speicher
  3. CVerkettete Listen können nicht sortiert werden
  4. DVergleiche auf Knoten verketteter Listen sind langsamer
8.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(2n²)
  2. BO(n³)
  3. CO(n!)
  4. DO(n² 2ⁿ)

Lösungsschlüssel

  1. 1. B · O(n²)
  2. 2. C · 6 Sekunden
  3. 3. B · Exponentiell
  4. 4. B · O(n log n)
  5. 5. D · O(2ⁿ)
  6. 6. D · O(log n)
  7. 7. A · Das Erreichen des mittleren Elements kostet O(n) Schritte, da es keinen direkten Indexzugriff gibt
  8. 8. D · O(n² 2ⁿ)

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