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 Tiefensuche auf einem Graphen, der als Adjazenzlisten gespeichert ist?

  1. AO(V × E)
  2. BO(E log V)
  3. CO(V²)
  4. DO(V + E)
2.Leicht

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

  1. ABubblesort
  2. BQuicksort
  3. CMergesort
  4. DHeapsort
3.Leicht

Welcher Sortieralgorithmus wählt ein Pivotelement und teilt das Array in kleinere und größere Elemente auf?

  1. ABubblesort
  2. BQuicksort
  3. CMergesort
  4. DInsertionsort
4.Mittel

Wie viele Vergleiche braucht die binäre Suche im Worst Case ungefähr bei einem sortierten Array mit 1,000,000 Elementen?

  1. AEtwa 500,000
  2. BEtwa 20
  3. CEtwa 1,000
  4. DEtwa 100
5.Mittel

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

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

Du sortierst ein Array mit n Elementen einmal und beantwortest danach k Enthaltenseinsanfragen mit binärer Suche. Wie hoch sind die Gesamtkosten?

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

Welcher Algorithmus findet einen minimalen Spannbaum, indem er wiederholt die günstigste Kante hinzufügt, die keinen Zyklus bildet?

  1. APrim-Algorithmus, ausgehend von einem Knoten
  2. BFloyd-Warshall
  3. CKruskal-Algorithmus
  4. DDijkstra-Algorithmus
8.Schwer

Kürzeste einfache Wege lassen sich in polynomieller Zeit finden. Was ist über das Finden des längsten einfachen Weges zwischen zwei Knoten in einem allgemeinen Graphen bekannt?

  1. AEs ist NP-schwer
  2. BEs ist immer in O(V + E) lösbar
  3. CEs ist unentscheidbar
  4. DEs lässt sich mit dem Dijkstra-Algorithmus und negierten Gewichten lösen

Lösungsschlüssel

  1. 1. D · O(V + E)
  2. 2. A · Bubblesort
  3. 3. B · Quicksort
  4. 4. B · Etwa 20
  5. 5. A · O(n)
  6. 6. B · O(n log n + k log n)
  7. 7. C · Kruskal-Algorithmus
  8. 8. A · Es ist NP-schwer

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