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

Was ist der Basisfall einer rekursiven Funktion?

  1. AEin Fall, der direkt beantwortet wird, ohne einen weiteren rekursiven Aufruf
  2. BDer Aufruf, der am meisten Speicher verbraucht
  3. CDer Fall mit der größten Eingabe, der vor allen rekursiven Aufrufen behandelt wird
  4. DDie erste Zeile der Funktion
2.Leicht

Was ist Rekursion?

  1. AEine Funktion, die sich selbst mit kleineren Eingaben aufruft
  2. BEin Sortierverfahren
  3. CEine Schleife, die nie endet
  4. DEine Art von Datenstruktur
3.Leicht

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

  1. AHeapsort
  2. BQuicksort
  3. CMergesort
  4. DBubblesort
4.Mittel

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

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

Warum wechseln viele Sortierroutinen in Bibliotheken bei sehr kleinen Teilarrays zu Insertionsort?

  1. AInsertionsort hat wenig Overhead und ist bei kleinen oder fast sortierten Eingaben schnell
  2. BInsertionsort ist im Worst Case O(n log n)
  3. CRekursive Algorithmen können Arrays mit weniger als 10 Elementen nicht verarbeiten
  4. DInsertionsort braucht bei großen Eingaben weniger Speicher als jeder andere Sortieralgorithmus
6.Mittel

Dynamische Programmierung ist nützlich, wenn ein Problem Folgendes aufweist:

  1. ANur zufällige Eingaben
  2. BEine einzige Schleife
  3. CÜberhaupt keine Teilprobleme, sodass es in einem Schritt lösbar ist
  4. DÜberlappende Teilprobleme und optimale Teilstruktur
7.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
8.Schwer

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

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

Lösungsschlüssel

  1. 1. A · Ein Fall, der direkt beantwortet wird, ohne einen weiteren rekursiven Aufruf
  2. 2. A · Eine Funktion, die sich selbst mit kleineren Eingaben aufruft
  3. 3. D · Bubblesort
  4. 4. D · Sie ruft sich immer weiter selbst auf, bis der Aufrufstack überläuft
  5. 5. A · Insertionsort hat wenig Overhead und ist bei kleinen oder fast sortierten Eingaben schnell
  6. 6. D · Überlappende Teilprobleme und optimale Teilstruktur
  7. 7. B · Nach V − 1 Runden prüft er, ob sich noch eine Kante relaxieren lässt
  8. 8. B · Θ(n³)

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