Algorithmen lernen: Quizze und Übungen für Informatik-Studenten

Question 1

Wie lautet die Zeitkomplexität des Sortieralgorithmus 'Quicksort' im besten Fall?

Accepted Answer

O(n)

Answer

O(n log n)

Answer

O(n^2)

Answer

O(2^n)

Question 2

Welche der folgenden Aussagen zur rekursiven Implementierung von Algorithmen ist korrekt?

Accepted Answer

Rekursion ist eine Technik, bei der ein Algorithmus sich selbst aufruft.

Answer

Rekursion kann nur bei Algorithmen eingesetzt werden, die auf Division beruhen.

Answer

Die rekursive Implementierung eines Algorithmus führt immer zu einer effizienteren Lösung.

Answer

Rekursive Algorithmen benötigen keinen Stack, um Daten zu speichern.

Question 3

Welcher der folgenden Algorithmen eignet sich am besten zum Suchen eines bestimmten Elements in einer großen, unsortierten Liste?

Accepted Answer

Sequentielle Suche

Answer

Binäre Suche

Answer

Heapsort

Answer

Quicksort

Question 4

Was ist ein Vorteil der Verwendung von Heaps bei der Implementierung von Sortieralgorithmen?

Accepted Answer

Heaps können verwendet werden, um sowohl aufsteigend als auch absteigend sortierte Listen zu erzeugen.

Answer

Heaps ermöglichen eine effizientere Suche als binäre Suchbäume.

Answer

Heaps benötigen weniger Speicherplatz als Arrays.

Answer

Heaps sind immer stabiler als andere Sortieralgorithmen.

Question 5

welcher Suchalgorithmus teilt eine sortierte Folge wiederholt in zwei Hälften und hat eine Komplexität von O(log n)?

Accepted Answer

Binäre Suche

Answer

Sequentielle Suche

Answer

Interpolationssuche

Answer

Hash-Suche

Question 6

Welches Verfahren ruft sich selbst in seiner Implementierung auf und löst ein Problem durch Zerlegung in kleinere Teilprobleme?

Accepted Answer

Rekursion

Answer

Iteration

Answer

Schleife

Answer

bedingte Anweisung

Question 7

Welche Methode der Algorithmenanalyse gibt an, wie sich die Laufzeit eines Algorithmus mit zunehmender Eingabegröße im ungünstigsten Fall verhält?

Accepted Answer

Worst-Case-Analyse

Answer

Best-Case-Analyse

Answer

Durchschnittsfallanalyse

Answer

Amortisierte Analyse

Question 8

Welche Komplexitätsklasse umfasst Algorithmen, die in einer Laufzeit gelöst werden können, die durch ein Polynom in der Eingabegröße begrenzt ist?

Accepted Answer

P

Answer

NP

Answer

NP-vollständig

Answer

NP-schwer

Question 9

Welcher Algorithmus zerlegt eine Eingabe in kleinere Teilprobleme, löst diese rekursiv und kombiniert die Lösungen zu einer Gesamtlösung?

Accepted Answer

Divide-and-conquer

Answer

Greedy

Answer

Dynamische Programmierung

Answer

Backtracking

Question 10

Welches Programmierparadigma betont die Verwendung unveränderlicher Variablen und Funktionen, die keine Nebenwirkungen haben?

Accepted Answer

Funktionalen Programmieren

Answer

Imperatives Programmieren

Answer

Objektorientiertes Programmieren

Answer

Logisches Programmieren

Question 11

Welche Algorithmusoptimierungstechnik speichert bereits berechnete Ergebnisse, um die Laufzeit zu verbessern?

Accepted Answer

Memoization

Answer

Tail-call-Optimierung

Answer

Inline-Expansion

Answer

Schleifenentfaltung

Question 12

Welcher Algorithmentyp garantiert eine Lösung, die nachweislich optimal für ein gegebenes Problem ist?

Accepted Answer

Exakter Algorithmus

Answer

Approximationsalgorithmus

Answer

Heuristischer Algorithmus

Answer

Probabilistischer Algorithmus

Question 13

Welcher Suchalgorithmus ist am effizientesten bei der Suche nach einem Element in einer sortierten Liste mit n Elementen?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Quicksort

Question 14

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

Accepted Answer

Merge Sort

Answer

Bubble Sort

Answer

Insertion Sort

Answer

Selection Sort

Question 15

