Algorithmen und Komplexität: Online-Quiz für Klasse 11 Informatik

Question 1

Welcher Suchalgorithmus ist für die Suche in einer sortierten Liste mit **n** Elementen am effizientesten?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Hashing

Answer

Interpolationssuche

Question 2

Wie lautet die Laufzeitkomplexität des Bubble-Sort-Algorithmus in Big-O-Notation?

Accepted Answer

O(n²)

Answer

O(n)

Answer

O(n log(n))

Answer

O(1)

Question 3

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

Accepted Answer

f(n) wächst langsamer oder gleich schnell wie g(n) für große n.

Answer

f(n) wächst schneller als g(n) für große n.

Answer

f(n) ist für alle n kleiner oder gleich g(n).

Answer

f(n) ist eine Konstante.

Question 4

Welcher Sortieralgorithmus ist am effizientesten für eine Liste, die bereits fast sortiert ist?

Accepted Answer

Insertionsort

Answer

Bubblesort

Answer

Mergesort

Answer

Quicksort

Question 5

Welche Aussage zur Laufzeitkomplexität des Bubble-Sort-Algorithmus ist korrekt?

Accepted Answer

O(n²), da im schlimmsten Fall für jeden Vergleich zwei Durchläufe durch die Liste nötig sind.

Answer

O(n), da eine Liste mit n Elementen im Durchschnitt in einem Durchlauf sortiert werden kann.

Answer

O(n log n), da Bubble-Sort eine Liste durch wiederholtes Teilen und Vergleichen sortiert.

Answer

O(log n), da Bubble-Sort eine Liste durch wiederholtes Vertauschen benachbarter Elemente sortiert.

Question 6

Welcher Sortieralgorithmus aus der Liste hat die schlechteste Laufzeitkomplexität von O(n^2)?

Accepted Answer

Bubblesort

Answer

Quicksort

Answer

Mergesort

Answer

Heapsort

Question 7

Welcher Algorithmus ist optimal für die Suche in einem sortierten Array?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Interpolationssuche

Question 8

Welche Algorithmen haben im schlimmsten Fall eine Laufzeitkomplexität von O(n²)?

Accepted Answer

Bubble-Sort

Accepted Answer

Selection-Sort

Answer

Merge-Sort

Answer

Binäre Suche

Question 9

Was beschreibt die Komplexität eines Algorithmus?

Accepted Answer

Die Ressourcen, die er benötigt

Answer

Die Anzahl der Schritte, die er ausführen kann

Answer

Die Geschwindigkeit, mit der er ein Problem löst

Question 10

Welcher Algorithmus benötigt im ungünstigsten Fall die meisten Schritte, um ein Element in einem ungeordneten Array zu finden?

Accepted Answer

Lineare Suche

Answer

Binäre Suche

Answer

Interpolationssuche

Answer

Hash-Tabelle

Question 11

Welches Suchverfahren findet in einer sortierten Liste mit n Elementen ein bestimmtes Element mit einer asymptotischen Worst-Case-Komplexität von O(log2(n))?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Hashtabelle

Answer

Breadth-First-Search

Question 12

Was ist das zentrale Prinzip von Greedy-Algorithmen?

Accepted Answer

Wähle bei jedem Schritt die Option, die den aktuellen Zustand verbessert, auch wenn sie nicht zur besten Gesamtlösung führt.

Answer

Betrachte alle möglichen zukünftigen Zustände und wähle den mit dem besten erwarteten Ergebnis.

Answer

Verwende eine zufällige Strategie, um Entscheidungen zu treffen.

Answer

Wähle die Option, die den größten unmittelbaren Vorteil bringt, ohne die langfristigen Folgen zu berücksichtigen.

Question 13

Wie funktioniert Rekursion?

Accepted Answer

Ein Algorithmus ruft sich selbst mit kleineren Teilen des Problems auf.

Answer

Ein Algorithmus wiederholt sich, bis das Problem gelöst ist.

Answer

Ein Algorithmus speichert Zwischenergebnisse.

Question 14

Welches Merkmal kennzeichnet einen rekursiven Algorithmus?

Accepted Answer

Rekursive Algorithmen rufen sich selbst auf.

Answer

Rekursive Algorithmen verwenden Schleifen.

Answer

Rekursive Algorithmen nutzen eine binäre Suche.

Answer

Rekursive Algorithmen sind nichtdeterministisch.

Question 15

