Komplexitätsanalyse: Laufzeit und Speicherbedarf von Algorithmen verstehen

Question 1

Welches Modell wird verwendet, um die Laufzeit eines Algorithmus **als Funktion der Eingangsgröße** zu beschreiben?

Accepted Answer

Asymptotische Analyse

Answer

Empirische Analyse

Answer

Worst-Case-Analyse

Answer

Best-Case-Analyse

Question 2

Welche Komplexitätsklasse enthält Algorithmen, deren Laufzeit durch ein **Polynom** in der Eingangsgröße begrenzt ist?

Accepted Answer

P

Answer

NP

Answer

NP-vollständig

Answer

NP-schwer

Question 3

Welcher der folgenden Algorithmen hat die Komplexität **O(log n)**?

Accepted Answer

Binärsuche

Answer

Linearsuche

Answer

Sortierung nach Einfügen

Answer

Sortierung durch Auswahl

Question 4

Welches Problem ist ein Beispiel für ein **NP-vollständiges** Problem?

Accepted Answer

Hamilton-Kreis

Answer

Sortierung

Answer

Primzahltest

Answer

Faktorisierung

Question 5

Was beschreibt die Laufzeitanalyse im **Worst-Case-Szenario**?

Accepted Answer

Die maximale Laufzeit für einen beliebigen Eingang

Answer

Die durchschnittliche Laufzeit über alle Eingänge

Answer

Die minimale Laufzeit für einen beliebigen Eingang

Answer

Die Laufzeit für den häufigsten Eingang

Question 6

Welche der folgenden Funktionen stellt die Komplexität eines Algorithmus dar, der n-mal eine Schleife durchläuft und in jeder Iteration eine **Konstantenoperation** ausführt?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(n^2)

Answer

O(log n)

Question 7

Welche Aussage über die Laufzeit von Algorithmen ist falsch?

Accepted Answer

Die Laufzeit eines Algorithmus ist immer eine konstante Größe.

Answer

Die Laufzeit eines Algorithmus kann von der Größe der Eingabe abhängen.

Answer

Die Laufzeit eines Algorithmus kann für unterschiedliche Eingaben variieren.

Answer

Die Laufzeit eines Algorithmus kann exponentiell mit der Größe der Eingabe wachsen.

Question 8

Welcher Begriff bezeichnet die maximale Anzahl von Schritten, die ein Algorithmus für eine Eingangsgröße n ausführen kann?

Accepted Answer

Worst-Case-Komplexität

Answer

Best-Case-Komplexität

Answer

Durchschnittliche Komplexität

Answer

Amortisierte Komplexität

Question 9

Was ist der Zweck einer Heap-Datenstruktur?

Accepted Answer

Effiziente Implementierung von Prioritätswarteschlangen

Answer

Effiziente Implementierung von Stapeln

Answer

Effiziente Implementierung von Warteschlangen

Answer

Effiziente Implementierung von Arrays

Question 10

Welcher Algorithmus ist für seine lineare Laufzeitkomplexität bekannt?

Accepted Answer

Einfügesortierung

Answer

Blasensortierung

Answer

Merge Sort

Answer

Quicksort

Question 11

Welche Faktoren beeinflussen die Laufzeit eines Algorithmus? Nennen Sie 3 Beispiele.

Accepted Answer

Eingabegröße

Accepted Answer

Hardwareplattform

Accepted Answer

Programmiersprache

Answer

Benutzeroberfläche

Question 12

Welche Komplexitätsklasse beschreibt Algorithmen, deren Laufzeit sich durch O(log n) abschätzen lässt?

Accepted Answer

P

Answer

NP

Answer

NP-vollständig

Answer

NP-schwer

Question 13

Welches Problem ist NP-vollständig?

Accepted Answer

Minimales Spanning-Tree-Problem

Answer

Sortierung

Answer

Primzahlenberechnung

Answer

Fakultätsberechnung

Question 14

Welche Eigenschaft kennzeichnet einen Algorithmus mit linearer Laufzeit?

Accepted Answer

Seine Laufzeit wächst proportional zur Eingabegröße.

Answer

Seine Laufzeit wächst exponentiell zur Eingabegröße.

Answer

Seine Laufzeit ist konstant unabhängig von der Eingabegröße.

Answer

Seine Laufzeit wächst logarithmisch zur Eingabegröße.

Question 15

Welche Aussage über die Mastermethode ist zutreffend?

Accepted Answer