Nenne einen wesentlichen Unterschied zwischen deterministischen und nicht-deterministischen Algorithmen.

Accepted Answer

Deterministische Algorithmen liefern bei gleichen Eingaben immer dasselbe Ergebnis.

Answer

Nicht-deterministische Algorithmen benötigen weniger Zeit.

Answer

Deterministische Algorithmen sind immer effizienter.

Answer

Nicht-deterministische Algorithmen sind einfacher zu implementieren.

Question 16

Discuss the advantages and disadvantages of recursive algorithm implementations compared to iterative implementations, particularly in the context of self-similar problems.

Accepted Answer

Recursive implementations are ideally suited for problems exhibiting self-similarity.

Answer

Recursive implementations are inherently easier to comprehend.

Answer

Recursive implementations excel in efficiency.

Answer

Iterative implementations are universally superior to recursive implementations.

Question 17

Welcher Sortieralgorithmus weist eine Zeitkomplexität von O(n^2) auf?

Accepted Answer

Bubblesort

Answer

Quicksort

Answer

Heapsort

Answer

Mergesort

Question 18

Was bedeutet die Verkettung zweier Algorithmen?

Accepted Answer

Die Ausführung zweier Algorithmen nacheinander

Answer

Die gleichzeitige Ausführung zweier Algorithmen

Answer

Die Ausführung zweier Algorithmen unterbrechungsbasiert

Answer

Die parallele Ausführung zweier Algorithmen

Question 19

Welches Suchverfahren ist für sortierte Daten am effizientesten?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Interpolationssuche

Answer

Hashtabelle

Question 20

Welcher der folgenden Algorithmen verwendet die Strategie "Teile und Herrsche"?

Accepted Answer

Quicksort

Answer

Heapsort

Answer

Bubblesort

Answer

Insertionsort

Question 21

Was ist der Zweck einer Vorbedingung in einem Algorithmus?

Accepted Answer

Überprüfung der Gültigkeit der Eingaben für den Algorithmus

Answer

Gewährleistung der Beendigung des Algorithmus

Answer

Verbesserung der Lesbarkeit des Algorithmus

Answer

Verringerung der Laufzeit des Algorithmus

Question 22

Welche Aussage zur Komplexitätsklasse NP-vollständig ist korrekt?

Accepted Answer

NP-vollständig impliziert, dass es keine effizienten Algorithmen für Probleme dieser Klasse gibt

Answer

NP-vollständige Probleme können effizient gelöst werden, wenn eine bestimmte Teilmenge der Eingabe bekannt ist

Answer

Alle NP-vollständigen Probleme haben eine polynomielle Zeitkomplexität

Answer

NP-Vollständigkeit ist ein Maß für die Schwierigkeit eines Algorithmus

Question 23

Welcher Suchalgorithmus ist am effizientesten, um ein Element in einem sortierten Array zu finden? Beschreibe seinen Ablauf.

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Interpolationssuche

Answer

Hashing-Algorithmus

Question 24

Welche Laufzeitkomplexität hat der Algorithmus, der eine sortierte Liste von n Elementen durchläuft und für jedes Element eine Operation ausführt?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(n^2)

Answer

O(log n)

Question 25

Welcher Algorithmus ist ein rekursiver Algorithmus?

Accepted Answer

Fakultätsberechnung

Answer

Primfaktorzerlegung

Answer

Quicksort

Answer

Merge

Question 26

Welcher Suchalgorithmus ist effizient für große, sortierte Datenmengen?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Interpolationssuche

Answer

Hashing

Question 27

Was ist der Zweck einer Hash-Funktion?

Accepted Answer

Einen großen Schlüsselraum in einen kleineren Wertebereich abzubilden

Answer

Schlüsselwerte zu sortieren

Answer

Daten zu verschlüsseln

Answer

Daten zu komprimieren

Question 28

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

Accepted Answer

O(n)

Answer

O(1)

Answer

O(n^2)

Answer

O(log n)

Question 29

Welcher Datentyp ist für die Implementierung eines Stacks geeignet?

Accepted Answer

Linked List

Answer

Array

Answer

Queue

Answer

Hash Table

Question 30

Was ist das Ziel der Algorithmusanalyse?

Accepted Answer

Die Effizienz eines Algorithmus vorhersagen

Answer

Die Korrektheit eines Algorithmus beweisen

Answer

Die Implementierung eines Algorithmus zu optimieren

Answer

Die Komplexität eines Algorithmus zu reduzieren

