Algorithmen lernen: Interaktive Quizze für Klasse 13 Informatik

Question 1

Welcher Sortieralgorithmus eignet sich am besten für große, bereits nahezu sortierte Datenmengen?

Accepted Answer

Insertionsort

Answer

Bubblesort

Answer

Quicksort

Answer

Heapsort

Question 2

Welche Methode wird in der rekursiven Implementierung des Binärsuchalgorithmus angewandt?

Accepted Answer

Teile-und-Herrsche

Answer

Zurückverfolgung

Answer

Gieriges Vorgehen

Answer

Dynamische Programmierung

Question 3

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

Accepted Answer

O(n²)

Answer

O(n)

Answer

O(n log n)

Answer

O(log n)

Question 4

Welche Datenstruktur wird in Heapsort verwendet, um den Baum darzustellen?

Accepted Answer

Feld

Answer

Verkettete Liste

Answer

Stapel

Answer

Warteschlange

Question 5

Welche Eigenschaft beschreibt das asymptotische Laufzeitverhalten eines Algorithmus?

Accepted Answer

Das Verhalten des Algorithmus für große Eingaben

Answer

Die Anzahl der Operationen, die der Algorithmus ausführt

Answer

Die Zeit, die der Algorithmus zur Ausführung benötigt

Answer

Die Speicheranforderungen des Algorithmus

Question 6

Welche Technik wird verwendet, um die Effizienz eines Algorithmus anhand der Anzahl der ausgeführten Operationen zu messen?

Accepted Answer

Groß-O-Notation

Answer

Omega-Notation

Answer

Theta-Notation

Answer

Klein-o-Notation

Question 7

Welche Laufzeitkomplexität hat der Quicksort-Algorithmus, wenn die Eingabe bereits sortiert ist?

Accepted Answer

O(n)

Answer

O(n log n)

Answer

O(n^2)

Answer

O(2^n)

Question 8

Welche Komplexitätsklasse umfasst Probleme, die in polynomialer Zeit lösbar sind?

Accepted Answer

P

Answer

L

Answer

NP

Answer

EXPTIME

Question 9

Welches rekursive Verfahren löst das Problem, Scheiben von einem Startturm zu einem Zielturm zu bewegen, wobei nur eine Scheibe auf einmal bewegt werden darf?

Accepted Answer

Turm von Hanoi

Answer

Fibonacci-Zahlen

Answer

Quicksort

Answer

Insertionsort

Question 10

Welches Problem ist NP-vollständig?

Accepted Answer

Hamilton-Kreis

Answer

Shortest Path

Answer

Bubblesort

Answer

Mergesort

Question 11

Welche Laufzeitkomplexität besitzt der folgende Algorithmus: `for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ... } }`?

Accepted Answer

O(n²)

Answer

O(n)

Answer

O(n log n)

Answer

O(2ⁿ)

Question 12

Welche rekursive Funktion berechnet korrekt die Fakultät einer natürlichen Zahl?

Accepted Answer

int fakultaet(int n) { if (n == 0) return 1; else return n * fakultaet(n - 1); }

Answer

int fakultaet(int n) { return n * fakultaet(n - 1); }

Answer

int fakultaet(int n) { for (int i = 1; i <= n; i++) { return i * fakultaet(i - 1); } }

Answer

int fakultaet(int n) { while (n > 0) { return n * fakultaet(n - 1); } }

Question 13

Welche Komplexitätsklasse umfasst Algorithmen, deren Laufzeit durch ein Polynom beschränkt ist?

Accepted Answer

P

Answer

NP

Answer

EXP

Answer

NP-vollständig

Question 14

Welche Methode des Quicksorts wählt konsistent das erste Element des Arrays als Pivot?

Accepted Answer

Erste-Element-Methode

Answer

Zufalls-Element-Methode

Answer

Median-der-Median-Methode

Answer

Dreier-Elemente-Median-Methode

Question 15

Welcher Sortieralgorithmus behält die relative Reihenfolge gleicher Elemente bei und ist daher stabil?

Accepted Answer

Mergesort

Answer

Quicksort

Answer

Heapsort

Answer

Selectionsort

Question 16

Welche Komplexitätsklasse umfasst alle Entscheidungsprobleme, die in polynomieller Zeit gelöst werden können?

Accepted Answer

P

Answer

NP

Answer

NP-vollständig

Answer

NP-schwer

Question 17

Welche Funktion ist durch die folgende rekursive Definition charakterisiert: f(n) = f(n - 1) + n, mit f(1) = 1?

Accepted Answer

f(n) = n * (n + 1) / 2

Answer

