Algorithmen und Komplexität: Online-Quiz für Klasse 12 Gesamtschule

Question 1

Welches Sortierverfahren benötigt keinen zusätzlichen Speicherplatz und hat eine durchschnittliche Laufzeitkomplexität von O(n²)?

Accepted Answer

Bubblesort

Answer

Quicksort

Answer

Mergesort

Answer

Insertionsort

Question 2

Welche Aussage trifft am besten auf die Laufzeitanalyse von Algorithmen zu?

Accepted Answer

Die Laufzeit hängt von der Anzahl der ausgeführten Schritte ab.

Answer

Die Laufzeit kann immer als Polynom dargestellt werden.

Answer

Asymptotische Notation liefert genaue Laufzeitwerte für alle Eingaben.

Answer

Die Laufzeitanalyse gilt nur für rekursive Algorithmen.

Question 3

Welcher Sortieralgorithmus benötigt im Durchschnitt O(n^2) Zeit?

Accepted Answer

Bubblesort

Answer

Quicksort

Answer

Mergesort

Answer

Heapsort

Question 4

Welches Sortierverfahren hat eine durchschnittliche Laufzeitkomplexität von Θ(n^2)?

Accepted Answer

Insertionsort

Answer

Quicksort

Answer

Heapsort

Answer

Mergesort

Question 5

In einem sortierten Array mit n Elementen soll ein bestimmtes Element gesucht werden. Welcher Algorithmus ist dafür am effizientesten?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Insertionsort

Answer

Heapsort

Question 6

Welcher Suchalgorithmus findet ein Element in einem sortierten Array mit n Elementen in logarithmischer Zeit?

Accepted Answer

Binäre Suche

Answer

Bubble-Sort

Answer

Quicksort

Answer

Insertionsort

Question 7

Welcher Sortieralgorithmus hat die durchschnittliche Laufzeitkomplexität O(n log n)?

Accepted Answer

Mergesort

Answer

Bubblesort

Answer

Selectionsort

Answer

Insertionsort

Question 8

Welche Option beschreibt die Zeitkomplexität O(n log n) für einen Algorithmus, wobei n die Anzahl der Elemente im Eingabe-Datensatz ist?

Accepted Answer

n * log(n)

Answer

n + log(n)

Answer

log(n) / n

Answer

n log(log(n))

Question 9

Welcher Sortieralgorithmus basiert auf dem Prinzip "Teile und herrsche"?

Accepted Answer

Quicksort

Answer

Bubblesort

Answer

Heapsort

Answer

Selectionsort

Question 10

Welches Sortierverfahren hat die höchste Laufzeitkomplexität im ungünstigsten Fall?

Accepted Answer

Bubblesort

Answer

Selectionsort

Answer

Insertionsort

Answer

Heapsort

Question 11

Welcher Algorithmus findet ein Element in einem großen, sortierten Array am schnellsten?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Bubblesort

Answer

Mergesort

Question 12

Welches Sortierverfahren hat im ungünstigsten Fall eine Laufzeitkomplexität von O(n²)?

Accepted Answer

Bubblesort

Answer

Heapsort

Answer

Quicksort

Answer

Mergesort

Question 13

Welcher Sortieralgorithmus hat im ungünstigsten Fall die längste Laufzeit und eine Komplexität von O(n²)?

Accepted Answer

Bubblesort

Answer

Quicksort

Answer

Selectionsort

Answer

Heapsort

Question 14

Welches Sortierverfahren vergleicht im ungünstigsten Fall jedes Element mit allen vorherigen Elementen und hat eine Laufzeit von O(n^2)?

Accepted Answer

Insertionsort

Answer

Quicksort

Answer

Mergesort

Answer

Heapsort

Question 15

Welches Sortierverfahren hat die beste Zeitkomplexität von O(n log n) und ist zudem stabil?

Accepted Answer

Heapsort

Answer

Bubblesort

Answer

Selectionsort

Answer

Insertionsort

Question 16