Welcher Algorithmus aus der Liste verwendet das Prinzip der Rekursion?

Accepted Answer

Faktorielle Berechnung

Answer

Bubble-Sort

Answer

Binäre Suche

Answer

Quicksort

Question 16

Welches Sortierverfahren vergleicht jedes Element im ungünstigsten Fall mit allen anderen Elementen und hat daher eine Laufzeitkomplexität von Θ(n²)?

Accepted Answer

Bubble-Sort

Answer

Insertion-Sort

Answer

Merge-Sort

Answer

Quick-Sort

Question 17

Welche Aussage beschreibt die Komplexitätsklasse P am treffendsten?

Accepted Answer

P umfasst Probleme, die von einer deterministischen Turingmaschine in polynomieller Zeit gelöst werden können.

Answer

P umfasst Probleme, die von einer nichtdeterministischen Turingmaschine in polynomieller Zeit gelöst werden können.

Answer

P umfasst Probleme, die von einem Quantencomputer in polynomieller Zeit gelöst werden können.

Answer

P umfasst Probleme, die von einem klassischen Computer in konstanter Zeit gelöst werden können.

Question 18

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

Accepted Answer

Bubblesort

Answer

Quicksort

Answer

Mergesort

Question 19

Beschreibe das grundlegende Funktionsprinzip eines Greedy-Algorithmus und erläutere, wie er sich von anderen Algorithmen unterscheidet.

Accepted Answer

Greedy-Algorithmen treffen bei jedem Schritt lokale Entscheidungen, ohne die langfristigen Auswirkungen zu berücksichtigen.

Answer

Greedy-Algorithmen garantieren immer ein optimales Gesamtergebnis.

Answer

Greedy-Algorithmen sind ausschließlich für Sortieraufgaben geeignet.

Answer

Greedy-Algorithmen sind immer rekursiv.

Question 20

Welche Größe gibt die höchste Anzahl an elementaren Operationen an, die ein Algorithmus im ungünstigsten Fall für eine Eingabe der Größe n ausführt?

Accepted Answer

Worst-Case-Komplexität

Answer

Durchschnittskomplexität

Question 21

Welches Sortierverfahren garantiert immer die beste Laufzeitkomplexität im ungünstigsten Fall für eine ungeordnete Liste mit n Elementen?

Accepted Answer

Merge Sort

Answer

Insertionsort

Answer

Bubblesort

Answer

Quicksort

Question 22

Welche Laufzeitkomplexität hat die binäre Suche?

Accepted Answer

Logarithmische Zeit (O(log n))

Answer

Konstante Zeit (O(1))

Answer

Quadratische Zeit (O(n^2))

Answer

Exponentielle Zeit (O(2^n))

Question 23

Welche Zeitkomplexität hat der Bubblesort-Algorithmus?

Accepted Answer

O(n²)

Answer

O(1)

Answer

O(n)

Answer

O(log n)

Question 24

Welche Eigenschaft trifft auf den QuickSort-Algorithmus zu?

Accepted Answer

Er ist rekursiv.

Answer

Er ist stabil.

Answer

Seine durchschnittliche Laufzeitkomplexität ist O(n²).

Question 25

Welche Aussage beschreibt die Zeitkomplexität des Merge-Sort-Algorithmus korrekt?

Accepted Answer

O(n log n)

Answer

O(n)

Answer

O(n^2)

Question 26

Wozu dient Rekursion in Algorithmen?

Accepted Answer

Zerlegen komplexer Probleme in kleinere, rekursiv lösbare Teilprobleme.

Answer

Steigerung der Effizienz von Algorithmen.

Answer

Speichern von Daten in unterschiedlichen Datenstrukturen.

Answer

Erstellen grafischer Benutzeroberflächen.

Question 27

Welche Aussage beschreibt die Worst-Case-Laufzeitkomplexität eines Sortieralgorithmus am besten?

Accepted Answer

Die maximale Anzahl an Schritten, die der Algorithmus im ungünstigsten Fall ausführen kann.

Answer

Die minimale Anzahl an Schritten, die der Algorithmus benötigt, um eine Liste zu sortieren.

Answer

Die Anzahl der Vergleiche, die der Algorithmus während der Sortierung durchführt.

Answer

Die durchschnittliche Anzahl an Schritten, die der Algorithmus benötigt, um eine Liste zu sortieren.

Question 28

Was beschreibt die Effizienz eines Algorithmus?

