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 Average-Case-Laufzeit?

  1. ADen Mittelwert zwischen den Laufzeiten im Best Case und im Worst Case
  2. BDie Laufzeit auf dem am weitesten verbreiteten Computer
  3. CDie Laufzeit für eine Eingabe durchschnittlicher Länge
  4. DDie erwartete Laufzeit bezüglich einer gegebenen Verteilung der Eingaben der Größe n
2.Leicht

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

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

Welche Zeitkomplexität hat die lineare Suche in einem unsortierten Array mit n Elementen (Worst Case)?

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

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

  1. AZuerst die kürzeste Aktivität wählen
  2. BZuerst die Aktivität mit den wenigsten Überschneidungen wählen, dann mit den verträglichen wiederholen
  3. CDie Aktivität wählen, die am frühesten beginnt
  4. DDie Aktivität wählen, die am frühesten endet, dann mit den verträglichen wiederholen
5.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(log n)
  2. BO(n²)
  3. CO(n)
  4. DO(2ⁿ)
6.Mittel

Was bedeutet es, dass ein Problem optimale Teilstruktur hat?

  1. ADas Problem hat genau eine optimale Lösung, die jedes Teilproblem teilt
  2. BJedes Teilproblem hat dieselbe Größe
  3. CDas Problem kann in konstanter Zeit gelöst werden
  4. DEine optimale Lösung lässt sich aus optimalen Lösungen seiner Teilprobleme zusammensetzen
7.Schwer

Wie erkennt der Bellman-Ford-Algorithmus einen vom Startknoten erreichbaren Kreis mit negativem Gewicht?

  1. ANach V − 1 Runden prüft er, ob sich noch eine Kante relaxieren lässt
  2. BEr prüft, ob irgendeine Kante ein negatives Gewicht hat
  3. CEr zählt die Kreise mit einer Tiefensuche
  4. DEr führt den Dijkstra-Algorithmus zweimal aus und vergleicht die beiden Distanzergebnisse
8.Schwer

Welche Definition der Klasse NP ist richtig?

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

Lösungsschlüssel

  1. 1. D · Die erwartete Laufzeit bezüglich einer gegebenen Verteilung der Eingaben der Größe n
  2. 2. B · Das Array muss sortiert sein
  3. 3. C · O(n)
  4. 4. D · Die Aktivität wählen, die am frühesten endet, dann mit den verträglichen wiederholen
  5. 5. C · O(n)
  6. 6. D · Eine optimale Lösung lässt sich aus optimalen Lösungen seiner Teilprobleme zusammensetzen
  7. 7. A · Nach V − 1 Runden prüft er, ob sich noch eine Kante relaxieren lässt
  8. 8. A · Entscheidungsprobleme, deren Ja-Antworten mithilfe eines Zertifikats in polynomieller Zeit überprüft werden können

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