f(n) = n + 1

Answer

f(n) = 2^n - 1

Answer

f(n) = n^2

Question 18

Welches Suchverfahren ist für sortierte Daten am effizientesten?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Interpolationssuche

Answer

Hashing

Question 19

Welche Aussage zur Laufzeit eines Algorithmus ist korrekt?

Accepted Answer

Die Laufzeit kann abhängig von der Größe der Eingabe variieren.

Answer

Die Laufzeit ist immer konstant.

Answer

Die Laufzeit ist immer linear proportional zur Anzahl der Eingabedaten.

Answer

Die Laufzeit ist immer logarithmisch proportional zur Anzahl der Eingabedaten.

Question 20

Welcher Algorithmentyp eignet sich am besten, um das kleinste Element in einer sortierten Liste zu finden?

Accepted Answer

Suchverfahren

Answer

Sortierverfahren

Answer

Rekursive Algorithmen

Answer

Hashing-Algorithmen

Question 21

Welche Datenstruktur ermöglicht eine effiziente Implementierung einer Warteschlange?

Accepted Answer

Verkettete Liste

Answer

Array

Answer

Hashtabelle

Answer

Binärer Suchbaum

Question 22

Welcher Begriff beschreibt die Anzahl der Operationen, die ein Algorithmus im ungünstigsten Fall benötigt?

Accepted Answer

Zeitkomplexität

Answer

Laufzeit

Answer

Komplexität

Answer

Asymptotische Komplexität

Question 23

Welcher Sortieralgorithmus fügt das kleinste Element aus dem unsortierten Teil iterativ in den sortierten Teil ein?

Accepted Answer

Insertionsort

Answer

Bubblesort

Answer

Quicksort

Answer

Selectionsort

Question 24

Welche Laufzeitanalyse untersucht die höchstmögliche Anzahl an Operationen, die ein Algorithmus unabhängig von der Eingabedatenmenge benötigt?

Accepted Answer

Worst-Case-Analyse

Answer

Durchschnittsfallanalyse

Answer

Bestfallanalyse

Answer

Amortisierte Analyse

Question 25

Welcher Suchalgorithmus teilt den Suchraum wiederholt in zwei Hälften und vergleicht den Suchbegriff mit der Mitte, bis das gesuchte Element gefunden oder ausgeschlossen wurde?

Accepted Answer

Binäre Suche

Answer

Breadth-First-Suche

Answer

Depth-First-Suche

Answer

Lineare Suche

Question 26

Welche Komplexitätsklasse beschreibt Algorithmen, deren Laufzeit durch ein Polynom mit festem Grad begrenzt ist?

Accepted Answer

P

Answer

NP

Answer

NPC

Answer

EXP

Question 27

Welches Baumdatenmodell ermöglicht es jedem Knoten, maximal zwei untergeordnete Knoten zu haben?

Accepted Answer

Binärbaum

Answer

B-Baum

Answer

AVL-Baum

Answer

Rot-Schwarz-Baum

Question 28

Welcher Sortieralgorithmus verwendet Buckets, um Elemente je nach ihrem Wert zu gruppieren und innerhalb dieser Buckets zu sortieren?

Accepted Answer

Radixsort

Answer

Heapsort

Answer

Quicksort

Answer

Mergesort

Question 29

Welcher Sortieralgorithmus ist ein stabiler Algorithmus, der die relative Reihenfolge gleicher Elemente beibehält?

Accepted Answer

Mergesort

Answer

Bubblesort

Answer

Insertionsort

Answer

Quicksort

Question 30

Welche Laufzeitanalyse schätzt die durchschnittliche Anzahl an Operationen, die ein Algorithmus für eine bestimmte Eingabegröße ausführen wird?

Accepted Answer

Durchschnittsfallanalyse

Answer

Bestfallanalyse

Answer

Worst-Case-Analyse

Answer

Amortisierte Analyse

Question 31

Welcher Sortieralgorithmus vergleicht jeweils zwei benachbarte Elemente und tauscht sie, falls sie nicht in der richtigen Reihenfolge sind? Seine Laufzeit beträgt O(n²)?

Accepted Answer

Bubblesort

Answer

Schnellsortierung

Answer

Heapsort

Answer

Mergesort

Question 32

Welcher Suchalgorithmus zeichnet sich durch eine logarithmische Laufzeit O(log n) aus, wenn die zu suchenden Daten sortiert vorliegen?

Accepted Answer

Binäre Suche

Answer

Sequentielle Suche

Answer

Hash-Suche

Answer

Interpolationssuche

Question 33