Sie ist nur auf Algorithmen mit rekursiven Aufrufen anwendbar.

Answer

Sie liefert immer die exakte Laufzeit.

Answer

Sie ist nur für Algorithmen mit exponentieller Laufzeit geeignet.

Answer

Sie berücksichtigt nicht die Grundoperationen im Algorithmus.

Question 16

Welcher Algorithmus besitzt die höchste Laufzeitkomplexität?

Accepted Answer

Bubblesort

Answer

Quicksort

Answer

Heapsort

Answer

Mergesort

Question 17

Vergleiche die Zeitkomplexität von linearen und binären Suchalgorithmen.

Accepted Answer

Linear: O(n), Binär: O(log n)

Answer

Linear: O(1), Binär: O(n)

Answer

Linear: O(log n), Binär: O(1)

Question 18

Welche Laufzeitkomplexität hat ein Algorithmus, der eine sortierte Liste linear durchsucht?

Accepted Answer

O(n)

Answer

O(n^2)

Answer

O(log n)

Answer

O(1)

Question 19

Wie lautet die Laufzeitkomplexität eines Algorithmus, der alle Elemente einer Liste mit n Elementen miteinander vergleicht?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n log n)

Answer

O(log n)

Question 20

Welche Aussage über die Speicherkomplexität von Algorithmen ist korrekt?

Accepted Answer

Sie gibt die benötigte Speichermenge für ein bestimmtes Eingabenvolumen an.

Answer

Sie wird in Big-Omega-Notation ausgedrückt.

Answer

Sie ist unabhängig von der Eingabegröße.

Answer

Sie ist immer geringer als die Laufzeitkomplexität.

Question 21

Welcher Algorithmentyp hat typischerweise die geringste Speicherkomplexität?

Accepted Answer

In-Place-Algorithmus

Answer

Dynamisch programmierter Algorithmus

Answer

Rekursiver Algorithmus

Answer

Backtracking-Algorithmus

Question 22

Welche Technik wird hauptsächlich verwendet, um die Laufzeitkomplexität rekursiver Algorithmen zu analysieren?

Accepted Answer

Master-Theorem

Answer

Amortisierte Analyse

Answer

Empirische Analyse

Answer

Big-O-Notation

Question 23

Welcher Faktor kann die Laufzeitkomplexität eines Algorithmus am stärksten beeinflussen?

Accepted Answer

Eingabedaten

Answer

Hardware-Architektur

Answer

Programmiersprache

Answer

Betriebssystem

Question 24

Was ist das Hauptmerkmal der asymptotischen Analyse?

Accepted Answer

Sie ignoriert Konstanten und niedrigere Ordnungsterme.

Answer

Sie ist nur für kleine Eingaben geeignet.

Answer

Sie berücksichtigt alle Terme in der Laufzeitfunktion.

Answer

Sie ist immer genauer als die Worst-Case-Analyse.

Question 25

Welches der folgenden Probleme gehört zur Komplexitätsklasse NP-vollständig?

Accepted Answer

SAT-Problem

Answer

Quicksort

Answer

Binäre Suche

Answer

Dijkstra-Algorithmus

Question 26

Welches der folgenden Symbole steht für die Größenordnung der oberen Schranke der Laufzeit eines Algorithmus?

Accepted Answer

O

Answer

Θ

Answer

σ

Answer

Ω

Question 27

Welche der folgenden Algorithmusklassen ist am effizientesten hinsichtlich der Laufzeit?

Accepted Answer

Linear

Answer

Quadratisch

Answer

Exponential

Question 28

Welche Methode der Komplexitätsanalyse dient dazu, die beste Falllaufzeit eines Algorithmus zu ermitteln?

Accepted Answer

Best-Case-Analyse

Answer

Amortisierte Analyse

Answer

Worst-Case-Analyse

Answer

Durchschnittsanalyse

Question 29

Welche Aussage über die Big-O-Notation ist korrekt?

Accepted Answer

Sie gibt die obere Schranke für das asymptotische Wachstum des Algorithmus an.

Answer

Sie gibt die minimale Laufzeit des Algorithmus an.

Answer

Sie gibt die durchschnittliche Laufzeit des Algorithmus an.

Question 30

Welche der folgenden Eigenschaften trifft auf die Reduzierbarkeitsrelation zu?

Accepted Answer

Sie ist reflexiv, transitiv und antisymmetrisch.

Answer

Sie ist weder reflexiv noch transitiv.

Answer

Sie ist transitiv, aber nicht reflexiv.

