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 Laufzeit hat Countingsort für n ganze Zahlen im Bereich 0 bis k?

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

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

  1. ABubblesort
  2. BInsertionsort
  3. CMergesort
  4. DQuicksort
3.Leicht

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

  1. AHeapsort
  2. BQuicksort
  3. CBubblesort
  4. DMergesort
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 ruft sich immer weiter selbst auf, bis der Aufrufstack überläuft
  4. DSie läuft in O(1) Zeit
5.Mittel

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

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

Wie viele Ebenen hat die Rekursion von Mergesort bei einem Array mit n Elementen?

  1. AEtwa n
  2. BEtwa n / 2
  3. CEtwa √n
  4. DEtwa log₂ n
7.Schwer

Welche Laufzeit hat der Dijkstra-Algorithmus mit einem binären Heap auf einem Graphen mit V Knoten und E Kanten?

  1. AO(V × E)
  2. BO(V + E)
  3. CO((V + E) log V)
  4. DO(V³)
8.Schwer

Das Halteproblem zeigt, dass:

  1. AManche Programme auf schnelleren Computern schneller laufen, das Anhalten also von der Hardware abhängt
  2. BKein Algorithmus für jedes Programm und jede Eingabe entscheiden kann, ob es anhält
  3. CJedes Programm irgendwann anhält
  4. DSchleifen vermieden werden sollten

Lösungsschlüssel

  1. 1. C · O(n + k)
  2. 2. D · Quicksort
  3. 3. C · Bubblesort
  4. 4. C · Sie ruft sich immer weiter selbst auf, bis der Aufrufstack überläuft
  5. 5. D · O(log n)
  6. 6. D · Etwa log₂ n
  7. 7. C · O((V + E) log V)
  8. 8. B · Kein Algorithmus für jedes Programm und jede Eingabe entscheiden kann, ob es anhält

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