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

Die Laufzeit eines Algorithmus ist O(n). Wie nennt man dieses Wachstum?

  1. AKonstant
  2. BLogarithmisch
  3. CLinear
  4. DQuadratisch
2.Leicht

Wie viel zusätzlichen Speicher braucht ein üblicher arraybasierter Mergesort?

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

Welche dieser Laufzeiten ist polynomiell?

  1. AO(n³)
  2. BO(n!)
  3. CO(2ⁿ)
  4. DO(nⁿ)
4.Mittel

In einem sortierten Array suchst du zwei Elemente mit einer Zielsumme, indem du von jedem Ende einen Zeiger nach innen bewegst. Welche Zeitkomplexität hat das?

  1. AO(n²)
  2. BO(n)
  3. CO(n log n)
  4. DO(log 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 3 Münzen; das Optimum ist 3
  2. BGreedy braucht 3 Münzen; das Optimum ist 2
  3. CGreedy braucht 2 Münzen; das Optimum ist 2
  4. DGreedy braucht 4 Münzen; das Optimum ist 3
6.Mittel

Welche Zeitkomplexität hat die Berechnung der n-ten Fibonacci-Zahl mit einer Bottom-up-Tabelle?

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

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

  1. AΘ(n²)
  2. BΘ(n log n)
  3. CΘ(n)
  4. DΘ(n log² n)
8.Schwer

Warum kann der Dijkstra-Algorithmus falsche Ergebnisse liefern, wenn einige Kantengewichte negativ sind?

  1. ANegative Zahlen können nicht in einer Prioritätswarteschlange gespeichert werden
  2. BEin Knoten wird beim Entnehmen endgültig festgelegt, aber eine spätere negative Kante könnte ihm noch einen kürzeren Weg geben
  3. CEr gerät bei jeder negativen Kante in eine Endlosschleife
  4. DEr funktioniert nur auf ungerichteten Graphen

Lösungsschlüssel

  1. 1. C · Linear
  2. 2. C · O(n)
  3. 3. A · O(n³)
  4. 4. B · O(n)
  5. 5. B · Greedy braucht 3 Münzen; das Optimum ist 2
  6. 6. A · O(n)
  7. 7. D · Θ(n log² n)
  8. 8. B · Ein Knoten wird beim Entnehmen endgültig festgelegt, aber eine spätere negative Kante könnte ihm noch einen kürzeren Weg geben

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