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

Ein O(n²)-Algorithmus braucht für n = 1000 eine Sekunde. Wie lange braucht er etwa für n = 2000?

  1. A2 Sekunden
  2. B4 Sekunden
  3. C8 Sekunden
  4. D1 Sekunde
2.Leicht

Welche Entwurfsstrategie verwendet Mergesort?

  1. ABrute Force
  2. BTeile und herrsche (Divide and Conquer)
  3. CGierige Wahl (Greedy)
  4. DDynamische Programmierung
3.Leicht

Was bedeutet es, wenn eine Operation in O(1) Zeit läuft?

  1. ASie kann nur einmal ausgeführt werden
  2. BSie dauert immer genau eine Sekunde
  3. CIhre Laufzeit wächst nicht mit der Eingabegröße
  4. DSie verarbeitet genau ein Element pro Sekunde Laufzeit
4.Mittel

Welche Greedy-Regel liefert beim Aktivitätsauswahlproblem immer eine maximale Anzahl sich nicht überschneidender Aktivitäten?

  1. ADie Aktivität wählen, die am frühesten beginnt
  2. BDie Aktivität wählen, die am frühesten endet, dann mit den verträglichen wiederholen
  3. CZuerst die Aktivität mit den wenigsten Überschneidungen wählen, dann mit den verträglichen wiederholen
  4. DZuerst die kürzeste Aktivität wählen
5.Mittel

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

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

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

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

Welche Laufzeit hat der Dijkstra-Algorithmus mit einem binären Heap auf einem Graphen mit V Knoten und E Kanten?

  1. AO(V + E)
  2. BO(V³)
  3. CO(V × E)
  4. DO((V + E) log V)
8.Schwer

Welche Definition der Klasse P ist richtig?

  1. AProbleme, die parallel gelöst werden können
  2. BEntscheidungsprobleme, die ein deterministischer Algorithmus in polynomieller Zeit löst
  3. CProbleme, die auf jedem Computer exponentielle Zeit brauchen
  4. DProbleme, deren Lösungen in polynomieller Zeit geprüft, aber nie gefunden werden können

Lösungsschlüssel

  1. 1. B · 4 Sekunden
  2. 2. B · Teile und herrsche (Divide and Conquer)
  3. 3. C · Ihre Laufzeit wächst nicht mit der Eingabegröße
  4. 4. B · Die Aktivität wählen, die am frühesten endet, dann mit den verträglichen wiederholen
  5. 5. C · O(n²)
  6. 6. B · O(2ⁿ)
  7. 7. D · O((V + E) log V)
  8. 8. B · Entscheidungsprobleme, die ein deterministischer Algorithmus in polynomieller Zeit löst

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