Answer

Sie ist reflexiv, aber nicht transitiv.

Question 31

Welches der folgenden Probleme gehört zur Klasse der NP-vollständigen Probleme?

Accepted Answer

3-SAT

Answer

Sortierung

Answer

Lineare Algebra

Answer

Baumsuche

Question 32

Welche Methode wird verwendet, um die Speicherkomplexität eines Algorithmus zu analysieren?

Accepted Answer

Analyse des Speicherverbrauchs

Answer

Worst-Case-Analyse

Answer

Amortisierte Analyse

Answer

Big-O-Notation

Question 33

Welche Aussage über die asymptotische Analyse ist korrekt?

Accepted Answer

Sie betrachtet das Verhalten des Algorithmus für sehr große Eingaben.

Answer

Sie betrachtet das Verhalten des Algorithmus für kleine Eingaben.

Answer

Sie betrachtet das genaue Verhalten des Algorithmus.

Question 34

Welcher der folgenden Algorithmen hat eine rekursive Struktur?

Accepted Answer

Quicksort

Answer

Sortierung durch Einfügen

Answer

Sequenzielle Suche

Answer

Binäre Suche

Question 35

Welcher der folgenden Algorithmen hat eine Laufzeitkomplexität von O(n²)?

Accepted Answer

Bubblesort

Answer

Mergesort

Answer

Heapsort

Answer

Quicksort

Question 36

Welche der aufgeführten Funktionen wächst am schnellsten?

Accepted Answer

f(n) = 2^n

Answer

f(n) = log(n)

Answer

f(n) = n

Answer

f(n) = n^3

Question 37

Was bedeutet die Landau-Notation f(n) = O(g(n))?

Accepted Answer

Im ungünstigsten Fall wächst f(n) höchstens proportional zu g(n).

Answer

f(n) wächst immer langsamer als g(n).

Answer

f(n) wächst immer schneller als g(n).

Question 38

Welche Algorithmusklasse hat die geringste Zeitkomplexität?

Accepted Answer

O(1)

Answer

O(log(n))

Answer

O(n)

Answer

O(n²)

Question 39

Welcher der folgenden Faktoren hat den größten Einfluss auf die Laufzeit eines Algorithmus?

Accepted Answer

Größe der Eingabe

Answer

Programmiersprache

Answer

Betriebssystem

Answer

Geschwindigkeit der CPU

Question 40

Was ist der Hauptzweck der Big-O-Notation?

Accepted Answer

Beschreibung der oberen Schranke für die Laufzeit eines Algorithmus.

Answer

Beschreibung der unteren Schranke für die Laufzeit eines Algorithmus.

Answer

Beschreibung der durchschnittlichen Laufzeit eines Algorithmus.

Question 41

Welcher der folgenden Algorithmen ist nicht rekursiv?

Accepted Answer

Bubblesort

Answer

Mergesort

Answer

Quicksort

Answer

Heapsort

Question 42

Was bedeutet die Angabe "Raumkomplexität O(n)"?

Accepted Answer

Der Algorithmus benötigt zusätzlichen Speicher proportional zur Größe der Eingabe.

Answer

Der Algorithmus benötigt konstanten zusätzlichen Speicher.

Answer

Der Algorithmus benötigt keinen zusätzlichen Speicher.

Question 43

Welche Aussage zur Komplexitätsanalyse ist **falsch**?

Accepted Answer

Die Komplexitätsanalyse berücksichtigt ausschließlich die Laufzeit eines Algorithmus.

Answer

Die Komplexitätsanalyse verwendet asymptotische Notation, um das Laufzeitverhalten zu beschreiben.

Answer

Die Komplexitätsanalyse hilft, die Effizienz von Algorithmen gegenüberzustellen.

Question 44

Welche asymptotische Notation beschreibt einen Algorithmus, dessen Laufzeit proportional zur Eingabegröße wächst?

Accepted Answer

O(n)

Answer

O(n²)

Answer

O(log n)

Answer

O(1)

Question 45

Welcher Suchalgorithmus weist typischerweise eine logarithmische Laufzeit auf?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Insertion Sort

Answer

Bubblesort

Question 46

Was ist der ungünstigste Fall für die Laufzeit des Sortieralgorithmus Quicksort?

Accepted Answer

O(n²)

Answer

O(n)

Answer

O(log n)

Answer

O(1)

Question 47

Welche Aussage zur Big-O-Notation ist **korrekt**?

Accepted Answer

