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 die lineare Suche in einem unsortierten Array mit n Elementen (Worst Case)?

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

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

  1. APolynomiell
  2. BLinear
  3. CExponentiell
  4. DLogarithmisch
3.Leicht

Welche Notation beschreibt eine untere Schranke für das Wachstum?

  1. Ao (Klein-o)
  2. BΩ (Groß-Omega)
  3. CΘ (Groß-Theta)
  4. DO (Groß-O)
4.Mittel

Ist es richtig zu sagen, dass ein O(n²)-Algorithmus auch O(n³) ist?

  1. AJa, denn Groß-O ist eine obere Schranke, und n² wächst nicht schneller als n³
  2. BNein, denn n³ ist für große n kleiner als n²
  3. CJa, aber nur wenn n kleiner als 100 ist
  4. DNein, denn Groß-O muss stets die genaue Wachstumsrate der Funktion angeben
5.Mittel

Wie baut der Algorithmus von Prim einen minimalen Spannbaum auf?

  1. AEr sortiert alle Kanten nach Gewicht und fügt jede hinzu, sofern sie im Wald keinen Kreis bildet
  2. BEr entfernt die teuerste Kante, bis keine Kreise mehr übrig sind
  3. CEr führt eine Breitensuche aus und behält den BFS-Baum
  4. DEr lässt einen Baum von einem Startknoten aus wachsen und fügt die günstigste Kante hinzu, die den Baum verlässt
6.Mittel

Welche Zeitkomplexität hat die Berechnung der n-ten Fibonacci-Zahl mit einer Bottom-up-Tabelle?

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

Das 0/1-Rucksackproblem benötigt mit dynamischer Programmierung O(nW) Zeit. Warum nennt man das pseudopolynomiell?

  1. AWeil n immer klein ist
  2. BWeil er nur für W = 0 funktioniert
  3. CW ist eine Zahl, daher ist die Laufzeit exponentiell in der Anzahl der Bits, mit denen W geschrieben wird
  4. DWeil der Algorithmus randomisiert ist und seine Laufzeit je nach Eingabe schwankt
8.Schwer

Nach dem Master-Theorem hat T(n) = 8T(n/2) + O(n²) die Lösung:

  1. AΘ(n³)
  2. BΘ(n log n)
  3. CΘ(n²)
  4. DΘ(n² log n)

Lösungsschlüssel

  1. 1. A · O(n)
  2. 2. C · Exponentiell
  3. 3. B · Ω (Groß-Omega)
  4. 4. A · Ja, denn Groß-O ist eine obere Schranke, und n² wächst nicht schneller als n³
  5. 5. D · Er lässt einen Baum von einem Startknoten aus wachsen und fügt die günstigste Kante hinzu, die den Baum verlässt
  6. 6. D · O(n)
  7. 7. C · W ist eine Zahl, daher ist die Laufzeit exponentiell in der Anzahl der Bits, mit denen W geschrieben wird
  8. 8. A · Θ(n³)

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