Welche Aussage beschreibt die asymptotische Notation bei der Laufzeitanalyse von Algorithmen am besten?

Accepted Answer

Sie zeigt, wie schnell die Laufzeit mit steigender Eingangsgröße wächst.

Answer

Sie gibt die genaue Laufzeit für jede Eingangsgröße an.

Answer

Sie wird nur für sehr komplexe Algorithmen verwendet.

Question 17

Welche Laufzeitanalyse gibt die höchste Anzahl an Operationen an, die ein Algorithmus für jede mögliche Eingabe benötigt?

Accepted Answer

Worst-Case-Analyse

Answer

Best-Case-Analyse

Answer

Durchschnittliche Analyse

Question 18

Welcher Algorithmus hat die beste Laufzeitkomplexität für die Suche nach einem Element in einem sortierten Array?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Jump-Suche

Question 19

Welcher Sortieralgorithmus benötigt im Durchschnitt O(n²) und im ungünstigsten Fall O(n³)?

Accepted Answer

Bubblesort

Answer

Selectionsort

Answer

Insertionsort

Answer

Mergesort

Question 20

Welches Sortierverfahren hat eine durchschnittliche Laufzeitkomplexität von O(n hoch 2)?

Accepted Answer

Insertionssort

Answer

Quicksort

Answer

Heapsort

Question 21

Welche Eigenschaften treffen auf NP-vollständige Probleme zu?

Accepted Answer

Sie sind auch NP-schwer.

Accepted Answer

Sie können durch Transformation auf ein anderes NP-vollständiges Problem gelöst werden.

Answer

Sie sind in polynomieller Zeit lösbar.

Answer

Ihre Lösung erfordert immer eine Brute-Force-Suche.

Question 22

Welche Aussage beschreibt das Prinzip der Breitensuche am besten?

Accepted Answer

Erkundet alle Knoten einer Ebene, bevor sie in die nächste Ebene übergeht.

Answer

Verwendet einen Stack, um zu besuchende Knoten zu speichern.

Answer

Ermittelt den kürzesten Weg zwischen zwei Knoten in einem Graphen.

Answer

Basiert auf dem Ansatz der Rückverfolgung durch den Graphen.

Question 23

Welche Laufzeitanalyse gibt eine Obergrenze für die Anzahl der Schritte an, die ein Algorithmus benötigt, um einen Datensatz beliebiger Größe zu bearbeiten?

Accepted Answer

Worstfallanalyse

Answer

Bestfallanalyse

Answer

Durchschnittsfallanalyse

Answer

Amortisationsanalyse

Question 24

Welcher Suchalgorithmus hat die beste Worst-Case-Laufzeit für sortierte Daten?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Tiefensuche

Answer

Breitensuche

Question 25

Welche Notation gibt in der Asymptotischen Analyse die obere Grenze für die schlechteste Laufzeit eines Algorithmus an?

Accepted Answer

O-Notation

Answer

Ω-Notation

Answer

Θ-Notation

Question 26

Was ist das zentrale Merkmal eines Algorithmus?

Accepted Answer

Eine präzise Folge eindeutiger Anweisungen zur Problemlösung.

Answer

Eine Sammlung unzusammenhängender Ideen.

Answer

Eine intuitive Problemlösung basierend auf Erfahrung.

Question 27

Bei der linearen Suche wird ein Element in einer unsortierten Liste gesucht. Wie hoch ist die Worst-Case-Laufzeitkomplexität dieser Suche in einer unsortierten Liste der Größe n?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 28

Wie hoch ist die Worst-Case-Laufzeitkomplexität des Bubble-Sort-Algorithmus, der eine Liste mit n Elementen sortiert?

Accepted Answer

O(n²)

Answer

O(n)

Answer

O(n log n)

Question 29

Welcher Vorteil ergibt sich aus der Verwendung paralleler Algorithmen?

Accepted Answer

Höhere Rechenleistung durch Nutzung mehrerer Prozessoren

Answer

