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

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

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

Welche Zeitkomplexität hat Mergesort im Worst Case?

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

Ein Greedy-Algorithmus:

  1. AProbiert jede mögliche Lösung aus
  2. BVerwendet ausschließlich Rekursion
  3. CLiefert immer die optimale Lösung
  4. DTrifft in jedem Schritt die lokal beste Wahl
5.Mittel

Welche Zeitkomplexität hat die Multiplikation zweier n × n-Matrizen mit der üblichen dreifachen Schleife?

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

Eine Funktion führt eine Schleife mit n Iterationen und danach, getrennt davon, eine weitere Schleife mit n Iterationen aus. Welche Zeitkomplexität hat sie?

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

Welche Definition der Klasse NP ist richtig?

  1. AProbleme, die nicht in polynomieller Zeit gelöst werden können
  2. BProbleme, die kein Algorithmus lösen kann
  3. CEntscheidungsprobleme, deren Ja-Antworten mithilfe eines Zertifikats in polynomieller Zeit überprüft werden können
  4. DProbleme, die nicht polynomiell sind
8.Schwer

Wie wird das Problem des Handlungsreisenden (TSP) eingeordnet?

  1. AEs ist unentscheidbar
  2. BDie Entscheidungsversion ist NP-vollständig, die Optimierungsversion NP-schwer
  3. CDie Entscheidungsversion liegt in P, aber die Optimierungsversion ist NP-vollständig
  4. DEs liegt in P, weil der Dijkstra-Algorithmus es löst, indem er jede Stadt einmal besucht

Lösungsschlüssel

  1. 1. B · O(n²)
  2. 2. A · O(n)
  3. 3. B · O(n log n)
  4. 4. D · Trifft in jedem Schritt die lokal beste Wahl
  5. 5. C · O(n³)
  6. 6. A · O(n)
  7. 7. C · Entscheidungsprobleme, deren Ja-Antworten mithilfe eines Zertifikats in polynomieller Zeit überprüft werden können
  8. 8. B · Die Entscheidungsversion ist NP-vollständig, die Optimierungsversion NP-schwer

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