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

Wie funktioniert Selectionsort?

  1. AEs fügt jedes Element durch Verschieben in einen wachsenden sortierten Teil ein
  2. BEs sucht wiederholt das Minimum des unsortierten Teils und tauscht es nach vorn
  3. CEs teilt das Array in Hälften und führt sie zusammen
  4. DEs vertauscht wiederholt benachbarte Elemente, die in falscher Reihenfolge stehen
2.Leicht

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

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

Ein O(n²)-Algorithmus braucht für n = 1000 eine Sekunde. Wie lange braucht er etwa für n = 2000?

  1. A1 Sekunde
  2. B8 Sekunden
  3. C4 Sekunden
  4. D2 Sekunden
4.Mittel

Die untere Schranke für vergleichsbasiertes Sortieren im Worst Case ist:

  1. AΩ(log n)
  2. BΩ(n²)
  3. CΩ(n log n)
  4. DΩ(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

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

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

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

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

Was würde folgen, wenn jemand einen Polynomialzeitalgorithmus für ein NP-vollständiges Problem fände?

  1. AJedes Problem in NP wäre in polynomieller Zeit lösbar, also P = NP
  2. BAlle Algorithmen mit exponentieller Laufzeit würden sofort in linearer Zeit laufen
  3. CNur dieses eine Problem würde nach P wandern
  4. DDas Halteproblem würde entscheidbar

Lösungsschlüssel

  1. 1. B · Es sucht wiederholt das Minimum des unsortierten Teils und tauscht es nach vorn
  2. 2. A · O(n)
  3. 3. C · 4 Sekunden
  4. 4. C · Ω(n log n)
  5. 5. B · Greedy braucht 3 Münzen; das Optimum ist 2
  6. 6. B · O(log n)
  7. 7. A · Ein Knoten wird beim Entnehmen endgültig festgelegt, aber eine spätere negative Kante könnte ihm noch einen kürzeren Weg geben
  8. 8. A · Jedes Problem in NP wäre in polynomieller Zeit lösbar, also P = NP

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