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 Insertionsort im Worst Case?

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

Was ist Memoisation?

  1. ADas Speichern der Ergebnisse von Funktionsaufrufen, sodass wiederholte Aufrufe aus dem Speicher beantwortet werden
  2. BDas automatische Umwandeln einer Rekursion in eine gleichwertige Schleife, sodass kein Aufrufstack nötig ist
  3. CDas Schreiben von Kommentaren neben jede Codezeile
  4. DDas Freigeben von Speicher, nachdem eine Funktion zurückkehrt
3.Leicht

Was beschreibt die Worst-Case-Laufzeit eines Algorithmus?

  1. ADie maximale Laufzeit über alle Eingaben der Größe n
  2. BDie Laufzeit auf einem langsamen Computer
  3. CDie Laufzeit bei der kleinsten Eingabe
  4. DDie erwartete Laufzeit bei einer zufälligen Eingabe der Größe n
4.Mittel

Ein Greedy-Algorithmus:

  1. ALiefert immer die optimale Lösung
  2. BProbiert jede mögliche Lösung aus
  3. CVerwendet ausschließlich Rekursion
  4. DTrifft in jedem Schritt die lokal beste Wahl
5.Mittel

Welche Aussage über eine rekursive Funktion ohne erreichbaren Basisfall ist richtig?

  1. ASie läuft in O(1) Zeit
  2. BSie ruft sich immer weiter selbst auf, bis der Aufrufstack überläuft
  3. CSie gibt automatisch 0 zurück
  4. DDer Compiler wandelt sie immer in eine Schleife um, die sicher endet
6.Mittel

Warum bringt dynamische Programmierung bei Mergesort keine echte Beschleunigung?

  1. AMergesort hat keine rekursive Struktur
  2. BSeine Teilprobleme überlappen sich nicht, also gibt es nichts wiederzuverwenden
  3. CDynamische Programmierung funktioniert nur bei Graphenproblemen, nicht bei Arrays
  4. DMergesort ist bereits O(n)
7.Schwer

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

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

Wie erkennt der Bellman-Ford-Algorithmus einen vom Startknoten erreichbaren Kreis mit negativem Gewicht?

  1. AEr prüft, ob irgendeine Kante ein negatives Gewicht hat
  2. BNach V − 1 Runden prüft er, ob sich noch eine Kante relaxieren lässt
  3. CEr zählt die Kreise mit einer Tiefensuche
  4. DEr führt den Dijkstra-Algorithmus zweimal aus und vergleicht die beiden Distanzergebnisse

Lösungsschlüssel

  1. 1. A · O(n²)
  2. 2. A · Das Speichern der Ergebnisse von Funktionsaufrufen, sodass wiederholte Aufrufe aus dem Speicher beantwortet werden
  3. 3. A · Die maximale Laufzeit über alle Eingaben der Größe n
  4. 4. D · Trifft in jedem Schritt die lokal beste Wahl
  5. 5. B · Sie ruft sich immer weiter selbst auf, bis der Aufrufstack überläuft
  6. 6. B · Seine Teilprobleme überlappen sich nicht, also gibt es nichts wiederzuverwenden
  7. 7. D · Θ(n log² n)
  8. 8. B · Nach V − 1 Runden prüft er, ob sich noch eine Kante relaxieren lässt

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