Question 31

Welcher der aufgeführten Algorithmen ist ein rekursiver Algorithmus?

Accepted Answer

Factorial

Answer

Bubblesort

Answer

Quicksort

Answer

Binary search

Question 32

Welche Komplexitätsklasse hat der Algorithmus für die binäre Suche in einem sortierten Array?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(2^n)

Question 33

Welche Strategie verwendet der Bubblesort-Algorithmus, um ein Array zu sortieren?

Accepted Answer

Vergleicht benachbarte Elemente und tauscht sie bei Bedarf

Answer

Teilt das Array in zwei Hälften und sortiert diese rekursiv

Answer

Sucht das kleinste Element im unsortierten Teil und verschiebt es an den Anfang

Answer

Verwendet ein Pivotelement, um das Array in zwei Partitionen zu teilen

Question 34

Welche Datenstruktur wird im Depth-First-Search (DFS)-Algorithmus verwendet?

Accepted Answer

Stack

Answer

Queue

Answer

Tree

Answer

Hash table

Question 35

Was ist das Ziel der Algorithmenanalyse?

Accepted Answer

Die Effizienz eines Algorithmus bestimmen

Answer

Die Korrektheit eines Algorithmus beweisen

Answer

Die Implementierung eines Algorithmus optimieren

Answer

Die Komplexität eines Algorithmus reduzieren

Question 36

Welcher Suchalgorithmus hat die beste Worst-Case-Komplexität für eine sortierte Liste?

Accepted Answer

Binäre Suche

Answer

Hashtabellensuche

Answer

Interpolationssuche

Answer

Lineare Suche

Question 37

Welcher Sortieralgorithmus ist stabil?

Accepted Answer

Mergesort

Answer

Heapsort

Answer

Bubblesort

Answer

Quicksort

Question 38

Welcher Suchalgorithmus halbiert die zu durchsuchende Liste wiederholt und hat eine durchschnittliche Laufzeitkomplexität von O(log n)?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Interpolationssuche

Question 39

Welche Methode der Algorithmusanalyse liefert die maximale Laufzeit eines Algorithmus?

Accepted Answer

Worstfallanalyse

Answer

Bestfallanalyse

Answer

Durchschnittsanalyse

Question 40

Welcher Suchalgorithmus ist am effizientesten, wenn das zu suchende Element in einer unsortierten Liste zufällig verteilt ist?

Accepted Answer

Lineare Suche

Answer

Binäre Suche

Answer

Hashing

Answer

Interpolationssuche

Question 41

Welche rekursive Funktion berechnet die Fakultät einer positiven ganzen Zahl n?

Accepted Answer

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

Answer

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

Answer

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

Question 42

Welche asymptotische Komplexitätsklasse beschreibt einen Algorithmus, dessen Laufzeit durch eine Konstante beschränkt ist?

Accepted Answer

O(1)

Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Question 43

Welche Datenstruktur eignet sich für die effiziente Implementierung einer Warteschlange?

Accepted Answer

Verkettete Liste

Answer

Stack

Answer

Hashtabelle

Answer

Array

Question 44

Welcher Suchalgorithmus hat eine Worst-Case-Komplexität von O(log n)?

Accepted Answer

Binärsuche

Answer

Ternäre Suche

Answer

Interpolationssuche

Answer

Lineare Suche

Question 45

Welcher Sortieralgorithmus ist stabil und behält die ursprüngliche Reihenfolge gleicher Elemente bei?

Accepted Answer

Mergesort

Answer

Quicksort

Answer

Heapsort

Answer

Bubblesort

Question 46

Welcher Komplexitätsgrad kennzeichnet einen Algorithmus, der für große Eingaben exponentiell wächst?

Accepted Answer

O(2^n)

Answer

O(n^2)

Answer

O(n)

Answer

O(log n)

Question 47

Was ist der Zweck einer Hash-Funktion?

Accepted Answer

Zuordnung eines eindeutigen Schlüsselwerts zu einer Eingabe

Answer

Sortieren einer Liste von Elementen

Answer

Speicherung von Daten in einer linearen Struktur

Question 48

Welche Datenstruktur wird verwendet, um eine Menge eindeutiger Elemente zu speichern?

Accepted Answer

Menge

Answer

Liste

Answer

Array

Answer

Baum

Question 49

Was ist der grundlegende Unterschied zwischen deterministischen und nicht-deterministischen Algorithmen?

Accepted Answer

