Algorithmenentwurfstechniken: Quizfragen und Lernmaterialien

Question 1

Welcher der folgenden Algorithmen ist ein Greedy-Algorithmus?

Accepted Answer

Dijkstra-Algorithmus

Answer

Quicksort

Answer

Merge Sort

Answer

Top-Down-Dynamische Programmierung

Question 2

Welche Aussage beschreibt die Dynamische Programmierung am besten?

Accepted Answer

Eine Methode zur Lösung von Optimierungsproblemen durch die schrittweise Optimierung kleinerer Teilprobleme.

Answer

Nur anwendbar auf Probleme mit rekursiven Strukturen.

Answer

Garantiert immer die absolut beste Lösung für ein Problem.

Question 3

Welche zwei gängigen Methoden werden verwendet, um die Korrektheit von Algorithmen zu beweisen?

Accepted Answer

Induktion und Widerspruch

Answer

Simulation und Optimierung

Answer

Quicksort und Mergesort

Answer

Greedy und Divide-and-Conquer

Question 4

Welcher Schritt ist der erste bei der Entwicklung eines Divide-and-Conquer-Algorithmus?

Accepted Answer

Das Problem in kleinere Teilprobleme zerlegen

Answer

Die Teilprobleme lösen

Answer

Die Lösungen der Teilprobleme zusammenführen

Answer

Den Basisfall überprüfen

Question 5

Was ist der Hauptvorteil der dynamischen Programmierung?

Accepted Answer

Sie nutzt Memoization, um doppelte Berechnungen zu vermeiden.

Answer

Sie löst Probleme in exponentieller Zeit.

Answer

Sie ist nur für Probleme mit optimalen Unterstrukturen anwendbar.

Answer

Sie garantiert immer die beste Lösung.

Question 6

Welche Laufzeitkomplexität hat der klassische Merge-Sort-Algorithmus?

Accepted Answer

