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

Welcher Sortieralgorithmus vertauscht wiederholt benachbarte Elemente, die in der falschen Reihenfolge stehen?

  1. AMergesort
  2. BBubblesort
  3. CQuicksort
  4. DHeapsort
2.Leicht

Welche Zeitkomplexität hat Mergesort im Worst Case?

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

Was bedeutet f(n) = Θ(g(n))?

  1. Af wächst echt langsamer als g
  2. Bf wächst echt schneller als g
  3. Cf wächst gleich schnell wie g, nach oben und unten durch konstante Vielfache von g beschränkt
  4. Df ist für jedes n immer kleiner als g, also beschränkt g es nach oben, aber nie nach unten
4.Mittel

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

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

Wie viele Münzen verwendet bei Münzen zu 1, 3 und 4 und einem Betrag von 6 die gierige Methode „größte Münze zuerst" im Vergleich zum Optimum?

  1. AGreedy braucht 2 Münzen; das Optimum ist 2
  2. BGreedy braucht 4 Münzen; das Optimum ist 3
  3. CGreedy braucht 3 Münzen; das Optimum ist 2
  4. DGreedy braucht 3 Münzen; das Optimum ist 3
6.Mittel

Warum bringt dynamische Programmierung bei Mergesort keine echte Beschleunigung?

  1. AMergesort ist bereits O(n)
  2. BDynamische Programmierung funktioniert nur bei Graphenproblemen, nicht bei Arrays
  3. CSeine Teilprobleme überlappen sich nicht, also gibt es nichts wiederzuverwenden
  4. DMergesort hat keine rekursive Struktur
7.Schwer

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

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

Die Karatsuba-Multiplikation erfüllt T(n) = 3T(n/2) + O(n). Was ist die Lösung?

  1. AΘ(n log n)
  2. BΘ(nlog₂ 3), etwa n1,585
  3. CΘ(n²)
  4. DΘ(n3)

Lösungsschlüssel

  1. 1. B · Bubblesort
  2. 2. D · O(n log n)
  3. 3. C · f wächst gleich schnell wie g, nach oben und unten durch konstante Vielfache von g beschränkt
  4. 4. B · O(log n)
  5. 5. C · Greedy braucht 3 Münzen; das Optimum ist 2
  6. 6. C · Seine Teilprobleme überlappen sich nicht, also gibt es nichts wiederzuverwenden
  7. 7. D · Beim fraktionalen Rucksackproblem, bei dem Gegenstände geteilt werden dürfen
  8. 8. B · Θ(nlog₂ 3), etwa n1,585

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