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

Was ist log₂ 1024?

  1. A10
  2. B12
  3. C32
  4. D512
2.Leicht

Was setzt die binäre Suche bei ihrer Eingabe voraus?

  1. ADas Array darf höchstens 1000 Elemente haben
  2. BDie Länge des Arrays muss eine Zweierpotenz sein
  3. CDas Array muss sortiert sein
  4. DDas Array darf nur positive Zahlen enthalten
3.Leicht

Welche dieser Laufzeiten ist polynomiell?

  1. AO(nⁿ)
  2. BO(n!)
  3. CO(n³)
  4. DO(2ⁿ)
4.Mittel

Welche Zeitkomplexität hat der Bellman-Ford-Algorithmus auf einem Graphen mit V Knoten und E Kanten?

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

Wie viel Stack-Speicher braucht eine einfache rekursive Fakultätsfunktion fact(n) = n × fact(n − 1)?

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

Welche Zeit- und Speicherkosten hat die Berechnung der n-ten Fibonacci-Zahl mit einer Schleife, die nur die letzten beiden Werte behält?

  1. AO(n) Zeit und O(1) Speicher
  2. BO(log n) Zeit und O(n) Speicher
  3. CO(2ⁿ) Zeit und O(1) Speicher
  4. DO(n) Zeit und O(n) Speicher
8.Schwer

Was ist die Lösung der Rekursionsgleichung T(n) = 2T(n/2) + n log n?

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

Lösungsschlüssel

  1. 1. A · 10
  2. 2. C · Das Array muss sortiert sein
  3. 3. C · O(n³)
  4. 4. C · O(V × E)
  5. 5. D · O(n)
  6. 6. B · O(n)
  7. 7. A · O(n) Zeit und O(1) Speicher
  8. 8. D · Θ(n log² n)

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