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 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²)
2.Leicht

Der Zugriff auf ein Array-Element über seinen Index benötigt:

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

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

  1. AHeapsort
  2. BMergesort
  3. CBubblesort
  4. DQuicksort
4.Mittel

Wie baut der Algorithmus von Prim einen minimalen Spannbaum auf?

  1. AEr sortiert alle Kanten nach Gewicht und fügt jede hinzu, sofern sie im Wald keinen Kreis bildet
  2. BEr lässt einen Baum von einem Startknoten aus wachsen und fügt die günstigste Kante hinzu, die den Baum verlässt
  3. CEr entfernt die teuerste Kante, bis keine Kreise mehr übrig sind
  4. DEr führt eine Breitensuche aus und behält den BFS-Baum
5.Mittel

Was misst die amortisierte Analyse?

  1. ADie erwarteten Kosten über zufällige Eingaben
  2. BDie Kosten eines Algorithmus bei der besten Eingabe
  3. CDie Kosten der einzelnen teuersten Operation irgendwo in der Folge
  4. DDie durchschnittlichen Kosten pro Operation über eine Worst-Case-Folge von Operationen
6.Mittel

Die Breitensuche (BFS) auf einem ungewichteten Graphen findet:

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

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

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

Welche Definition der Klasse P ist richtig?

  1. AProbleme, deren Lösungen in polynomieller Zeit geprüft, aber nie gefunden werden können
  2. BEntscheidungsprobleme, die ein deterministischer Algorithmus in polynomieller Zeit löst
  3. CProbleme, die auf jedem Computer exponentielle Zeit brauchen
  4. DProbleme, die parallel gelöst werden können

Lösungsschlüssel

  1. 1. C · O(log n)
  2. 2. D · O(1)
  3. 3. C · Bubblesort
  4. 4. B · Er lässt einen Baum von einem Startknoten aus wachsen und fügt die günstigste Kante hinzu, die den Baum verlässt
  5. 5. D · Die durchschnittlichen Kosten pro Operation über eine Worst-Case-Folge von Operationen
  6. 6. C · Kürzeste Wege, gemessen in der Anzahl der Kanten vom Startknoten
  7. 7. C · Nein, die untere Schranke gilt für den Worst Case über alle Eingaben, nicht für jede Eingabe
  8. 8. B · Entscheidungsprobleme, die ein deterministischer Algorithmus in polynomieller Zeit löst

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