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. ASortieren, suchen, zurückgeben
  2. BRaten, prüfen, wiederholen
  3. CLesen, berechnen, schreiben
  4. DTeilen, beherrschen, zusammenführen
2.Leicht

Die Platzkomplexität misst:

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

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

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

Wie viele Vergleiche braucht die binäre Suche im Worst Case ungefähr bei einem sortierten Array mit 1,000,000 Elementen?

  1. AEtwa 500,000
  2. BEtwa 20
  3. CEtwa 1,000
  4. DEtwa 100
5.Mittel

Die untere Schranke für vergleichsbasiertes Sortieren im Worst Case ist:

  1. AΩ(n log n)
  2. BΩ(log n)
  3. CΩ(n)
  4. DΩ(n²)
6.Mittel

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

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

Welche Aussage über P und NP ist korrekt?

  1. ALösungen von NP-Problemen lassen sich nicht schnell überprüfen
  2. BEs wurde bewiesen, dass P ≠ NP
  3. CNP bedeutet „nicht polynomiell“
  4. DJedes Problem in P liegt auch in NP
8.Schwer

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

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

Lösungsschlüssel

  1. 1. D · Teilen, beherrschen, zusammenführen
  2. 2. B · Die Menge an Speicher, die ein Algorithmus bei wachsender Eingabe benötigt
  3. 3. C · O(n²)
  4. 4. B · Etwa 20
  5. 5. A · Ω(n log n)
  6. 6. B · O(n)
  7. 7. D · Jedes Problem in P liegt auch in NP
  8. 8. D · Θ(n³)

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