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 die binäre Suche in einem sortierten Array?

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

Was ist log₂ 1024?

  1. A12
  2. B10
  3. C512
  4. D32
3.Leicht

Welche Notation beschreibt eine obere Schranke für das Wachstum?

  1. AGroß-O (Big O)
  2. BGroß-Omega (Big Omega)
  3. CGroß-Theta (Big Theta)
  4. DKlein-Omega (Little omega)
4.Mittel

Was berechnet der Floyd-Warshall-Algorithmus, und wie schnell?

  1. AEinen minimalen Spannbaum in O(E log V)
  2. BKürzeste Wege von einem Startknoten zu allen anderen in O(V + E)
  3. CKürzeste Wege zwischen allen Knotenpaaren in O(V³)
  4. DEine topologische Sortierung in O(V²)
5.Mittel

Wie viele Vergleiche braucht die binäre Suche im Worst Case ungefähr bei einem sortierten Array mit 1,000,000 Elementen?

  1. AEtwa 1,000
  2. BEtwa 500,000
  3. CEtwa 20
  4. DEtwa 100
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. BEine optimale Lösung lässt sich aus optimalen Lösungen seiner Teilprobleme zusammensetzen
  3. CJedes Teilproblem hat dieselbe Größe
  4. DDas Problem kann in konstanter Zeit gelöst werden
7.Schwer

Warum erreicht die binäre Suche auf einer einfach verketteten Liste keine Laufzeit von O(log n)?

  1. ADie binäre Suche braucht mindestens doppelt so viel Speicher
  2. BDas Erreichen des mittleren Elements kostet O(n) Schritte, da es keinen direkten Indexzugriff gibt
  3. CVerkettete Listen können nicht sortiert werden
  4. DVergleiche auf Knoten verketteter Listen sind langsamer
8.Schwer

Insertionsort läuft bei sortierter Eingabe in O(n). Widerspricht das der unteren Schranke Ω(n log n) für vergleichsbasiertes Sortieren?

  1. AJa, die untere Schranke ist also falsch
  2. BJa, aber nur für Arrays mit weniger als 100 Elementen
  3. CNein, weil Insertionsort kein vergleichsbasiertes Sortierverfahren ist
  4. DNein, die untere Schranke gilt für den Worst Case über alle Eingaben, nicht für jede Eingabe

Lösungsschlüssel

  1. 1. B · O(log n)
  2. 2. B · 10
  3. 3. A · Groß-O (Big O)
  4. 4. C · Kürzeste Wege zwischen allen Knotenpaaren in O(V³)
  5. 5. C · Etwa 20
  6. 6. B · Eine optimale Lösung lässt sich aus optimalen Lösungen seiner Teilprobleme zusammensetzen
  7. 7. B · Das Erreichen des mittleren Elements kostet O(n) Schritte, da es keinen direkten Indexzugriff gibt
  8. 8. D · Nein, die untere Schranke gilt für den Worst Case über alle Eingaben, nicht für jede Eingabe

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