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(log n)
  3. CO(n log n)
  4. DO(n)
2.Leicht

Ein Algorithmus mit zwei verschachtelten Schleifen, die jeweils n-mal durchlaufen werden, hat typischerweise welche Komplexität?

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

Welche Zeitkomplexität hat das Finden des größten Werts in einem unsortierten Array mit n Zahlen?

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

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

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

Wie viele Münzen verwendet bei Münzen zu 1, 3 und 4 und einem Betrag von 6 die gierige Methode „größte Münze zuerst" im Vergleich zum Optimum?

  1. AGreedy braucht 3 Münzen; das Optimum ist 2
  2. BGreedy braucht 4 Münzen; das Optimum ist 3
  3. CGreedy braucht 2 Münzen; das Optimum ist 2
  4. DGreedy braucht 3 Münzen; das Optimum ist 3
6.Mittel

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

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

Die Karatsuba-Multiplikation erfüllt T(n) = 3T(n/2) + O(n). Was ist die Lösung?

  1. AΘ(n3)
  2. BΘ(n log n)
  3. CΘ(n²)
  4. DΘ(nlog₂ 3), etwa n1,585
8.Schwer

Welche Zeit- und Speicherkosten hat die Berechnung der n-ten Fibonacci-Zahl mit einer Schleife, die nur die letzten beiden Werte behält?

  1. AO(n) Zeit und O(n) Speicher
  2. BO(2ⁿ) Zeit und O(1) Speicher
  3. CO(log n) Zeit und O(n) Speicher
  4. DO(n) Zeit und O(1) Speicher

Lösungsschlüssel

  1. 1. A · O(n²)
  2. 2. A · O(n²)
  3. 3. B · O(n)
  4. 4. D · O(n)
  5. 5. A · Greedy braucht 3 Münzen; das Optimum ist 2
  6. 6. C · O(n²)
  7. 7. D · Θ(nlog₂ 3), etwa n1,585
  8. 8. D · O(n) Zeit und O(1) Speicher

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