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 Laufzeit hat Countingsort für n ganze Zahlen im Bereich 0 bis k?

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

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

  1. AQuadratisch
  2. BLogarithmisch
  3. CKonstant
  4. DLinear
3.Leicht

Welche dieser Funktionen wächst für große n am langsamsten?

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

Warum wechseln viele Sortierroutinen in Bibliotheken bei sehr kleinen Teilarrays zu Insertionsort?

  1. AInsertionsort braucht bei großen Eingaben weniger Speicher als jeder andere Sortieralgorithmus
  2. BInsertionsort ist im Worst Case O(n log n)
  3. CInsertionsort hat wenig Overhead und ist bei kleinen oder fast sortierten Eingaben schnell
  4. DRekursive Algorithmen können Arrays mit weniger als 10 Elementen nicht verarbeiten
5.Mittel

Welcher Algorithmus findet die kürzesten Wege von einem Startknoten in einem Graphen mit nichtnegativen Kantengewichten?

  1. AKruskal-Algorithmus
  2. BDijkstra-Algorithmus
  3. CTiefensuche (DFS)
  4. DBellman-Ford ist in allen Fällen erforderlich
6.Mittel

Welche Zeitkomplexität hat der Bellman-Ford-Algorithmus auf einem Graphen mit V Knoten und E Kanten?

  1. AO(E log V)
  2. BO(V × E)
  3. CO(V³ × E)
  4. DO(V + E)
7.Schwer

Nach dem Master-Theorem hat T(n) = 8T(n/2) + O(n²) die Lösung:

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

Warum ist eine Suche in einer Hashtabelle im Durchschnitt O(1), im Worst Case aber O(n)?

  1. ASchlüssel müssen zuerst sortiert werden
  2. BViele Schlüssel können im selben Bucket kollidieren
  3. CArrays haben O(n) Zugriffszeit
  4. DHashfunktionen sind langsam

Lösungsschlüssel

  1. 1. B · O(n + k)
  2. 2. D · Linear
  3. 3. C · O(log n)
  4. 4. C · Insertionsort hat wenig Overhead und ist bei kleinen oder fast sortierten Eingaben schnell
  5. 5. B · Dijkstra-Algorithmus
  6. 6. B · O(V × E)
  7. 7. A · Θ(n³)
  8. 8. B · Viele Schlüssel können im selben Bucket kollidieren

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