Geringere Kosten als bei sequentiellen Algorithmen

Answer

Einfachere Programmierung als bei sequentiellen Algorithmen

Answer

Höhere Ergebnisgenauigkeit als bei sequentiellen Algorithmen

Question 30

Die Laufzeitkomplexität eines Algorithmus zur Berechnung des kleinsten gemeinsamen Vielfachen zweier natürlicher Zahlen beträgt O(n). Zu welcher Komplexitätsklasse gehört dieser Algorithmus?

Accepted Answer

Lineare Komplexität

Answer

Konstante Komplexität

Answer

Quadratische Komplexität

Answer

Exponentielle Komplexität

Question 31

Wie wird die Laufzeitanalyse bei Sortieralgorithmen durchgeführt?

Accepted Answer

Es wird untersucht, wie viele elementare Operationen im Verhältnis zur Größe des Arrays ausgeführt werden.

Answer

Es wird nur die absolute Zeit gemessen, die zum Sortieren eines Arrays benötigt wird.

Question 32

Welches Suchverfahren ist für die Suche nach einem Element in einem großen, sortierten Array am effizientesten?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Interpolationssuche

Answer

Hashing

Question 33

Welcher Sortieralgorithmus eignet sich am besten, um eine große, unsortierte Liste von Elementen **absteigend** zu sortieren?

Accepted Answer

Heapsort

Answer

Bubblesort

Answer

Quicksort

Answer

Insertionsort

Question 34

Welche Herausforderungen müssen Algorithmendesigner bei der Entwicklung von Algorithmen für große Datenmengen bewältigen?

Accepted Answer

Höherer Zeit- und Ressourcenbedarf für die Verarbeitung großer Datenmengen

Answer

Vereinfachte Implementierung von Algorithmen für große Datenmengen

Answer

Geringerer Speicherbedarf für die Verarbeitung großer Datenmengen

Answer

Wegfall der Notwendigkeit von Skalierbarkeitstechniken

Question 35

Wie funktioniert der Divide-and-Conquer-Ansatz bei Sortieralgorithmen? Erläutere seine Vorteile.

Accepted Answer

Der Divide-and-Conquer-Ansatz teilt das Problem in kleinere Teilprobleme, löst diese rekursiv und fügt die Lösungen zu einer Gesamtlösung zusammen. Er ist besonders effizient für große Datenmengen.

Answer

Der Divide-and-Conquer-Ansatz ist nur für kleine Datenmengen geeignet, da er komplex ist.

Answer

Der Divide-and-Conquer-Ansatz erfordert keine Rekursion und ist daher nicht für Sortierprobleme geeignet.

Answer

Der Divide-and-Conquer-Ansatz ist ineffizient, da er viele Vergleiche erfordert.

Question 36

Welches Suchverfahren benötigt im Durchschnitt O(log n) Schritte, um ein Element in einer Liste mit n Elementen zu finden?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Interpolationssuche

Question 37

Welche Komplexitätsklasse umfasst Algorithmen, die in polynomialer Zeit gelöst werden können?

Accepted Answer

P

Answer

NP

Answer

NP-vollständig

Answer

NP-schwer

Question 38

Welcher der folgenden Algorithmen ist für die Suche eines Elements in einem sortierten Array am effizientesten?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Interpolations-Suche

Answer

Hashing

Question 39

Was ist das Ziel der asymptotischen Analyse von Algorithmen?

Accepted Answer

Das Verhalten des Algorithmus für sehr große Eingaben zu bestimmen.

Answer

Die genaue Laufzeit des Algorithmus für alle Eingaben zu berechnen.

Answer

Den Speicherbedarf des Algorithmus abzuschätzen.

Answer

Die Stabilität des Algorithmus zu gewährleisten.

Question 40

Was ist eine Big-O-Notation?

Accepted Answer

Eine mathematische Notation, die die obere Schranke der Komplexität eines Algorithmus beschreibt.

Answer

Eine Methode zur Berechnung der Laufzeit eines Algorithmus.