Sie stellt eine obere Grenze für die Laufzeit eines Algorithmus dar.

Answer

Sie beschreibt die durchschnittliche Laufzeit eines Algorithmus.

Answer

Sie bestimmt die genaue Laufzeit eines Algorithmus.

Question 48

Welcher Faktor hat **keinen** Einfluss auf die Komplexität eines Algorithmus?

Accepted Answer

Die verwendete Programmiersprache

Answer

Die Größe der Eingabe

Answer

Die zugrundeliegende Datenstruktur

Question 49

Welche Aussage zur Rekursion ist **richtig**?

Accepted Answer

Rekursive Algorithmen können zu einem erhöhten Speicherbedarf führen.

Answer

Rekursive Algorithmen sind immer effizienter als iterative Algorithmen.

Answer

Rekursive Algorithmen sind immer einfacher zu verstehen als iterative Algorithmen.

Question 50

Welche Aussage zur Komplexität von Sortieralgorithmen ist **falsch**?

Accepted Answer

Bubblesort hat eine logarithmische Laufzeit.

Answer

Insertion Sort hat im besten Fall eine lineare Laufzeit.

Answer

Quicksort hat im Worst-Case eine quadratische Laufzeit.

Answer

Mergesort hat eine logarithmische Laufzeit.

Question 51

Welcher Algorithmus eignet sich besonders für die Suche in einem sortierten Array?

Accepted Answer

Binäre Suche

Answer

Hashing

Answer

Sortieren

Answer

Lineare Suche

Question 52

Welche der folgenden Komplexitätsklassen beschreibt Algorithmen mit polynomieller Laufzeit?

Accepted Answer

P

Answer

NP

Answer

PSPACE

Answer

EXPTIME

Question 53

Welches Maß beschreibt die Anzahl der Operationen, die ein Algorithmus im schlimmsten Fall ausführt?

Accepted Answer

Zeitkomplexität

Answer

Rechenkomplexität

Answer

Informationskomplexität

Answer

Raumkomplexität

Question 54

Welches Verfahren kann verwendet werden, um die asymptotische Laufzeit eines Algorithmus zu bestimmen?

Accepted Answer

Meistermethode

Answer

Suchverfahren

Answer

Sortierverfahren

Answer

Reduktionsverfahren

Question 55

Welche der folgenden Aufgaben ist NP-vollständig?

Accepted Answer

SAT-Problem

Answer

Sortierung

Answer

Suche

Question 56

Welche der folgenden Aussagen zur Komplexitätsanalyse ist richtig?

Accepted Answer

Die Komplexitätsanalyse liefert eine obere Schranke für die Laufzeit eines Algorithmus.

Answer

Die Komplexitätsanalyse kann die tatsächliche Laufzeit eines Algorithmus genau vorhersagen.

Answer

Die Komplexitätsanalyse ist nur für sequentielle Algorithmen anwendbar.

Question 57

Welche Aussage beschreibt die Beziehung zwischen der Zeitkomplexität und der Raumkomplexität eines Algorithmus?

Accepted Answer

Für einige Algorithmen kann es einen Trade-off zwischen Zeit- und Raumkomplexität geben.

Answer

Die Zeitkomplexität ist immer größer als die Raumkomplexität.

Answer

Die Raumkomplexität ist immer größer als die Zeitkomplexität.

Question 58

Welche asymptotische Notation wird verwendet, um eine Funktion zu beschreiben, die exponentiell wächst?

Accepted Answer

O(2^n)

Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Question 59

Welcher Algorithmus hat die zweitschlechteste Laufzeitkomplexität unter den folgenden?

Accepted Answer

Quicksort

Answer

Heapsort

Answer

Merge Sort

Answer

Bubblesort

Question 60

Welche der folgenden Aussagen über den Algorithmus von Dijkstra ist wahr?

Accepted Answer

Er findet den kürzesten Weg von einem Quellknoten zu allen anderen Knoten in einem gewichteten ungerichteten Graphen.

Answer

Er findet den kürzesten Weg von allen Knoten zu einem Zielknoten in einem gerichteten Graphen.

Question 61

Welche der folgenden Aussagen zum traveling Salesman problem (TSP) ist richtig?

Accepted Answer

Es ist ein NP-hartes Optimierungsproblem.

Answer

Es ist ein Entscheidungsproblem in NP.

Answer

Es hat eine polynomielle Laufzeitkomplexität.

Answer

Es kann mit einem Greedy-Algorithmus optimal gelöst werden.