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 Komplexitätsklasse wächst für große n am schnellsten?

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

Die Laufzeit eines Algorithmus ist O(n). Wie nennt man dieses Wachstum?

  1. AQuadratisch
  2. BLogarithmisch
  3. CKonstant
  4. DLinear
3.Leicht

Welche Zeitkomplexität hat die Tiefensuche auf einem Graphen, der als Adjazenzlisten gespeichert ist?

  1. AO(V + E)
  2. BO(V × E)
  3. CO(V²)
  4. DO(E log V)
4.Mittel

In einem sortierten Array suchst du zwei Elemente mit einer Zielsumme, indem du von jedem Ende einen Zeiger nach innen bewegst. Welche Zeitkomplexität hat das?

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

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

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

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

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

Liegt 22n in O(2ⁿ)?

  1. ANein, denn 22n wächst langsamer als 2ⁿ
  2. BJa, denn beide sind exponentiell
  3. CNein, denn 22n = 4ⁿ und 4ⁿ / 2ⁿ = 2ⁿ wächst unbeschränkt
  4. DJa, denn konstante Faktoren im Exponenten werden in der Groß-O-Notation immer ignoriert
8.Schwer

Welcher Algorithmus findet einen minimalen Spannbaum, indem er wiederholt die günstigste Kante hinzufügt, die keinen Zyklus bildet?

  1. ADijkstra-Algorithmus
  2. BKruskal-Algorithmus
  3. CFloyd-Warshall
  4. DPrim-Algorithmus, ausgehend von einem Knoten

Lösungsschlüssel

  1. 1. B · O(2ⁿ)
  2. 2. D · Linear
  3. 3. A · O(V + E)
  4. 4. C · O(n)
  5. 5. D · Ω(n log n)
  6. 6. C · O(n)
  7. 7. C · Nein, denn 22n = 4ⁿ und 4ⁿ / 2ⁿ = 2ⁿ wächst unbeschränkt
  8. 8. B · Kruskal-Algorithmus

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