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 drei Schritte hat ein Teile-und-herrsche-Algorithmus?

  1. ATeilen, beherrschen, zusammenführen
  2. BRaten, prüfen, wiederholen
  3. CSortieren, suchen, zurückgeben
  4. DLesen, berechnen, schreiben
2.Leicht

Die Platzkomplexität misst:

  1. ADen Festplattenplatz der Programmdatei nach dem Kompilieren
  2. BDie Anzahl der Codezeilen
  3. CDie Menge an Speicher, die ein Algorithmus bei wachsender Eingabe benötigt
  4. DDie physische Größe des Computers
3.Leicht

Welche Zeitkomplexität hat das Finden des größten Werts in einem unsortierten Array mit n Zahlen?

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

Welche Zeitkomplexität hat der Bellman-Ford-Algorithmus auf einem Graphen mit V Knoten und E Kanten?

  1. AO(V³ × E)
  2. BO(E log V)
  3. CO(V × E)
  4. DO(V + E)
5.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 2 Münzen; das Optimum ist 2
  2. BGreedy braucht 4 Münzen; das Optimum ist 3
  3. CGreedy braucht 3 Münzen; das Optimum ist 3
  4. DGreedy braucht 3 Münzen; das Optimum ist 2
6.Mittel

Wie baut der Algorithmus von Prim einen minimalen Spannbaum auf?

  1. AEr führt eine Breitensuche aus und behält den BFS-Baum
  2. BEr lässt einen Baum von einem Startknoten aus wachsen und fügt die günstigste Kante hinzu, die den Baum verlässt
  3. CEr entfernt die teuerste Kante, bis keine Kreise mehr übrig sind
  4. DEr sortiert alle Kanten nach Gewicht und fügt jede hinzu, sofern sie im Wald keinen Kreis bildet
7.Schwer

Warum kann der Dijkstra-Algorithmus falsche Ergebnisse liefern, wenn einige Kantengewichte negativ sind?

  1. AEr gerät bei jeder negativen Kante in eine Endlosschleife
  2. BEin Knoten wird beim Entnehmen endgültig festgelegt, aber eine spätere negative Kante könnte ihm noch einen kürzeren Weg geben
  3. CNegative Zahlen können nicht in einer Prioritätswarteschlange gespeichert werden
  4. DEr funktioniert nur auf ungerichteten Graphen
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. BHashfunktionen sind langsam
  3. CSchlüssel müssen zuerst sortiert werden
  4. DViele Schlüssel können im selben Bucket kollidieren

Lösungsschlüssel

  1. 1. A · Teilen, beherrschen, zusammenführen
  2. 2. C · Die Menge an Speicher, die ein Algorithmus bei wachsender Eingabe benötigt
  3. 3. D · O(n)
  4. 4. C · O(V × E)
  5. 5. D · Greedy braucht 3 Münzen; das Optimum ist 2
  6. 6. B · Er lässt einen Baum von einem Startknoten aus wachsen und fügt die günstigste Kante hinzu, die den Baum verlässt
  7. 7. B · Ein Knoten wird beim Entnehmen endgültig festgelegt, aber eine spätere negative Kante könnte ihm noch einen kürzeren Weg geben
  8. 8. D · Viele Schlüssel können im selben Bucket kollidieren

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