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 setzt die binäre Suche bei ihrer Eingabe voraus?

  1. ADas Array darf höchstens 1000 Elemente haben
  2. BDas Array darf nur positive Zahlen enthalten
  3. CDie Länge des Arrays muss eine Zweierpotenz sein
  4. DDas Array muss sortiert sein
2.Leicht

Was ist ein Algorithmus?

  1. AEine Programmiersprache zum Schreiben mathematischer Formeln
  2. BEine endliche Folge eindeutig definierter Schritte, die ein Problem löst
  3. CJedes Computerprogramm mit grafischer Oberfläche
  4. DEine Datenstruktur, die Zahlen speichert
3.Leicht

Was beschreibt die Worst-Case-Laufzeit eines Algorithmus?

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

Die Zeitkomplexität des naiven rekursiven Fibonacci (fib(n) = fib(n−1) + fib(n−2)) ist:

  1. AExponentiell
  2. BKonstant
  3. CLogarithmisch
  4. DLinear
5.Mittel

Die Breitensuche (BFS) auf einem ungewichteten Graphen findet:

  1. AEine topologische Sortierung in allen Graphen
  2. BKürzeste Wege, gemessen in der Anzahl der Kanten vom Startknoten
  3. CDen minimalen Spannbaum
  4. DKürzeste Wege in Graphen mit negativen Kantengewichten
6.Mittel

Welcher Algorithmus findet die kürzesten Wege von einem Startknoten in einem Graphen mit nichtnegativen Kantengewichten?

  1. AKruskal-Algorithmus
  2. BDijkstra-Algorithmus
  3. CBellman-Ford ist in allen Fällen erforderlich
  4. DTiefensuche (DFS)
7.Schwer

Warum ist eine Suche in einer Hashtabelle im Durchschnitt O(1), im Worst Case aber O(n)?

  1. AViele Schlüssel können im selben Bucket kollidieren
  2. BArrays haben O(n) Zugriffszeit
  3. CHashfunktionen sind langsam
  4. DSchlüssel müssen zuerst sortiert werden
8.Schwer

Der Strassen-Algorithmus multipliziert Matrizen mit 7 statt 8 rekursiven Multiplikationen von Blöcken halber Größe. Welche Laufzeit hat er?

  1. AΘ(nlog₂ 7), etwa n2,81
  2. BΘ(n³)
  3. CΘ(n² log n)
  4. DΘ(n2)

Lösungsschlüssel

  1. 1. D · Das Array muss sortiert sein
  2. 2. B · Eine endliche Folge eindeutig definierter Schritte, die ein Problem löst
  3. 3. C · Die maximale Laufzeit über alle Eingaben der Größe n
  4. 4. A · Exponentiell
  5. 5. B · Kürzeste Wege, gemessen in der Anzahl der Kanten vom Startknoten
  6. 6. B · Dijkstra-Algorithmus
  7. 7. A · Viele Schlüssel können im selben Bucket kollidieren
  8. 8. A · Θ(nlog₂ 7), etwa n2,81

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