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

Was ist Rekursion?

  1. AEine Schleife, die nie endet
  2. BEine Art von Datenstruktur
  3. CEin Sortierverfahren
  4. DEine Funktion, die sich selbst mit kleineren Eingaben aufruft
3.Leicht

Wie lautet die Groß-O-Klasse von 3n² + 5n + 2?

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

Du sortierst ein Array mit n Elementen einmal und beantwortest danach k Enthaltenseinsanfragen mit binärer Suche. Wie hoch sind die Gesamtkosten?

  1. AO(nk)
  2. BO(n log n + k log n)
  3. CO(k n log n)
  4. DO(n + k)
5.Mittel

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

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

Wie viele Ebenen hat die Rekursion von Mergesort bei einem Array mit n Elementen?

  1. AEtwa n / 2
  2. BEtwa √n
  3. CEtwa log₂ n
  4. DEtwa n
7.Schwer

Welche Definition der Klasse NP ist richtig?

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

Bei welcher Variante des Rucksackproblems liefert die Greedy-Regel „Gegenstände nach Wert pro Gewicht nehmen" immer eine optimale Lösung?

  1. ABeim fraktionalen Rucksackproblem, bei dem Gegenstände geteilt werden dürfen
  2. BBei beiden Varianten
  3. CBei keiner der beiden Varianten
  4. DBeim 0/1-Rucksackproblem, bei dem Gegenstände immer ganz genommen werden müssen

Lösungsschlüssel

  1. 1. A · O(n²)
  2. 2. D · Eine Funktion, die sich selbst mit kleineren Eingaben aufruft
  3. 3. C · O(n²)
  4. 4. B · O(n log n + k log n)
  5. 5. A · O(n²)
  6. 6. C · Etwa log₂ n
  7. 7. C · Entscheidungsprobleme, deren Ja-Antworten mithilfe eines Zertifikats in polynomieller Zeit überprüft werden können
  8. 8. A · Beim fraktionalen Rucksackproblem, bei dem Gegenstände geteilt werden dürfen

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