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 die lineare Suche in einem unsortierten Array mit n Elementen (Worst Case)?

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

Welche Entwurfsstrategie verwendet Mergesort?

  1. ATeile und herrsche (Divide and Conquer)
  2. BDynamische Programmierung
  3. CBrute Force
  4. DGierige Wahl (Greedy)
3.Leicht

Was setzt die binäre Suche bei ihrer Eingabe voraus?

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

Welche Zeitkomplexität hat Quicksort im Worst Case?

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

Welche Zeitkomplexität hat: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Wie viele Münzen verwendet bei Münzen zu 1, 3 und 4 und einem Betrag von 6 die gierige Methode „größte Münze zuerst" im Vergleich zum Optimum?

  1. AGreedy braucht 4 Münzen; das Optimum ist 3
  2. BGreedy braucht 3 Münzen; das Optimum ist 3
  3. CGreedy braucht 3 Münzen; das Optimum ist 2
  4. DGreedy braucht 2 Münzen; das Optimum ist 2
7.Schwer

Welche Technik liefert für Quicksort bei jeder Eingabe eine erwartete Laufzeit von O(n log n)?

  1. ARekursion nur auf der linken Seite verwenden
  2. BImmer das erste Element wählen
  3. CDen Pivot gleichverteilt zufällig wählen
  4. DDie Eingabe vor dem Quicksort sortieren
8.Schwer

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

  1. AArrays haben O(n) Zugriffszeit
  2. BSchlüssel müssen zuerst sortiert werden
  3. CViele Schlüssel können im selben Bucket kollidieren
  4. DHashfunktionen sind langsam

Lösungsschlüssel

  1. 1. C · O(n)
  2. 2. A · Teile und herrsche (Divide and Conquer)
  3. 3. A · Das Array muss sortiert sein
  4. 4. C · O(n²)
  5. 5. A · O(n log n)
  6. 6. C · Greedy braucht 3 Münzen; das Optimum ist 2
  7. 7. C · Den Pivot gleichverteilt zufällig wählen
  8. 8. C · Viele Schlüssel können im selben Bucket kollidieren

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