Deterministische Algorithmen produzieren für jede Eingabe immer dasselbe Ergebnis, während nicht-deterministische Algorithmen mehrere mögliche Ergebnisse erzeugen können.

Answer

Deterministische Algorithmen sind immer effizienter als nicht-deterministische Algorithmen.

Question 50

Welcher Suchalgorithmus durchläuft die Elemente einer Datenstruktur von hinten nach vorne?

Accepted Answer

Reverse-lineare Suche

Answer

Lineare Suche

Answer

Binäre Suche

Answer

Interpolationssuche

Question 51

Welche Sortiermethode unterteilt die zu sortierende Datenstruktur rekursiv in zwei Teillisten?

Accepted Answer

Quicksort

Answer

Bubblesort

Answer

Selectionsort

Answer

Insertionsort

Question 52

Welche Datenstruktur ist optimal für das Hinzufügen und Löschen von Elementen in konstanter Zeit geeignet?

Accepted Answer

Hashtabelle

Answer

Liste

Answer

Stack

Answer

Warteschlange

Question 53

Welche Voraussetzung muss für die Anwendung des Prinzips der dynamischen Programmierung erfüllt sein?

Accepted Answer

Die optimale Lösung für Teilprobleme kann zur Lösung des Gesamtproblems herangezogen werden.

Answer

Das Problem muss rekursiv sein.

Answer

Das Problem muss in konstanter Zeit lösbar sein.

Question 54

Welche Eigenschaft zeichnet gierige Algorithmen aus?

Accepted Answer

Sie treffen bei jedem Schritt die lokal beste Entscheidung.

Answer

Sie sind immer rekursiv.

Answer

Sie garantieren immer die global optimale Lösung.

Question 55

Unterscheiden Sie zwischen einem Algorithmus und einem Programm.

Accepted Answer

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

Answer

Ein Algorithmus ist immer effizienter als ein Programm.

Question 56

Wie wird die Effizienz eines Algorithmus gemessen?

Accepted Answer

Zeitkomplexität und Speicherkomplexität

Answer

Nur durch die Anzahl der verwendeten Variablen

Answer

Nur durch die Anzahl der ausgeführten Operationen

Answer

Nur durch die Länge des Eingabecodes

Question 57

Welche Suchmethode teilt eine sortierte Liste wiederholt in zwei Hälften, um ein bestimmtes Element zu finden?

Accepted Answer

Binäre Suche

Answer

Tiefensuche

Answer

Lineare Suche

Answer

Breitensuche

Question 58

Welcher Sortieralgorithmus vergleicht und tauscht benachbarte Elemente in einer Liste, bis alle Elemente in der richtigen Reihenfolge sind?

Accepted Answer

Bubblesort

Answer

Mergesort

Answer

Heapsort

Answer

Quicksort

Question 59

Welche Kennzahl beschreibt die Anzahl der Operationen, die ein Algorithmus abhängig von der Größe der Eingabe benötigt?

Accepted Answer

Zeitkomplexität

Answer

Optimalität

Answer

Effizienz

Answer

Raumkomplexität

Question 60

Welche der folgenden Eigenschaften zeichnet KEINEN effizienten Algorithmus aus?

Accepted Answer

Hohe Zeitkomplexität

Answer

Niedrige Raumkomplexität

Answer

Determinismus

Answer

Korrektheit

Question 61

Welcher Sortieralgorithmus sortiert eine Liste in linearer Zeit (O(n)) und ist stabil?

Accepted Answer

Counting Sort

Answer

Heapsort

Answer

Quicksort

Answer

Mergesort

Question 62

Welcher Algorithmus ist ein nicht-deterministischer Algorithmus, dessen Ergebnis von Zufallsentscheidungen beeinflusst wird?

Accepted Answer

Zufallsalgorithmus

Answer

Bubblesort

Answer

Heapsort

Answer

Quicksort

Question 63

Welcher Suchalgorithmus verwendet eine Warteschlange, um alle Knoten eines Graphen schichtweise zu besuchen?

Accepted Answer

Breitensuche

Answer

Lineare Suche

Answer

Tiefensuche

Answer

Binäre Suche

Question 64

Welcher Sortieralgorithmus verwendet eine Prioritätswarteschlange, um die Elemente in aufsteigender Reihenfolge auszugeben?

Accepted Answer

Heapsort

Answer

Quicksort

Answer

Bubblesort

Answer

Mergesort