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 beschreibt die Worst-Case-Laufzeit eines Algorithmus?

  1. ADie Laufzeit auf einem langsamen Computer
  2. BDie erwartete Laufzeit bei einer zufälligen Eingabe der Größe n
  3. CDie Laufzeit bei der kleinsten Eingabe
  4. DDie maximale Laufzeit über alle Eingaben der Größe n
2.Leicht

Was ist Rekursion?

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

Was beschreibt die Average-Case-Laufzeit?

  1. ADie Laufzeit für eine Eingabe durchschnittlicher Länge
  2. BDie Laufzeit auf dem am weitesten verbreiteten Computer
  3. CDie erwartete Laufzeit bezüglich einer gegebenen Verteilung der Eingaben der Größe n
  4. DDen Mittelwert zwischen den Laufzeiten im Best Case und im Worst Case
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 endet, dann mit den verträglichen wiederholen
  2. BDie Aktivität wählen, die am frühesten beginnt
  3. CZuerst die kürzeste Aktivität wählen
  4. DZuerst die Aktivität mit den wenigsten Überschneidungen wählen, dann mit den verträglichen wiederholen
5.Mittel

Welche Zeitkomplexität hat Quicksort im Worst Case?

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

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

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

Welche Definition der Klasse P ist richtig?

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

Welche Zeitkomplexität hat: for i = 1 to n: for (j = i; j ≤ n; j = j + i) O(1)-Arbeit?

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

Lösungsschlüssel

  1. 1. D · Die maximale Laufzeit über alle Eingaben der Größe n
  2. 2. A · Eine Funktion, die sich selbst mit kleineren Eingaben aufruft
  3. 3. C · Die erwartete Laufzeit bezüglich einer gegebenen Verteilung der Eingaben der Größe n
  4. 4. A · Die Aktivität wählen, die am frühesten endet, dann mit den verträglichen wiederholen
  5. 5. A · O(n²)
  6. 6. A · O(n)
  7. 7. D · Entscheidungsprobleme, die ein deterministischer Algorithmus in polynomieller Zeit löst
  8. 8. B · O(n log n)

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