Welches Verfahren wird angewandt, um die Zeitkomplexität eines Algorithmus durch Experimente zu ermitteln?

Accepted Answer

Empirische Analyse

Answer

Amortisierte Analyse

Answer

Theoretische Analyse

Answer

Asymptotische Analyse

Question 34

Wie lautet die rekursive Definition der Fibonacci-Folge?

Accepted Answer

F(n) = 0, wenn n = 0, F(n) = 1, wenn n = 1, sonst F(n) = F(n-1) + F(n-2)

Answer

F(n) = 1, wenn n = 0, F(n) = n, wenn n = 1, sonst F(n) = F(n-1) + F(n-2)

Answer

F(n) = 0, wenn n = 0, F(n) = 1, wenn n = 1, sonst F(n) = F(n-1) + n

Answer

F(n) = 1, wenn n = 0, F(n) = n, wenn n = 1, sonst F(n) = F(n-1) + n

Question 35

Welches Prinzip besagt, dass ein Algorithmus bei jeder Entscheidung die aktuell beste Option wählt, ohne zukünftige Auswirkungen zu berücksichtigen?

Accepted Answer

Prinzip der Gier

Answer

Prinzip der Optimalität

Answer

Prinzip der Dynamischen Programmierung

Answer

Prinzip des Zurückverfolgens

Question 36

Welcher der folgenden Sortieralgorithmen hat eine Zeitkomplexität von O(n^2) im ungünstigsten Fall?

Accepted Answer

Bubble Sort

Answer

Merge Sort

Answer

Quick Sort

Answer

Heapsort

Question 37

Welche Rekursionsregel wird in der folgenden Funktion verwendet: `def faktorial(n): if n == 0: return 1 else: return n * faktorial(n-1)`?

Accepted Answer

Lineare Rekursion

Answer

Baumrekursion

Answer

Tail Rekursion

Answer

Beharrliche Rekursion

Question 38

Welcher der folgenden Suchalgorithmen verwendet das Prinzip des Teilens und Herrschens?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Interpolationsuche

Answer

Jump Search

Question 39

Welche Laufzeitkomplexität hat die folgende Funktion: `def summe(n): sum = 0 for i in range(1, n+1): sum += i return sum`?

Accepted Answer

O(n)

Answer

O(log(n))

Answer

O(n^2)

Answer

O(n^3)

Question 40

Was versteht man unter der Big-O-Notation?

Accepted Answer

Eine obere Schranke für die schlechtestmögliche Laufzeit eines Algorithmus

Answer

Eine genaue Vorhersage der Laufzeit eines Algorithmus

Answer

Eine untere Schranke für die bestmögliche Laufzeit eines Algorithmus

Answer

Eine Methode zur Bestimmung des Speicherbedarfs eines Algorithmus

Question 41

Welcher der folgenden Algorithmen ist nicht deterministisch?

Accepted Answer

Randomisierter Quick Sort

Answer

Dijkstra-Algorithmus

Answer

Prims-Algorithmus

Answer

Floyd-Warshall-Algorithmus

Question 42

Was ist der Unterschied zwischen einem Algorithmus und einem Programm?

Accepted Answer

Ein Algorithmus ist eine abstrakte Beschreibung eines Prozesses, während ein Programm eine konkrete Implementierung des Algorithmus ist

Answer

Ein Programm ist eine abstrakte Beschreibung eines Prozesses, während ein Algorithmus eine konkrete Implementierung des Programms ist

Answer

Es gibt keinen Unterschied zwischen einem Algorithmus und einem Programm

Answer

Ein Algorithmus ist eine mathematische Formel, während ein Programm eine Folge von Anweisungen ist

Question 43

Welche der folgenden Aussagen über rekursive Algorithmen ist korrekt?

Accepted Answer

Sie lösen ein Problem, indem sie es in kleinere Instanzen desselben Problems zerlegen

Answer

Sie benötigen immer einen Stapel, um aufzurufen

Answer

Sie sind immer effizienter als iterative Algorithmen

Answer

Keine der oben genannten

Question 44

Welcher Suchalgorithmus hat eine durchschnittliche Laufzeit von O(log n), wenn die Liste sortiert ist?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Bubble Sort

Answer

Insertion Sort

Question 45

Welcher in-place arbeitende Sortieralgorithmus besitzt eine Laufzeitkomplexität von O(n²)?

Accepted Answer

Bubblesort

Answer

Heapsort

Answer

Quicksort

Answer

Mergesort

Question 46

Welcher Suchalgorithmus ist effizient für geordnete Daten und besitzt eine Laufzeitkomplexität von O(log n)?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Hashtabelle