Accepted Answer

Die optimale Nutzung von Ressourcen wie Zeit und Speicher zur Problemlösung.

Answer

Nur die Worst-Case-Komplexität.

Answer

Unabhängigkeit von der Eingabegröße.

Answer

Unmöglichkeit mathematischer Bestimmung.

Question 29

Ein Algorithmus hat eine Laufzeitkomplexität von O(n²). Wenn sich die Anzahl der Elemente in der Eingabe verdoppelt, um welchen Faktor erhöht sich dann die Laufzeit des Algorithmus?

Accepted Answer

4

Answer

2

Answer

Einen konstanten Faktor

Answer

Ändert sich nicht.

Question 30

Welcher Sortieralgorithmus teilt ein unsortiertes Array schrittweise in kleinere, sortierte Teile und fügt diese dann zusammen, um ein vollständig sortiertes Array zu erhalten?

Accepted Answer

Zusammenführungssortierung

Answer

Blasensortierung

Answer

Quicksortierung

Answer

Einfügesortierung

Question 31

Was ist ein wesentliches Merkmal eines Algorithmus?

Accepted Answer

Eine genaue Beschreibung einer endlichen Abfolge von Schritten zur Problemlösung.

Answer

Eine Analyse der Effizienz eines Algorithmus.

Answer

Eine Speicherstruktur zur effizienten Datenorganisation.

Answer

Eine Überprüfung der syntaktischen Korrektheit eines Codes.

Question 32

Welche Suchmethode hat die schlechteste Laufzeitkomplexität, um das kleinste Element in einer unsortierten Liste mit n Elementen zu finden?

Accepted Answer

Sequenzielle Suche

Answer

Binäre Suche

Answer

Interpolationssuche

Question 33

Was bedeutet es, wenn ein Problem als NP-vollständig bezeichnet wird?

Accepted Answer

B. Es ist mindestens so schwierig wie jedes andere NP-Problem.

Answer

A. Es kann in polynomialer Zeit gelöst werden.

Answer

C. Es kann mit einem Brute-Force-Algorithmus effizient gelöst werden.

Answer

D. Es ist trivial zu lösen.

Question 34

Welcher rekursive Sortieralgorithmus teilt eine Liste wiederholt in zwei Hälften, sortiert diese Hälften und fügt sie dann zu einer sortierten Liste zusammen?

Accepted Answer

Mergesort

Answer

Quicksort

Answer

Bubblesort

Question 35

Welcher Algorithmus garantiert die beste Laufzeit im schlimmsten Fall?

Accepted Answer

Mergesort

Answer

Bubblesort

Answer

Quicksort

Question 36

Kann ein Algorithmus mit linearer Laufzeitkomplexität O(n) rekursiv sein?

Accepted Answer

Ja, das ist möglich.

Answer

Nein, lineare Algorithmen sind nicht rekursiv.

Question 37

Analysiere die Laufzeitkomplexität des folgenden Codeausschnitts: `for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) {...} }`

Accepted Answer

O(n²)

Answer

O(n)

Answer

O(n³)

Answer

O(log n)

Question 38

Worin besteht der wesentliche Unterschied zwischen stabilen und instabilen Sortieralgorithmen?

Accepted Answer

Bei stabilen Algorithmen bleiben Elemente mit gleichen Werten in der sortierten Reihenfolge, während sie bei instabilen Algorithmen ihre Reihenfolge ändern können.

Answer

Stabile Algorithmen sind immer effizienter als instabile Algorithmen.

Answer

Instabile Algorithmen garantieren eine aufsteigende Sortierung, während stabile Algorithmen eine beliebige Reihenfolge erzeugen können.

Answer

Die Stabilität ist nur für numerische Datentypen relevant.

Question 39

Ein rekursiver Algorithmus berechnet die Fakultät einer natürlichen Zahl n. Bei jedem Aufruf verringert sich n um 1. Wie hoch ist die worst-case Laufzeitkomplexität dieses Algorithmus?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 40

Welcher Suchalgorithmus weist bei einer sortierten Liste von n Elementen die beste asymptotische Komplexität zum Auffinden eines bestimmten Elements auf?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Interpolations-Suche

Answer

Ternäre Suche

Question 41

Welcher Suchalgorithmus findet ein Element in einem binären Suchbaum mit n Knoten am schnellsten im schlimmsten Fall?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Tiefensuche

