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 drei Schritte hat ein Teile-und-herrsche-Algorithmus?

  1. ALesen, berechnen, schreiben
  2. BRaten, prüfen, wiederholen
  3. CTeilen, beherrschen, zusammenführen
  4. DSortieren, suchen, zurückgeben
2.Leicht

Ein Problem heißt in der Regel effizient lösbar (tractable), wenn:

  1. AEs nur durch Ausprobieren aller Möglichkeiten gelöst werden kann
  2. BEs in konstanter Zeit gelöst werden kann
  3. CEs keine Lösung hat
  4. DEs in polynomieller Zeit gelöst werden kann
3.Leicht

Die Platzkomplexität misst:

  1. ADie Anzahl der Codezeilen
  2. BDen Festplattenplatz der Programmdatei nach dem Kompilieren
  3. CDie physische Größe des Computers
  4. DDie Menge an Speicher, die ein Algorithmus bei wachsender Eingabe benötigt
4.Mittel

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

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

Die Zeitkomplexität des naiven rekursiven Fibonacci (fib(n) = fib(n−1) + fib(n−2)) ist:

  1. ALogarithmisch
  2. BExponentiell
  3. CLinear
  4. DKonstant
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

Welche Zeitkomplexität hat: for i = 1 to n: for (j = i; j ≤ n; j = j + i) O(1)-Arbeit?

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

Wie hoch sind die amortisierten Kosten für das Inkrementieren eines Binärzählers, wenn ein einzelnes Inkrement viele Bits umschalten kann?

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

Lösungsschlüssel

  1. 1. C · Teilen, beherrschen, zusammenführen
  2. 2. D · Es in polynomieller Zeit gelöst werden kann
  3. 3. D · Die Menge an Speicher, die ein Algorithmus bei wachsender Eingabe benötigt
  4. 4. D · O(n)
  5. 5. B · Exponentiell
  6. 6. B · O(n²)
  7. 7. A · O(n log n)
  8. 8. D · O(1) pro Inkrement

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