Algorithmen lernen: Such-, Sortier- und rekursive Algorithmen verstehen

Question 1

Welcher Schritt ist NICHT Bestandteil des Merge-Sort-Algorithmus?

Accepted Answer

Vergleichen der ersten Elemente der beiden Hälften

Answer

Aufteilen des Arrays in zwei Hälften

Answer

Sortieren der beiden Hälften

Answer

Zusammenführen der sortierten Hälften in das ursprüngliche Array

Question 2

Welche Datenstruktur ist die Grundlage der Binärsuche?

Accepted Answer

Sortiertes Array

Answer

Liste

Answer

Baum

Answer

Graph

Question 3

Was bezeichnet den Fall, in dem ein rekursiver Algorithmus beendet wird?

Accepted Answer

Basisfall

Answer

Rekursiver Fall

Answer

Abbruchbedingung

Answer

Endlosschleife

Question 4

Welche Laufzeitkomplexität besitzt der Heapsort-Algorithmus?

Accepted Answer

O(n log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(log n)

Question 5

Welcher Sortieralgorithmus ist in-place und stabil?

Accepted Answer

Insertionsort

Answer

Quicksort

Answer

Bubblesort

Answer

Heapsort

Question 6

Was ist der Unterschied zwischen deterministischen und nichtdeterministischen Algorithmen?

Accepted Answer

Deterministische Algorithmen liefern immer die gleiche Ausgabe, während nichtdeterministische Algorithmen unterschiedliche Ausgaben liefern können

Answer

Nichtdeterministische Algorithmen sind immer effizienter als deterministische Algorithmen

Answer

Deterministische Algorithmen verwenden immer Schleifen, während nichtdeterministische Algorithmen immer Rekursion verwenden

Answer

Es gibt keinen Unterschied zwischen deterministischen und nichtdeterministischen Algorithmen

Question 7

Welche Aussage beschreibt die Bedeutung der Komplexitätsklasse P korrekt?

Accepted Answer

P umfasst Probleme, die mit einem deterministischen Algorithmus in polynomieller Zeit gelöst werden können

Answer

P umfasst Probleme, die mit einem nichtdeterministischen Algorithmus in polynomieller Zeit gelöst werden können

Answer

P umfasst Probleme, die in exponentieller Zeit gelöst werden können

Answer

P umfasst Probleme, die nicht gelöst werden können

Question 8

Welche Technik verbessert die Laufzeit eines rekursiven Algorithmus?

Accepted Answer

Memoisierung

Answer

Schleifeninvarianten

Answer

Quicksort-Partitionierung

Answer

Dynamische Programmierung

Question 9

Welcher Suchalgorithmus weist eine Zeitkomplexität von O(log n) auf?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Tiefensuche

Answer

Breitensuche

Question 10

Welche Aussage zur Zeitkomplexität des Bubblesort-Algorithmus ist zutreffend?

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(log n)

Answer

O(n log n)

Question 11

Welche rekursive Funktion berechnet die Fibonacci-Folge?

Accepted Answer

int fibonacci(int n) { if (n <= 0) return 0; else if (n == 1) return 1; else return fibonacci(n - 1) + fibonacci(n - 2); }

Answer

int fibonacci(int n) { if (n <= 0) return 1; else if (n == 1) return 1; else return fibonacci(n - 1) + fibonacci(n - 2); }

Answer

int fibonacci(int n) { if (n <= 0) return 0; else if (n == 1) return 1; else return fibonacci(n - 2) + fibonacci(n - 1); }

Answer

int fibonacci(int n) { return n + fibonacci(n - 1); }

Question 12

Welche Aussage über rekursive Algorithmen ist korrekt?

Accepted Answer

Sie speichern Zwischenresultate im Stack.

Answer

Sie sind immer effizienter als iterative Algorithmen.

Answer

Sie sind einfacher zu implementieren als iterative Algorithmen.

Answer

Sie können nicht für Probleme verwendet werden, die eine große Anzahl von Rekursionsebenen erfordern.

Question 13

Welcher Algorithmus durchläuft einen Graphen in die Tiefe?

Accepted Answer

Tiefensuche

Answer

Breitensuche

Answer

Dijkstra

Answer

Floyd-Warshall

Question 14

Welche Art von Rekursion liegt vor, wenn eine Funktion sich unmittelbar selbst aufruft?

Accepted Answer

Direkte Rekursion

Answer

Indirekte Rekursion

Answer

Iterative Rekursion

Answer

Tail-Rekursion

Question 15

Welche Bedingung bildet die Grundlage des euklidischen Algorithmus zur Berechnung des größten gemeinsamen Teilers (ggT)?

Accepted Answer

Wenn der zweite Parameter 0 ist

Answer

Wenn der erste Parameter größer als der zweite ist

Answer

Wenn beide Parameter gleich sind

Answer

Wenn der erste Parameter 1 ist

Question 16

Welche Komplexitätsklasse umfasst Algorithmen mit einer polynomiellen Laufzeit?

Accepted Answer

P

Answer

NP

Answer

NP-vollständig

Answer

NP-schwer

Question 17

Welche Datenstruktur ist für die Speicherung von Daten mit eindeutigen Schlüsseln und schnellem Zugriff am besten geeignet?

Accepted Answer

Hash-Tabelle

Answer

Liste

Answer

Stapel

Answer

Warteschlange

Question 18

Welches Beweisverfahren eignet sich für den Nachweis der Korrektheit eines induktiven Algorithmus?

Accepted Answer

Induktion

Answer

Kontraposition

Answer

Direkter Beweis

Answer

Indirekter Beweis

Question 19

Welche Laufzeitkomplexität besitzt ein Algorithmus, der eine Liste mit n Elementen durchläuft und für jedes Element eine konstante Operation ausführt?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(n²)

Answer

O(log n)

Question 20

Welcher der folgenden Algorithmen ist rekursiv und hat eine Laufzeitkomplexität von O(n!)?

Accepted Answer

Fakultätsberechnung

Answer

Lineare Suche

Answer

Quicksort

Question 21

Welcher Suchalgorithmus ist für die Suche in einem sortierten Array am effizientesten?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Quicksort

Question 22

Welcher Suchalgorithmus ist für sortierte Listen am effizientesten?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Rekursive Suche

Answer

Depth-First-Suche

Question 23

Welcher Sortieralgorithmus behält die ursprüngliche Reihenfolge gleicher Elemente?

Accepted Answer

Mergesort

Answer

Bubblesort

Answer

Quicksort

Answer

Heapsort

Question 24

Wie unterscheidet sich ein Programm von einem Algorithmus?

Accepted Answer

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

Answer

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

Answer

Es gibt keinen Unterschied zwischen einem Algorithmus und einem Programm.

Answer

Ein Algorithmus kann in mehrere Programme umgesetzt werden, aber ein Programm kann nur einen Algorithmus umsetzen.

Question 25

Welche asymptotische Zeitkomplexität hat ein Algorithmus, der das größte Element in einem Array findet?

Accepted Answer

O(n)

Answer

O(n^2)

Answer

O(log n)

Answer

O(1)

Question 26

Welche Aussage trifft auf den Sortieralgorithmus Merge Sort zu?

Accepted Answer

Er ist stabil und hat eine Zeitkomplexität von O(n log n).

Answer

Er ist nicht stabil und hat eine Zeitkomplexität von O(n²).

Answer

Er ist stabil und hat eine Zeitkomplexität von O(n²).

Question 27

Welche Aussage trifft auf die Zeitkomplexität des Algorithmus zur Berechnung der Fibonacci-Folge zu?

Accepted Answer

Sie ist exponentiell.

Answer

Sie ist linear.

Answer

Sie ist konstant.

Answer

Sie ist logarithmisch.

Question 28

Welcher der folgenden Algorithmen ist ein probabilistischer Algorithmus?

Accepted Answer

Randomisierter Quicksort

Answer

Heapsort

Answer

Insertionsort

Answer

Deterministischer Quicksort

Question 29

Welcher Algorithmus berechnet das kleinste gemeinsame Vielfache (ggT) zweier Zahlen?

Accepted Answer

Euklidischer Algorithmus

Answer

Primzahlsieb

Answer

Binomialkoeffizient

Question 30

Welcher Suchalgorithmus prüft alle möglichen Kombinationen?

Accepted Answer

Exhaustive Search

Answer

Binäre Suche

Answer

Interpolationssuche

Answer

Hash-Suche

Question 31

Welcher Sortieralgorithmus ist stabil und hat eine Laufzeitkomplexität von O(n log n)?

Accepted Answer

Mergesort

Answer

Heapsort

Answer

Quicksort

Answer

Bubblesort

Question 32

Welche Bedingung beendet die rekursive Fakultätsfunktion?

Accepted Answer

n = 0

Answer

n > 0

Answer

n < 0

Answer

n = 1

Question 33

Was unterscheidet einen Algorithmus von einem Programm?

Accepted Answer

Ein Algorithmus ist eine abstrakte Methode, ein Programm eine konkrete Implementierung

Answer

Ein Algorithmus ist komplexer als ein Programm

Question 34

Welche Eigenschaft beschreibt die Unabhängigkeit von Algorithmen von der Programmiersprache?

Accepted Answer

Sprachenunabhängigkeit

Answer

Geräteunabhängigkeit

Answer

Betriebssystemunabhängigkeit

Answer

Plattformunabhängigkeit

Question 35

Welcher Algorithmus verwendet die Divide-and-Conquer-Strategie?

Accepted Answer

Quicksort

Answer

Insertionsort

Answer

Selectionsort

Answer

Bubblesort

Question 36

Welche Eigenschaft ist ein Hauptvorteil der Verwendung rekursiver Algorithmen?

Accepted Answer

Zerlegung komplexer Probleme in kleinere, lösbarere Unterprobleme

Answer

Verbesserte Lesbarkeit des Codes

Answer

Erhöhte Effizienz durch parallele Verarbeitung

Answer

Geringerer Speicherbedarf für große Datensätze

Question 37

Welche Aussage über die Determiniertheit von Algorithmen ist korrekt?

Accepted Answer

Algorithmen können sowohl deterministisch als auch nicht-deterministisch sein, abhängig von den Eingabedaten.

Answer

Alle Algorithmen sind deterministisch, da sie präzise Anweisungen befolgen.

Answer

Alle Algorithmen sind nicht-deterministisch, da sie auf Zufallswerten basieren.

Question 38

Welcher Algorithmus ist am besten geeignet, um ein bestimmtes Element in einer unsortierten Liste zu finden?

Accepted Answer

Lineare Suche

Answer

Bubblesort

Answer

Mergesort

Answer

Binäre Suche

Question 39

Welcher Sortieralgorithmus teilt das Array wiederholt in zwei Hälften, sortiert diese und fügt sie dann wieder zusammen?

Accepted Answer

Mergesort

Answer

Quicksort

Answer

Bubblesort

Answer

Heapsort

Question 40

Welche Technik löst ein Problem, indem sie es in kleinere Teilprobleme zerlegt und diese rekursiv löst?

Accepted Answer

Rekursion

Answer

Iteration

Answer

Dynamische Programmierung

Question 41

Welche Laufzeitkomplexität hat der Bubblesort-Algorithmus im ungünstigsten Fall?

Accepted Answer

O(n²)

Answer

O(n log n)

Answer

O(n)

Answer

O(log n)

Question 42

Welche Datenstruktur eignet sich am besten zur Implementierung eines Stacks, einer Datenstruktur, die das Last-in-First-out-Prinzip (LIFO) verwendet?

Accepted Answer

Liste

Answer

Graph

Answer

Baum

Answer

Menge

Question 43

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

Accepted Answer

Ein Algorithmus ist eine abstrakte Beschreibung der Problemlösung, während ein Programm eine konkrete Implementierung ist, die auf einem bestimmten Computersystem ausgeführt werden kann.

Answer

Ein Algorithmus ist immer deterministisch, während ein Programm nicht-deterministisch sein kann.

Answer

Ein Algorithmus muss immer in endlicher Zeit beendet werden, während ein Programm nicht beendet werden muss.

Question 44

Welcher Suchalgorithmus ist am effizientesten zum Auffinden eines Elements in einem sortierten Array?

Accepted Answer

Binäre Suche

Answer

Interpolationssuche

Answer

Hashtabelle

Answer

Lineare Suche

Question 45

Was ist der Zweck der asymptotischen Notation in der Analyse von Algorithmen?

Accepted Answer

Beschreibung des Verhaltens der Laufzeit oder des Speicherbedarfs eines Algorithmus für große Eingaben

Answer

Beschreibung der Parallelität eines Algorithmus

Answer

Analyse der Genauigkeit eines Algorithmus

Question 46

Welcher Sortieralgorithmus ist für große Datenmengen am effizientesten?

Accepted Answer

Quicksort

Answer

Bubblesort

Answer

Insertionsort

Question 47

Welcher Unterschied besteht zwischen deterministischen und nicht-deterministischen Algorithmen?

Accepted Answer

Ein deterministischer Algorithmus liefert für dieselbe Eingabe immer das gleiche Ergebnis, während ein nicht-deterministischer Algorithmus mehrere gültige Ergebnisse liefern kann.

Answer

Ein deterministischer Algorithmus ist immer schneller als ein nicht-deterministischer Algorithmus.

Question 48

Welcher Suchalgorithmus ist optimal für sortierte Listen?

Accepted Answer

Binäre Suche

Answer

Interpolationssuche

Answer

Lineare Suche

Question 49

Welche Laufzeitkomplexität hat der Sortieralgorithmus, der für fast sortierte Listen am effizientesten ist?

Accepted Answer

Insertionsort

Answer

Quicksort

Answer

Bubblesort

Question 50

Was ist das grundlegende Prinzip rekursiver Algorithmen?

Accepted Answer

Zerlegung eines Problems in kleinere Instanzen desselben Problems

Answer

Verwendung von Schleifen zur Iteration durch Daten

Answer

Verwendung von bedingten Anweisungen zur Steuerung des Programmflusses

Question 51

Welches ist ein Beispiel für einen rekursiven Algorithmus?

Accepted Answer

Berechnung der Fakultät

Answer

Bubblesort

Answer

Binäre Suche

Answer

Lineare Suche

Question 52

Welche Notation wird verwendet, um die obere Schranke der worst-case-Laufzeit eines Algorithmus anzugeben?

Accepted Answer

O-Notation

Answer

σ-Notation

Answer

Ω-Notation

Answer

Θ-Notation

Question 53

Das Traveling Salesman Problem (TSP) ist ein klassisches Beispiel für welche Art von Problem?

Accepted Answer

Kombinatorisches Optimierungsproblem

Answer

Sortieralgorithmus

Answer

Rekursives Problem

Answer

Suchproblem

Question 54

Welcher Suchalgorithmus ist am effizientesten, um ein bestimmtes Element in einem sortierten Array zu finden?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Jump Search

Answer

Hashing

Question 55

Die Laufzeit von Mergesort im ungünstigsten Fall wird durch welche Komplexitätsklasse beschrieben?

Accepted Answer

O(n log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(log n)

Question 56

Was ist das Kernprinzip der rekursiven Programmierung?

Accepted Answer

Ein Problem wird in kleinere, selbstähnliche Teilprobleme zerlegt, die durch die gleiche Funktion gelöst werden.

Answer

Ein Problem wird in unabhängige Teilprobleme zerlegt, die parallel gelöst werden.

Answer

Ein Problem wird durch die Verwendung globaler Variablen gelöst.

Answer

Ein Problem wird durch Schleifenkonstrukte gelöst, ohne Funktionen aufzurufen.

Question 57

Welcher der folgenden Algorithmen ist ein Beispiel für einen Greedy-Algorithmus?

Accepted Answer

Dijkstra-Algorithmus

Answer

Binäre Suche

Answer

Quicksort

Answer

Mergesort

Question 58

Wie berechnet ein rekursiver Algorithmus die Fakultät einer Zahl n?

Accepted Answer

Er berechnet die Fakultät von (n-1) rekursiv und multipliziert das Ergebnis mit n.

Answer

Er multipliziert die Zahlen von 1 bis n in einer Schleife.

Answer

Er verwendet eine vordefinierte Bibliothekfunktion zur Berechnung der Fakultät.

Answer

Er addiert die Fakultät von (n-1) zu n.

Question 59

Was beschreibt die Zeitkomplexität eines Algorithmus?

Accepted Answer

Die Anzahl der benötigten Operationen in Abhängigkeit von der Eingabegröße.

Answer

Den benötigten Speicherplatz in Abhängigkeit von der Eingabegröße.

Answer

Die Laufzeit des Algorithmus auf einer spezifischen Hardware.

Answer

Die Anzahl der Zeilen Code des Algorithmus.

Question 60

Welcher der folgenden Sortieralgorithmen hat im Durchschnitt die beste Laufzeit?

Accepted Answer

Quicksort

Answer

Insertionsort

Answer

Bubblesort

Answer

Mergesort

Question 61

Was ist die Grundidee des Divide-and-Conquer-Prinzips?

Accepted Answer

Ein Problem in kleinere Teilprobleme zerlegen, diese rekursiv lösen und die Teillösungen kombinieren.

Answer

Ein Problem durch Brute-Force zu lösen, indem alle Möglichkeiten durchprobiert werden.

Answer

Ein Problem durch Iteration zu lösen, bis eine Bedingung erfüllt ist.

Answer

Ein Problem durch Backtracking zu lösen, indem schrittweise Lösungen aufgebaut und bei Fehlern Schritte zurückgenommen werden.