Answer

Breitensuche

Question 42

Wie fügt man einen Knoten in einen binären Suchbaum ein?

Accepted Answer

Vergleiche den einzufügenden Wert mit dem Wert des aktuellen Knotens. Gehe links, wenn kleiner, rechts, wenn größer.

Answer

Finde das erste Blatt mit einem Wert größer oder gleich dem einzufügenden Wert und füge dort ein.

Answer

Füge den Wert an der Wurzel ein und sortiere den Baum neu.

Answer

Teile den Baum in zwei Hälften und füge in die kleinere Hälfte ein.

Question 43

Welcher der folgenden Sortieralgorithmen hat eine Laufzeitkomplexität von O(n log n) und funktioniert unabhängig von der Reihenfolge der Eingabe?

Accepted Answer

Quicksort

Answer

Bubblesort

Answer

Insertionsort

Answer

Selectionsort

Question 44

Wie lautet die rekursive Definition des Euklidischen Algorithmus?

Accepted Answer

ggT(a, b) = ggT(b, a % b), wenn a != 0 und b != 0

Answer

ggT(a, b) = a, wenn b = 0

Answer

ggT(a, b) = a * b, wenn a != 0 und b != 0

Answer

ggT(a, b) = ggT(a - b, b) wenn a > b

Question 45

Welcher der folgenden Algorithmen kann nicht zur Suche in sortierten Daten verwendet werden?

Accepted Answer

Breadth-First-Suche

Answer

Binäre Suche

Answer

Interpolationssuche

Answer

Lineare Suche

Question 46

Welche Art von Algorithmusanalyse betrachtet die Anzahl der ausgeführten Operationen für eine gegebene Eingabe?

Accepted Answer

Zeitkomplexitätsanalyse

Answer

Raumkomplexitätsanalyse

Answer

Worst-Case-Analyse

Answer

Amortisierte Analyse

Question 47

Welche ist die primäre Funktion der asymptotischen Notation bei der Analyse von Algorithmen?

Accepted Answer

Algorithmen basierend auf ihrem Wachstumsverhalten in Komplexitätsklassen einteilen.

Answer

Die genaue Laufzeit eines Algorithmus für jede Eingabe vorhersagen.

Answer

Anleitungen zur Implementierung effizienter Algorithmen liefern.

Question 48

Welche Methode verwendet der Sortieralgorithmus Heap Sort, um einen Heap zu erstellen?

Accepted Answer

Heapifizieren

Answer

Zusammenführen

Answer

Partitionieren

Answer

Einfüge-Sortierung

Question 49

Wie funktioniert der Prim-Algorithmus und wie wird er verwendet, um minimale Spannbäume in ungerichteten, gewichteten Graphen zu finden?

Accepted Answer

Der Prim-Algorithmus wählt schrittweise Kanten mit dem niedrigsten Gewicht aus, um einen wachsenden Baum aufzubauen, der alle Knoten des Graphen verbindet.

Answer

Der Prim-Algorithmus wählt zufällig Kanten aus, bis ein Baum entsteht.

Answer

Der Prim-Algorithmus findet den kürzesten Weg zwischen allen Knotenpaaren im Graphen.

Question 50

Wie funktioniert der Quicksort-Algorithmus?

Accepted Answer

Teilt das Array in ein Pivot-Element und zwei Teilarrays auf, sortiert diese rekursiv und fügt sie zusammen.

Answer

Sucht das größte Element im Array und stellt es ans Ende.

Answer

Vergleicht jedes Element mit allen anderen Elementen im Array.

Answer

Sucht das kleinste Element im Array und stellt es an den Anfang.

Question 51

Welcher Suchalgorithmus hat die niedrigste Laufzeitkomplexität, um ein Element in einem sortierten Array zu finden?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Interpolationssuche

Answer

Hash-Suche

Question 52

Welcher der folgenden Sortieralgorithmen hat im ungünstigsten Fall die schlechteste Laufzeitkomplexität?

Accepted Answer

Bubblesort

Answer

Quicksort

Answer

Mergesort

Answer

Heapsort

Question 53

Welcher Algorithmus hat bei einer **fast** sortierten Liste die beste **durchschnittliche** Laufzeit?

Accepted Answer

Insertionsort

Answer

Bubblesort

Answer

Selectionsort

Answer

Mergesort

Question 54

