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 lineare Suche in einem unsortierten Array mit n Elementen (Worst Case)?

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

Was setzt die binäre Suche bei ihrer Eingabe voraus?

  1. ADas Array darf nur positive Zahlen enthalten
  2. BDie Länge des Arrays muss eine Zweierpotenz sein
  3. CDas Array darf höchstens 1000 Elemente haben
  4. DDas Array muss sortiert sein
3.Leicht

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

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

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

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

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

  1. ABellman-Ford ist in allen Fällen erforderlich
  2. BKruskal-Algorithmus
  3. CTiefensuche (DFS)
  4. DDijkstra-Algorithmus
6.Mittel

Die Breitensuche (BFS) auf einem ungewichteten Graphen findet:

  1. ADen minimalen Spannbaum
  2. BEine topologische Sortierung in allen Graphen
  3. CKürzeste Wege in Graphen mit negativen Kantengewichten
  4. DKürzeste Wege, gemessen in der Anzahl der Kanten vom Startknoten
7.Schwer

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

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

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

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

Lösungsschlüssel

  1. 1. D · O(n)
  2. 2. D · Das Array muss sortiert sein
  3. 3. B · O(log n)
  4. 4. B · O(n²)
  5. 5. D · Dijkstra-Algorithmus
  6. 6. D · Kürzeste Wege, gemessen in der Anzahl der Kanten vom Startknoten
  7. 7. B · Nein, die untere Schranke gilt für den Worst Case über alle Eingaben, nicht für jede Eingabe
  8. 8. A · Θ(n³)

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