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 das Finden des größten Werts in einem unsortierten Array mit n Zahlen?

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

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

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

Was bedeutet es, wenn eine Operation in O(1) Zeit läuft?

  1. ASie kann nur einmal ausgeführt werden
  2. BSie dauert immer genau eine Sekunde
  3. CSie verarbeitet genau ein Element pro Sekunde Laufzeit
  4. DIhre Laufzeit wächst nicht mit der Eingabegröße
4.Mittel

Was berechnet der Floyd-Warshall-Algorithmus, und wie schnell?

  1. AEinen minimalen Spannbaum in O(E log V)
  2. BKürzeste Wege von einem Startknoten zu allen anderen in O(V + E)
  3. CKürzeste Wege zwischen allen Knotenpaaren in O(V³)
  4. DEine topologische Sortierung in O(V²)
5.Mittel

Quicksort verwendet immer das erste Element als Pivot. Bei welcher Eingabe zeigt es sein Worst-Case-Verhalten?

  1. ABei einem Array in zufälliger Reihenfolge
  2. BBei einem Array, dessen Elemente alle verschieden sind
  3. CBei einem Array der Länge 2
  4. DBei einem bereits sortierten Array
6.Mittel

Welche Zeitkomplexität hat die Multiplikation zweier n × n-Matrizen mit der üblichen dreifachen Schleife?

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

Welche Zeitkomplexität hat: for i = 1 to n: for (j = i; j ≤ n; j = j + i) O(1)-Arbeit?

  1. AO(n √n)
  2. BO(n log n)
  3. CO(n²)
  4. DO(n)
8.Schwer

Wie hoch sind die amortisierten Kosten für das Inkrementieren eines Binärzählers, wenn ein einzelnes Inkrement viele Bits umschalten kann?

  1. AO(log n) pro Inkrement
  2. BO(1) pro Inkrement
  3. CO(n) pro Inkrement
  4. DO(n log n) pro Inkrement

Lösungsschlüssel

  1. 1. A · O(n)
  2. 2. B · O(log n)
  3. 3. D · Ihre Laufzeit wächst nicht mit der Eingabegröße
  4. 4. C · Kürzeste Wege zwischen allen Knotenpaaren in O(V³)
  5. 5. D · Bei einem bereits sortierten Array
  6. 6. A · O(n³)
  7. 7. B · O(n log n)
  8. 8. B · O(1) pro Inkrement

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