O(n log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(log n)

Question 7

Welche der folgenden ist keine Technik des Algorithmenentwurfs?

Accepted Answer

Heuristik

Answer

Rekursion

Answer

Divide-and-Conquer

Answer

Dynamische Programmierung

Question 8

Welche Aussage beschreibt Greedy-Verfahren treffend?

Accepted Answer

Trifft lokale Entscheidungen ohne Berücksichtigung globaler Konsequenzen.

Answer

Zerlegt das Problem in kleinere Teilaufgaben.

Answer

Speichert alle möglichen Lösungen und wählt die optimale aus.

Answer

Durchläuft alle möglichen Lösungen, um die beste zu finden.

Question 9

Welches Algorithmus-Designmuster eignet sich am besten für Probleme mit unabhängigen Teilaufgaben?

Accepted Answer

Divide-and-Conquer

Answer

Dynamische Programmierung

Answer

Greedy-Algorithmen

Answer

Zufällige Suche

Question 10

Welcher Nachteil ist mit dynamischer Programmierung verbunden?

Accepted Answer

Hoher Speicherbedarf.

Answer

Anwendbar nur auf Probleme mit überlappenden Teilaufgaben.

Answer

Immer die effizienteste Algorithmus-Designtechnik.

Answer

Anwendbar nur auf Probleme mit wenigen Teilaufgaben.

Question 11

Welche Aussage trifft auf Algorithmen zu, die Approximationslösungen erzeugen?

Accepted Answer

Finden Lösungen innerhalb eines bestimmten Faktors der optimalen Lösung.

Answer

G garantieren optimale Lösungen.

Answer

Finden Lösungen mit linearer Laufzeit.

Answer

Erfordern exponentielle Laufzeit.

Question 12

Welcher Algorithmus löst das kürzeste gemeinsame Teilsequenzproblem?

Accepted Answer

Levenshtein-Algorithmus

Answer

Suffixtree

Answer

Huffman-Codierung

Answer

A*-Algorithmus

Question 13

Welche Aussage beschreibt deterministische Algorithmen?

Accepted Answer

Geben immer die gleiche Ausgabe für eine gegebene Eingabe aus.

Answer

Geben zufällige Ausgaben aus, abhängig von der Eingabe.

Answer

Können unterschiedliche Ausgaben für dieselbe Eingabe erzeugen.

Answer

Müssen eine sehr lange Laufzeit haben.

Question 14

Welcher Ansatz wird verwendet, um eine obere Schranke für die Algorithmuslaufzeit zu beweisen?

Accepted Answer

Master-Theorem

Answer

Widerspruchsbeweis

Answer

Induktionsbeweis

Answer

Experimentelle Analyse

Question 15

Welche Aussage beschreibt Algorithmen, die eine untere Schranke für ein Problem liefern?

Accepted Answer

Beweisen, dass kein Algorithmus das Problem unter einer bestimmten Zeit lösen kann.

Answer

Zeigen, dass ein bestimmter Algorithmus das Problem unter einer bestimmten Zeit lösen kann.

Answer

Liefern eine Annäherungslösung für das Problem.

Answer

Lösen das Problem für eine bestimmte Eingabe.

Question 16

Welche Schritte sind die Grundlage des Divide-and-Conquer-Algorithmus?

Accepted Answer

Zerlegen, Lösen, Zusammenfügen

Answer

Rekursive Zerlegung bis zur Lösbarkeit

Answer

Suche des kleinsten Teilproblems und Lösung von dort aus

Question 17

Welche Algorithmenentwurfstechnik ist optimal, um den kürzesten Pfad in einem gewichteten, gerichteten Graphen zu ermitteln?

Accepted Answer

Dynamische Programmierung

Answer

Gieriger Algorithmus

Answer

Teile-und-Herrsche

Question 18

Wie gehen Greedy-Algorithmen vor?

Accepted Answer

Sie treffen Entscheidungen, die den aktuellen Zustand verbessern, ohne die Zukunft zu beachten.

Answer

Sie finden immer die beste Lösung.

Answer

Sie sind immer schnell und effizient.

Answer

Sie sind nur für kleine Probleme geeignet.

Question 19

Welcher Algorithmus verwendet einen heuristischen Ansatz, liefert jedoch keine garantierte optimale Lösung?

Accepted Answer

Greedy-Algorithmus

Answer

Dynamische Programmierung

Answer

Divide-and-Conquer-Algorithmus

Answer

Backtracking-Algorithmus

Question 20

Welche Algorithmenentwurfstechnik unterteilt ein Problem in kleinere Teilprobleme und löst diese rekursiv, bis eine Basisbedingung erreicht ist?

Accepted Answer

Divide-and-Conquer

Answer

Dynamische Programmierung

Answer

Greedy-Algorithmus

Answer

Backtracking

Question 21

Welche Algorithmenentwurfstechnik speichert Lösungen zu überlappenden Teilproblemen, um sie wiederzuverwenden und so Rechenzeit zu sparen?

Accepted Answer

Dynamische Programmierung

Answer

Divide-and-Conquer

Answer

Greedy-Algorithmus

Question 22

Welche Eigenschaft eines Algorithmus beschreibt seine Fähigkeit, unabhängig von der Eingabedatenmenge stets die beste Lösung zu finden?

Accepted Answer

Optimalität

Answer

Effizienz

Answer

Zufälligkeit

Answer

Heuristik

Question 23

Welche Algorithmenentwurfstechnik eignet sich am besten für Probleme mit überlappenden Teilproblemen und optimalen Substrukturen?

Accepted Answer

Dynamische Programmierung

Answer

Divide-and-Conquer

Answer

Zufällige Suche

Answer

Greedy-Algorithmus

Question 24

Welcher Datentyp wird in Dynamischen Programmieralgorithmen typischerweise verwendet, um Lösungen zu Teilproblemen zu speichern?

Accepted Answer

Tabelle

Answer

Baum

Answer

Graph

Answer

Liste

Question 25

Welche Eigenschaft eines Algorithmus beschreibt seine Fähigkeit, in angemessener Zeit eine Lösung zu finden?

Accepted Answer

Effizienz

Answer

Heuristik

Answer

Skalierbarkeit

Answer

Optimalität

Question 26

Welcher der folgenden Algorithmen ist ein Divide-and-Conquer-Algorithmus?

Accepted Answer

Merge-Sort

Answer

Kruskal-Algorithmus

Answer

Dijkstra-Algorithmus

Question 27

Welche Technik kann verwendet werden, um die Zeitkomplexität eines rekursiven Algorithmus zu verbessern?

Accepted Answer

Memoization

Answer

Heuristik

Answer

Branch-and-Bound

Question 28

Welche der folgenden Aussagen beschreibt Greedy-Algorithmen am besten?

Accepted Answer

Sie treffen bei jedem Schritt die scheinbar beste Entscheidung, ohne zukünftige Konsequenzen zu berücksichtigen.

Answer

Sie garantieren immer eine optimale Lösung.

Answer

Sie sind immer effizient in der Laufzeit.

Question 29

Was ist der Hauptunterschied zwischen Dynamischer Programmierung und Greedy-Algorithmen?

Accepted Answer

Dynamische Programmierung zeichnet Zustände des Problems auf und geht bei Bedarf auf sie zurück, während Greedy-Algorithmen dies nicht tun.

Answer

Dynamische Programmierung ist immer effizienter als Greedy-Algorithmen.

Answer

Greedy-Algorithmen sind immer einfacher zu implementieren als dynamische Programmierung.

Question 30

Welche der folgenden Aussagen zur Zeitkomplexität von Greedy-Algorithmen ist korrekt?

Accepted Answer

Sie kann für verschiedene Probleme stark variieren.

Answer

Sie ist immer optimal.

Answer

Sie ist immer polynomiell.

Question 31

Welche der folgenden Aussagen beschreibt den Rekursionsansatz in der Dynamischen Programmierung am besten?

Accepted Answer

Er löst das Problem für kleinere Teilprobleme rekursiv und speichert die Ergebnisse.

Answer

Er löst das Problem nur einmal und speichert das Ergebnis.

Answer

Er löst das Problem iterativ und speichert die Ergebnisse in einer Tabelle.

Question 32

Welche der folgenden Aussagen zu Greedy-Algorithmen ist falsch?

Accepted Answer

Sie garantieren immer die optimale Lösung.

Answer

Sie sind einfach zu implementieren.

Answer

Sie eignen sich für Probleme, bei denen lokale Optimierungen zu einer globalen Optimierung führen können.

Question 33

Welche der folgenden Techniken kann verwendet werden, um die Leistung eines Divide-and-Conquer-Algorithmus zu verbessern?

Accepted Answer

Verwendung von Memoisierung

Answer

Vermeidung von Rekursion

Answer

Verwendung von Brute-Force-Ansätzen

Answer

Vergrößerung des Problemumfangs

Question 34

Welches der folgenden Beispiele ist KEIN typisches Dynamische Programmierproblem?

Accepted Answer

Berechnung des kürzesten Weges in einem Graphen

Answer

Berechnung des Rucksackproblems

Answer

Berechnung der längsten gemeinsamen Teilfolge zweier Zeichenketten

Answer

Berechnung der minimalen Anzahl von Münzen zur Darstellung eines bestimmten Geldbetrags

Question 35

Welche Eigenschaft eines Teilproblems ermöglicht die Verwendung der Divide-and-Conquer-Technik?

Accepted Answer

Das Teilproblem ist kleiner und ähnelt dem ursprünglichen Problem.

Answer

Das Teilproblem ist größer und enthält das ursprüngliche Problem.

Answer

Das Teilproblem ist völlig anders und steht in keinem Zusammenhang mit dem ursprünglichen Problem.

Answer

Das Teilproblem hat eine exponentielle Laufzeit.

Question 36

Welches Hauptmerkmal unterscheidet die Dynamische Programmierung von anderen Entwurfstechniken?

Accepted Answer

Sie speichert optimale Lösungen für Teilprobleme, um die Lösung für das Gesamtproblem effizient zu berechnen.

Answer

Sie verwendet Heuristiken, um gute, aber nicht unbedingt optimale Lösungen zu finden.

Answer

Sie basiert auf der Annahme, dass das Problem in kleinere, unabhängige Teilprobleme zerlegt werden kann.

Answer

Sie sucht nach allen möglichen Lösungen und wählt die beste aus.

Question 37

Welcher der folgenden Algorithmen veranschaulicht die Anwendung der Divide-and-Conquer-Technik?

Accepted Answer

Quicksort

Answer

Dijkstra's Algorithmus

Answer

Bellman-Ford-Algorithmus

Answer

Floyd-Warshall-Algorithmus

Question 38

Welche Aussage über die Beschränkungen von Greedy-Algorithmen ist korrekt?

Accepted Answer

Sie können nicht immer optimale Lösungen garantieren.

Answer

Sie berücksichtigen immer das globale Optimum bei der Entscheidungsfindung.

Answer

Sie können nur für Probleme mit kleinen Eingabedaten verwendet werden.

Answer

Sie sind immer langsamer als andere Algorithmentypen.

Question 39

Welches Hauptziel verfolgen Algorithmenentwurfstechniken?

Accepted Answer

Optimierung der Algorithmuslaufzeit

Answer

Reduzierung des Speicherbedarfs

Answer

Verbesserung der Benutzerfreundlichkeit

Answer

Steigerung der Algorithmusgenauigkeit

Question 40

Was ist ein wesentliches Merkmal von Divide-and-Conquer-Algorithmen?

Accepted Answer

Sie zerlegen ein Problem rekursiv in kleinere, ähnliche Teilprobleme.

Answer

Sie sind nicht geeignet für Probleme mit überlappenden Teilproblemen.

Answer

Sie lösen Probleme iterativ durch schrittweise Berechnung von Teilproblemen.

Answer

Sie benötigen immer eine polynomielle Laufzeit.

Question 41

Welche der folgenden Entwurfstechniken eignet sich am besten für die Lösung von Optimierungsproblemen mit überlappenden Teilproblemen?

Accepted Answer

Dynamische Programmierung

Answer

Greedy-Algorithmen

Answer

Zufällige Suche

Answer

Teilen und Erobern

Question 42

Welches Algorithmenentwurfsmuster basiert auf der rekursiven Aufteilung eines Problems in kleinere, unabhängige Unterprobleme?

Accepted Answer

Teile und Herrsche

Answer

Dynamische Programmierung

Answer

Backtracking

Answer

Gieriger Algorithmus

Question 43

Welches Algorithmenentwurfsmuster ist besonders nützlich für die Lösung von Optimierungsproblemen, indem es Teilprobleme löst und deren Ergebnisse zur Berechnung der optimalen Lösung speichert?

Accepted Answer

Dynamische Programmierung

Answer

Teile und Herrsche

Answer

Backtracking

Answer

Gieriger Algorithmus

Question 44

Welche Aussage charakterisiert am besten einen gierigen Algorithmus?

Accepted Answer

Er wählt in jedem Schritt die lokal beste Entscheidung, ohne die zukünftigen Auswirkungen zu berücksichtigen.

Answer

Er garantiert immer die global optimale Lösung.

Answer

Er ist immer der schnellste Algorithmus für ein bestimmtes Problem.

Question 45

Gegeben sei ein Array von Münzen mit unterschiedlichen Werten. Du möchtest die minimale Anzahl von Münzen finden, die benötigt werden, um einen bestimmten Geldbetrag zu bilden. Welches Algorithmenentwurfsmuster eignet sich am besten für dieses Problem?

Accepted Answer

Dynamische Programmierung

Answer

Teile und Herrsche

Answer

Gieriger Algorithmus

Answer

Backtracking

Question 46

Welche Aussage beschreibt den Nutzen von Algorithmenentwurfstechniken am besten?

Accepted Answer

Sie unterstützen die Entwicklung effizienter und effektiver Algorithmen für bestimmte Probleme.

Answer

Sie sind für alle Arten von Problemen einsetzbar.

Answer

Sie garantieren immer die beste Lösung für ein Problem.

Question 47

Welche Aussage über das Teile-und-Herrsche-Paradigma ist FALSCH?

Accepted Answer

Es teilt das Problem in nicht überlappende Unterprobleme auf, die voneinander unabhängig sind.

Answer

Es löst die Unterprobleme rekursiv.

Answer

Es kombiniert die Lösungen der Unterprobleme, um die Lösung des ursprünglichen Problems zu erhalten.

Question 48

Welches der folgenden Probleme kann typischerweise durch einen gierigen Algorithmus effizient gelöst werden?

Accepted Answer

Aufgabenplanung (z.B. die Planung von Terminen)

Answer

Traveling Salesman Problem

Answer

Hamiltonkreisproblem

Answer

Rucksackproblem

Question 49

Welche Aussage trifft auf dynamische Programmierung zu?

Accepted Answer

Sie löst Probleme durch Speichern von Lösungen zu überlappenden Unterproblemen, um Redundanz zu vermeiden.

Answer

Sie garantiert immer die optimale Lösung für ein Problem.

Answer

Sie ist immer effizienter als gierige Algorithmen.

Question 50

Welche Algorithmenentwurfstechnik ist am besten geeignet, um das Problem der Suche nach der längsten gemeinsamen Teilfolge zweier Zeichenketten zu lösen?

Accepted Answer

Dynamische Programmierung

Answer

Gieriger Algorithmus

Answer

Teile und Herrsche

Question 51

Welche Algorithmenentwurfstechnik ist am besten geeignet, um ein Problem in kleinere, unabhängige Unterprobleme zu zerlegen, die rekursiv gelöst werden können?

Accepted Answer

Divide-and-Conquer

Answer

Backtracking

Answer

Greedy-Algorithmus

Answer

Dynamische Programmierung

Question 52

Welches Merkmal ist charakteristisch für einen Greedy-Algorithmus?

Accepted Answer

Treffen lokal optimaler Entscheidungen in der Hoffnung, eine globale optimale Lösung zu finden.

Answer

Rekursive Zerlegung des Problems in kleinere Unterprobleme.

Answer

Speichern von Teilergebnissen zur Vermeidung von redundanten Berechnungen.

Question 53

Welches Problem ist ein typisches Beispiel für einen Algorithmus, der mit dynamischer Programmierung gelöst werden kann?

Accepted Answer

Das Finden des kürzesten Pfades in einem Graphen.

Answer

Das Suchen nach einem Element in einer sortierten Liste.

Answer

Das Sortieren einer Liste von Zahlen.

Answer

Das Berechnen der Fakultät einer Zahl.

Question 54

Wie unterscheiden sich Greedy-Algorithmen und dynamische Programmierung?

Accepted Answer

Greedy-Algorithmen treffen lokal optimale Entscheidungen, während dynamische Programmierung eine Tabelle von Teilergebnissen aufbaut.

Answer

Greedy-Algorithmen sind immer effizienter als dynamische Programmierung.

Question 55

Welche der folgenden Aussagen beschreibt den Vorteil der Divide-and-Conquer-Technik?

Accepted Answer

Sie ermöglicht die rekursive Lösung komplexer Probleme durch Zerlegung in kleinere, einfacher zu lösende Unterprobleme.

Answer

Sie ist immer die effizienteste Technik für jedes Problem.

Question 56

Welche der folgenden Aussagen trifft auf dynamische Programmierung zu?

Accepted Answer

Sie speichert Teilergebnisse, um redundante Berechnungen zu vermeiden.

Answer

Sie ist nur für Probleme geeignet, die sich in unabhängige Unterprobleme zerlegen lassen.

Answer

Sie ist immer die effizienteste Technik für jedes Problem.

Question 57

Welche der folgenden Aussagen beschreibt ein Problem, das sich gut mit einem Greedy-Algorithmus lösen lässt?

Accepted Answer

Ein Problem, bei dem eine lokale optimale Entscheidung die globale optimale Lösung nicht beeinträchtigt.

Answer

Ein Problem, das sich in unabhängige Unterprobleme zerlegen lässt.

Question 58

Welche der folgenden Algorithmenentwurfstechniken ist am besten geeignet, um alle möglichen Lösungen für ein Problem zu finden, wenn die Anzahl der möglichen Lösungen begrenzt ist?

Accepted Answer

Backtracking

Answer

Divide-and-Conquer

Answer

Greedy-Algorithmus

Question 59

Welches Entwurfsmuster eignet sich am besten für Probleme, die in kleinere, ähnliche Unterprobleme zerlegt werden können, deren Lösungen dann kombiniert werden, um die Gesamtproblem zu lösen?

Accepted Answer

Divide-and-Conquer

Answer

Dynamische Programmierung

Answer

Greedy-Algorithmus

Question 60

Ein Algorithmus, der bei jedem Schritt die lokale beste Entscheidung trifft, in der Hoffnung, die globale optimale Lösung zu finden, ist ein:

Accepted Answer

Greedy-Algorithmus

Answer

Backtracking-Algorithmus

Answer

Divide-and-Conquer-Algorithmus

Answer

Dynamische Programmierungsalgorithmus

Question 61

Welches Entwurfsmuster ist besonders nützlich, wenn ein Problem überlappende Unterprobleme aufweist, deren Lösungen wiederholt verwendet werden können, um die Effizienz zu verbessern?

Accepted Answer

Dynamische Programmierung

Answer

Backtracking

Answer

Divide-and-Conquer

Answer

Greedy-Algorithmus

Question 62

Welcher Algorithmus ist am besten geeignet, um das kürzeste Pfadproblem in einem gewichteten Graphen zu lösen?

Accepted Answer

Dijkstras Algorithmus

Answer

Mergesort

Answer

Quicksort

Answer

Bubblesort

Question 63

Welcher der folgenden Algorithmen ist KEIN Sortieralgorithmus?

Accepted Answer

Dijkstras Algorithmus

Answer

Quicksort

Answer

Bubblesort

Answer

Mergesort

Question 64

Welche Komplexitätsklasse beschreibt einen Algorithmus, dessen Ausführungszeit logarithmisch mit der Eingabegröße wächst?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n^2)