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

Die Laufzeit eines Algorithmus ist O(n). Wie nennt man dieses Wachstum?

  1. AKonstant
  2. BQuadratisch
  3. CLogarithmisch
  4. DLinear
2.Leicht

Welche Zeitkomplexität hat Insertionsort im Best Case, also bei einem bereits sortierten Array?

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

Wie lautet die Groß-O-Klasse von 3n² + 5n + 2?

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

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

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

Welche amortisierte Zeitkomplexität hat das Anhängen an ein dynamisches Array, das seine Kapazität verdoppelt, wenn es voll ist?

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

Welche Zeitkomplexität hat Quicksort im Worst Case?

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

Eine topologische Sortierung ist nur möglich für:

  1. AGerichtete azyklische Graphen (DAG)
  2. BVollständige Graphen
  3. CGraphen mit negativen Gewichten
  4. DUngerichtete Graphen
8.Schwer

Nimmt man beide Endpunkte jeder Kante eines maximalen Matchings, erhält man eine Knotenüberdeckung. Wie gut ist diese Überdeckung?

  1. AHöchstens doppelt so groß wie eine minimale Knotenüberdeckung
  2. BVon unbekannter Güte im Vergleich zum Optimum
  3. CImmer eine minimale Knotenüberdeckung
  4. DHöchstens log n-mal so groß wie das Minimum

Lösungsschlüssel

  1. 1. D · Linear
  2. 2. A · O(n)
  3. 3. A · O(n²)
  4. 4. D · O(log n)
  5. 5. A · O(1)
  6. 6. B · O(n²)
  7. 7. A · Gerichtete azyklische Graphen (DAG)
  8. 8. A · Höchstens doppelt so groß wie eine minimale Knotenüberdeckung

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