Answer

Ein Framework zur Analyse der Stabilität eines Algorithmus.

Answer

Eine Technik zur Optimierung des Speicherbedarfs eines Algorithmus.

Question 41

Was ist der Unterschied zwischen einem Algorithmus und einem Programm?

Accepted Answer

Ein Algorithmus ist eine formale Beschreibung eines Problems, während ein Programm eine Implementierung dieses Algorithmus in einer Programmiersprache ist.

Answer

Ein Programm ist eine formale Beschreibung eines Problems, während ein Algorithmus eine Implementierung dieses Programms in einer Programmiersprache ist.

Answer

Ein Algorithmus ist eine abstrakte Idee, während ein Programm eine konkrete Implementierung ist.

Answer

Es gibt keinen Unterschied zwischen einem Algorithmus und einem Programm.

Question 42

Welcher der folgenden Algorithmen ist probabilistisch?

Accepted Answer

Zufallszahlengenerator

Answer

Quicksort

Answer

Merge Sort

Answer

Binäre Suche

Question 43

Was ist das Halteproblem?

Accepted Answer

Das Problem, zu bestimmen, ob ein Programm für jede Eingabe anhält.

Answer

Das Problem, zu bestimmen, ob ein Programm für eine bestimmte Eingabe anhält.

Answer

Das Problem, zu bestimmen, ob ein bestimmtes Programm korrekt ist.

Answer

Das Problem, zu bestimmen, ob ein Programm effizient ist.

Question 44

Was ist das Grundprinzip einer Hashtabelle und in welchem Anwendungsfall ist ihr Einsatz besonders vorteilhaft?

Accepted Answer

Eine Hashtabelle speichert Schlüssel-Wert-Paare und ermöglicht eine schnelle Suche nach dem Schlüssel.

Accepted Answer

Hashtabellen ordnen Schlüsseln eindeutige Array-Indizes zu, basierend auf einer Hashfunktion.

Accepted Answer

Hashtabellen sind besonders nützlich bei der Suche in unsortierten Listen, da sie schnelle Zugriffszeiten unabhängig von der Datenanordnung bieten.

Answer

Hashtabellen sind nicht effizient für große Datensätze, da sie eine begrenzte Array-Größe haben.

Question 45

Erläutere den Unterschied zwischen `Big-O`- und `Ω`-Notation. Nenne einen Algorithmus, der in beiden Notationen ausgedrückt werden kann.

Accepted Answer

`Big-O`-Notation beschreibt die obere Grenze, während `Ω`-Notation die untere Grenze der Laufzeit eines Algorithmus angibt.

Answer

`Big-O`-Notation beschreibt die untere Grenze, während `Ω`-Notation die obere Grenze der Laufzeit eines Algorithmus angibt.

Answer

Beide Notationen beschreiben die durchschnittliche Fallkomplexität eines Algorithmus.

Answer

Die beiden Notationen sind gleichbedeutend.

Question 46

Welche Komplexität hat ein Algorithmus, der eine Liste mit n Elementen sequenziell durchläuft?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 47

Welches Sortierverfahren behält die relative Reihenfolge gleicher Elemente bei?

Accepted Answer

Merge Sort

Answer

Bubblesort

Answer

Quicksort

Answer

Heapsort

Question 48

Was beschreibt ein asymptotisches Landau-Symbol?

Accepted Answer

Das Verhalten einer Funktion für große Eingaben

Answer

Die Laufzeit eines Algorithmus als exakte Formel

Answer

Einen Algorithmus zur Codeoptimierung

Answer

Eine Datenstruktur für umfangreiche Datenmengen

Question 49

Welches Suchverfahren benötigt O(log n) Operationen zur Suche in einem sortierten Array?

Accepted Answer

Binäres Suchen

Answer

Sequenzielles Suchen

Answer

Interpolations-Suchen

Answer

Hashtabelle

Question 50

Was unterscheidet deterministische von nicht-deterministischen Algorithmen?

Accepted Answer