Frage: Erläutere die grundlegenden Unterschiede zwischen sequenziellen und parallelen Algorithmen. Beschreibe ihre jeweiligen Vor- und Nachteile.

Accepted Answer

Sequenzielle Algorithmen führen Anweisungen in einer festgelegten Reihenfolge aus, während parallele Algorithmen mehrere Anweisungen gleichzeitig ausführen können.

Accepted Answer

Sequenzielle Algorithmen eignen sich gut für Probleme, die eine große Datenmenge in kleinen Schritten verarbeiten müssen.

Answer

Parallele Algorithmen sind immer schneller als sequenzielle Algorithmen.

Answer

Parallele Algorithmen sind einfacher zu implementieren als sequenzielle Algorithmen.

Question 55

Welche Aussage beschreibt die Laufzeitkomplexität der linearen Suche korrekt?

Accepted Answer

Linear (O(n))

Answer

Konstant (O(1))

Answer

Logarithmisch (O(log n))

Answer

Quadratisch (O(n^2))

Question 56

Welcher Sortieralgorithmus ist in der Regel für umfangreiche Datenmengen am effizientesten?

Accepted Answer

Quicksort (Schnellsortierung)

Answer

Bubblesort

Answer

Insertionsort (einfaches Einfügen)

Answer

Selectionsort (Auswählsortierung)

Question 57

Was ist der Hauptzweck des Heap-Sort-Algorithmus?

Accepted Answer

Sortieren einer Liste in aufsteigender oder absteigender Reihenfolge

Answer

Suchen eines Elements in einer unsortierten Liste

Answer

Umwandeln eines ungerichteten Graphen in einen gerichteten Graphen

Answer

Partitionieren einer Menge von Elementen

Question 58

Welche der folgenden Aussagen beschreibt die Laufzeit eines Algorithmus korrekt?

Accepted Answer

Die Laufzeit gibt die Anzahl der Operationen an, die der Algorithmus im schlimmsten Fall für eine Eingabe einer bestimmten Größe ausführt.

Answer

Die Laufzeit ist eine Schätzung der maximal möglichen Laufzeit.

Answer

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

Question 59

Welcher Sortieralgorithmus hat eine Laufzeitkomplexität von O(n²)?

Accepted Answer

Bubblesort

Answer

Mergesort

Answer

Quicksort

Answer

Heapsort

Question 60

Was ist der Unterschied zwischen der Big-O-Notation und der Θ-Notation?

Accepted Answer

Die Θ-Notation beschreibt die enge obere und untere Grenze der Laufzeit, während die Big-O-Notation nur die obere Grenze beschreibt.

Answer

Die Big-O-Notation ist genauer als die Theta-Notation.

Answer

Die Θ-Notation ist nur für lineare Laufzeitfunktionen anwendbar.

Question 61

Was ist die Aufgabe eines Suchalgorithmus?

Accepted Answer

Ein Element in einer Datenstruktur zu finden.

Answer

Algorithmen zu entwerfen.

Answer

Daten in einer Datenbank zu speichern.

Answer

Eine Datenstruktur zu sortieren.

Question 62

Was ist der Unterschied zwischen rekursiven und iterativen Algorithmen?

Accepted Answer

Rekursive Algorithmen rufen sich selbst auf, während iterative Algorithmen Schleifen verwenden.

Answer

Rekursive Algorithmen können nur für einfache Probleme verwendet werden.

Answer

Iterative Algorithmen sind immer einfacher zu schreiben als rekursive Algorithmen.

Answer

Rekursive Algorithmen sind immer effizienter als iterative Algorithmen.

Question 63

Welches der folgenden Probleme kann nicht effizient mit einem Algorithmus gelöst werden?

Accepted Answer

Das Halteproblem

Answer

Die Berechnung des kleinsten gemeinsamen Vielfachen zweier Zahlen

Answer

Die Suche nach dem kürzesten Weg in einem Graphen

Answer

Die Sortierung einer Liste von Zahlen

Question 64

Was ist die NP-Vollständigkeit?

Accepted Answer

Eine Eigenschaft von Problemen, die leicht zu überprüfen, aber schwer zu lösen sind.

Answer

Eine Eigenschaft von Laufzeitkomplexitätsfunktionen, die immer positiv sind.

Answer

Eine Eigenschaft von Algorithmen, die immer die optimale Lösung finden.

Answer

Eine Eigenschaft von Datenstrukturen, die eine effiziente Speicherung ermöglichen.