Answer

Baumsuche

Question 47

Was ist der Fall, in dem eine rekursive Funktion abbricht?

Accepted Answer

Basisfall

Answer

Rekursiver Fall

Answer

Rückgabefall

Answer

Parameterübergabefall

Question 48

Welche Laufzeitkomplexität hat ein Algorithmus, der n² Operationen ausführt?

Accepted Answer

O(n²)

Answer

O(n)

Answer

O(n log n)

Answer

O(log n)

Question 49

Welche Datenstruktur ermöglicht die effiziente Speicherung von Schlüssel-Wert-Paaren?

Accepted Answer

Hashtabelle

Answer

Array

Answer

Liste

Answer

Baum

Question 50

Welches Sortierverfahren verwendet einen Pivot-Wert, um eine Liste zu partitionieren?

Accepted Answer

Quicksort

Answer

Bubblesort

Answer

Heapsort

Answer

Mergesort

Question 51

Was ist der wesentliche Unterschied zwischen einem Algorithmus und einem Programm?

Accepted Answer

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

Answer

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

Answer

Algorithmen und Programme sind identisch.

Answer

Ein Algorithmus ist immer effizienter als ein Programm.

Question 52

Welche Aussage zur Big-O-Notation ist korrekt?

Accepted Answer

Sie gibt die maximale Laufzeit eines Algorithmus an.

Answer

Sie gibt die minimale Laufzeit eines Algorithmus an.

Answer

Sie gibt die durchschnittliche Laufzeit eines Algorithmus an.

Answer

Sie gibt die Laufzeit eines Algorithmus im besten Fall an.

Question 53

Welcher Algorithmus kann zur Ermittlung eines minimalen Spannbaums in einem Graphen eingesetzt werden?

Accepted Answer

Kruskal-Algorithmus

Answer

Dijkstra-Algorithmus

Answer

Bellman-Ford-Algorithmus

Answer

Floyd-Warshall-Algorithmus

Question 54

Welcher Vorteil ergibt sich aus der Verwendung einer rekursiven Funktion?

Accepted Answer

Aufteilung komplexer Probleme in kleinere Teilprobleme

Answer

Verringerung des Speicherbedarfs

Answer

Verbesserung der Lesbarkeit des Codes

Answer

Beschleunigung der Programmausführung

Question 55

Was ist die Laufzeitkomplexität der linearen Suche, wenn sie in einer Liste mit n Elementen durchgeführt wird?

Accepted Answer

O(n)

Answer

O(n^2)

Answer

O(1)

Answer

O(log n)

Question 56

Welche Rekursionsmethode wird verwendet, um die Summe aller Elemente einer Liste zu berechnen?

Accepted Answer

Tail-Rekursion

Answer

Gegenseitige Rekursion

Answer

Head-Rekursion

Answer

Indirekte Rekursion

Question 57

Welche Datenstruktur wird verwendet, um einen binären Suchbaum zu implementieren?

Accepted Answer

Knoten

Answer

Array

Answer

Liste

Answer

Warteschlange

Question 58

Welcher Algorithmus wird verwendet, um festzustellen, ob ein Graph einen Kreis enthält?

Accepted Answer

Tiefen- oder Breitensuche

Answer

Floyd-Warshall-Algorithmus

Answer

Dijkstra-Algorithmus

Answer

Prims-Algorithmus

Question 59

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

Accepted Answer

O(n log n)

Answer

O(n^2)

Answer

O(n)

Question 60

Welcher Algorithmus wird verwendet, um den kürzesten Weg in einem gewichteten Graphen zu finden?

Accepted Answer

Dijkstra-Algorithmus

Answer

Floyd-Warshall-Algorithmus

Answer

Tiefen- oder Breitensuche

Answer

Prims-Algorithmus

Question 61

Welche Laufzeitkomplexität hat der Heapsort-Algorithmus?

Accepted Answer

O(n log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(1)

Question 62

Welcher Sortieralgorithmus hat im schlimmsten Fall eine Zeitkomplexität von O(n^2)?

Accepted Answer

Bubblesort

Answer

Heapsort

Answer

Mergesort

Answer

Quicksort

Question 63

Welches Suchverfahren ist besonders gut geeignet, um ein Element in einem sortierten Array zu finden?

Accepted Answer

Binäre Suche

Answer

Hashing

Answer

Lineare Suche

Answer

Trie-Suche

Question 64

Wie viele rekursive Aufrufe beinhaltet eine Funktion, die sich selbst dreimal rekursiv aufruft?

Accepted Answer

3

Answer

4

Answer

2

Answer

1