Deterministische Algorithmen liefern immer die gleiche Ausgabe, nicht-deterministische nicht.

Answer

Nicht-deterministische Algorithmen sind grundsätzlich schneller als deterministische.

Answer

Deterministische Algorithmen sind immer effizienter als nicht-deterministische.

Answer

Es besteht kein Unterschied zwischen deterministischen und nicht-deterministischen Algorithmen.

Question 51

Welche Komplexität hat ein Algorithmus, der n³ Operationen ausführt?

Accepted Answer

O(n³)

Answer

O(1)

Answer

O(log n)

Answer

O(n)

Question 52

Welcher der folgenden Algorithmen ist für große Eingaben ineffizient?

Accepted Answer

Bubble Sort

Answer

Binary Search

Answer

Quick Sort

Answer

Merge Sort

Question 53

Was beschreibt die Zeitkomplexität eines Algorithmus?

Accepted Answer

Die Anzahl der Operationen für eine bestimmte Eingabe

Answer

Den benötigten Speicherplatz

Answer

Die exakte Laufzeit auf einem bestimmten Prozessor

Answer

Die Anzahl der enthaltenen Anweisungen

Question 54

Was ist ein Beispiel für einen nichtdeterministischen Algorithmus und in welchen Bereichen wird er eingesetzt?

Accepted Answer

Monte-Carlo-Algorithmus

Answer

Dijkstra-Algorithmus

Answer

Quicksort-Algorithmus

Answer

Binäre Suche

Question 55

Was beschreibt die Big-O-Notation?

Accepted Answer

Das Wachstum der Laufzeit eines Algorithmus mit der Eingabegröße

Answer

Die maximale Laufzeit eines Algorithmus

Answer

Die Laufzeit eines Algorithmus für eine bestimmte Eingabegröße

Answer

Die Konstanten in der Laufzeit eines Algorithmus

Question 56

Frage: Algorithmen für Optimierungsprobleme:

Nenne zwei spezifische Algorithmen, die für die Lösung von Optimierungsproblemen entwickelt wurden.

Accepted Answer

Simplex-Algorithmus

Accepted Answer

Branch-and-Bound-Algorithmus

Answer

Dijkstra-Algorithmus

Question 57

Welche der folgenden Komplexitätsklassen beschreibt Algorithmen, die in polynomieller Zeit lösbar sind?

Accepted Answer

P

Answer

LOGSPACE

Answer

EXPTIME

Answer

NP

Question 58

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

Accepted Answer

Binäresuchen

Answer

Selektionssort

Answer

Quicksort

Answer

Lineare Suche

Question 59

Wie lautet die Laufzeitkomplexität des Quicksort-Algorithmus?

Accepted Answer

O(n log(n))

Answer

O(n)

Answer

O(log(n))

Answer

O(n^2)

Question 60

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

Accepted Answer

Merge Sort

Answer

Radix Sort

Answer

Bubble Sort

Answer

Hill Climbing

Question 61

Was ist das Ziel der Komplexitätsanalyse?

Accepted Answer

Messung des Ressourcenbedarfs eines Algorithmus

Answer

Implementierung von Algorithmen

Answer

Entwicklung von Algorithmen

Question 62

Welcher der folgenden Algorithmen ist eine heuristische Suchmethode?

Accepted Answer

A*-Algorithmus

Answer

Bellman-Ford-Algorithmus

Answer

Dijkstra-Algorithmus

Answer

Breadth-First-Search-Algorithmus

Question 63

Welcher der folgenden Algorithmen ist ein probabilistischer Algorithmus?

Accepted Answer

Monte-Carlo-Algorithmus

Answer

Greedy-Algorithmus

Answer

Quicksort

Answer

Binäresuchen

Question 64

Wie wird ein Problem als NP-vollständig bewiesen?

Accepted Answer

Durch Reduktion eines bekannten NP-vollständigen Problems auf das zu beweisende Problem.

Answer

Induktionsbeweis.

Answer

Direkter Beweis.