Algorithmen und Komplexität: Online-Quiz für die Fachoberschule

Question 1

Welche Aussagen über die Laufzeit eines Algorithmus treffen zu?

Accepted Answer

Sie ist proportional zur Anzahl der Operationen.

Accepted Answer

Sie kann sich je nach Eingabe ändern.

Answer

Sie ist unabhängig von der verwendeten Hardware.

Answer

Sie ist immer eine ganze Zahl.

Question 2

Welches der folgenden Probleme lässt sich nicht in polynomialer Zeit lösen?

Accepted Answer

Bestimmen, ob ein Graph einen Hamiltonkreis enthält

Answer

Ermitteln des kürzesten Pfades in einem gewichteten Graphen

Answer

Sortierung einer Liste von Zahlen

Answer

Suchen der größten gemeinsamen Teilmenge zweier Mengen

Question 3

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

Hamiltonkreisproblem

Accepted Answer

Rucksackproblem

Answer

Sortierproblem

Answer

Minimales Spannbaumproblem

Question 4

Welcher Algorithmus hat eine Laufzeitkomplexität von 2 hoch n?

Accepted Answer

Turm von Hanoi

Answer

Bubblesort

Answer

Binäre Suche

Answer

Quicksort

Question 5

Was bezeichnet die Anzahl der Operationen, die ein Algorithmus zur Problemlösung ausführt?

Accepted Answer

Laufzeit

Answer

Speicherbedarf

Answer

Genauigkeit

Answer

Robustheit

Question 6

Welche der folgenden Aussagen beschreibt die asymptotische Komplexität eines Algorithmus zutreffend?

Accepted Answer

Sie wird mit der O-Notation ausgedrückt.

Accepted Answer

Sie ist unabhängig von der konkreten Implementierung des Algorithmus.

Answer

Sie gibt exakt an, wie lange der Algorithmus für jede Eingabe läuft.

Answer

Sie zeigt die maximale Anzahl an Schritten, die der Algorithmus ausführen kann.

Question 7

Welche Aussage über NP-vollständige Probleme ist zutreffend?

Accepted Answer

Jedes NP-vollständige Problem kann auf jedes andere NP-vollständige Problem reduziert werden.

Answer

NP-vollständige Probleme können in polynomialer Zeit gelöst werden.

Answer

NP-vollständige Probleme sind immer leichter zu lösen als NP-schwere Probleme.

Answer

Die Komplexitätsklasse NP ist eine Teilmenge der Komplexitätsklasse P.

Question 8

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

Die kürzesten Wege zwischen allen Knoten in einem gewichteten Graphen finden

Answer

Eine Liste von Zahlen in aufsteigender Reihenfolge sortieren

Answer

Das kleinste gemeinsame Vielfache zweier Zahlen berechnen

Answer

Überprüfen, ob eine Zahl eine Primzahl ist

Question 9

Welche Aussage zur Komplexitätsanalyse von Algorithmen ist korrekt?

Accepted Answer

Die Komplexität eines Algorithmus beschreibt die maximale Anzahl an Operationen, die er für jede Eingabe einer bestimmten Größe ausführen kann.

Answer

Die Komplexität eines Algorithmus ist unabhängig von der Größe der Eingabe.

Answer

Die Komplexität eines Algorithmus kann nur durch Experimente bestimmt werden.

Answer

Die Komplexität eines Algorithmus gibt die minimale Anzahl an Operationen an, die er für jede Eingabe ausführen kann.

Question 10

Welche Aussage über die Komplexitätsklasse NP-vollständig ist richtig?

Accepted Answer

Wenn ein NP-vollständiges Problem in polynomialer Zeit gelöst werden kann, sind alle NP-Probleme in polynomialer Zeit lösbar.

Answer

NP-vollständige Probleme können in polynomialer Zeit gelöst werden.

Answer

Alle NP-Probleme sind auch NP-vollständig.

Answer

NP-vollständige Probleme müssen in exponentieller Zeit gelöst werden.

Question 11

Welches Problem kann in polynomialer Zeit auf jedes andere Problem in NP zurückgeführt werden?

Accepted Answer

Ein NP-vollständiges Problem.

Answer

Ein Problem, das in polynomialer Zeit gelöst werden kann.

Answer

Ein Problem, das nur in exponentieller Zeit gelöst werden kann.

Answer

Ein Problem, das nur in der Informatik relevant ist.

Question 12

Welches der folgenden Probleme ist NP-vollständig: Ermitteln, ob ein Graph einen Hamiltonkreis enthält?

Accepted Answer

Ermitteln, ob ein gegebener Graph einen Hamiltonkreis enthält

Answer

Bestimmen des kürzesten Weges in einem gewichteten Graphen

Answer

Überprüfen, ob eine gegebene Zahl eine Primzahl ist

Question 13

Welcher Algorithmus hat die höchste Komplexität?

Accepted Answer

O(2^n)

Answer

O(n)

Answer

O(n²)

Answer

Ω(n log n)

Question 14

Welches der folgenden Probleme lässt sich nicht in polynomialer Zeit lösen?

Accepted Answer

Travelling Salesman Problem

Answer

Dijkstra-Algorithmus

Answer

Sortierung eines Arrays

Answer

Suche des kürzesten Weges in einem Graphen

Question 15

Welche Aussage beschreibt die Komplexitätsklasse NP korrekt?

Accepted Answer

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

Answer

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

Answer

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

Question 16

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

Prüfen, ob ein Graph einen Hamilton-Kreis enthält

Accepted Answer

Prüfen, ob ein boolescher Ausdruck erfüllbar ist

Answer

Eine Liste von Zahlen aufsteigend sortieren

Answer

Den kürzesten Weg in einem gewichteten Graphen berechnen

Question 17

Welche Aussage über die Komplexitätsklasse NP ist korrekt?

Accepted Answer

NP-vollständige Probleme sind mindestens so schwierig wie jedes andere Problem in NP.

Answer

NP enthält alle Probleme, die deterministisch in polynomialer Zeit gelöst werden können.

Answer

NP ist eine Teilmenge von P.

Answer

Alle Probleme in NP können durch Brute-Force-Suche in polynomialer Zeit gelöst werden.

Question 18

Welcher Algorithmus hat die schlechteste Komplexität von O(log n)?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Sortierung durch Einfügen

Answer

Quicksort

Question 19

Welches der folgenden Probleme ist NP-vollständig: die Bestimmung, ob ein Graph einen Hamiltonkreis enthält?

Accepted Answer

Ja

Answer

Nein

Answer

Ich weiß es nicht

Question 20

Welche der folgenden Aussagen über rekursive Algorithmen ist korrekt?

Accepted Answer

Rekursive Algorithmen benötigen einen Basisfall, um zu terminieren.

Answer

Rekursive Algorithmen können nicht terminieren.

Answer

Rekursive Algorithmen sind immer effizient.

Answer

Rekursive Algorithmen können nur zum Sortieren von Daten verwendet werden.

Question 21

Welche der folgenden Aussagen über Graphen ist korrekt?

Accepted Answer

Graphen können zyklisch sein.

Answer

Graphen können nur gerichtete Kanten enthalten.

Answer

Graphen sind immer zusammenhängend.

Answer

Graphen können nur positive Gewichte für Kanten haben.

Question 22

Welches der folgenden Suchverfahren eignet sich für die Suche nach einem Element in einem binären Suchbaum, der eine sortierte Datenstruktur ist?

Accepted Answer

Binäre Suche

Answer

Lineare Suche

Answer

Tiefensuche

Answer

Breitensuche

Question 23

Welches der folgenden Probleme ist NP-vollständig: Einen Hamiltonkreis in einem Graphen finden?

Accepted Answer

Einen Hamiltonkreis in einem Graphen finden

Answer

Eine Liste von Zahlen sortieren

Answer

Die kürzesten Wege in einem Graphen berechnen

Answer

Die Primzahlen in einer Liste von Zahlen ermitteln

Question 24

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

3-SAT

Answer

Binäre Suche

Answer

Sortierung eines Arrays

Question 25

Welches der folgenden Probleme ist NP-vollständig und damit besonders schwer zu lösen?

Accepted Answer

Traveling-Salesman-Problem

Answer

Sortierung eines Arrays

Answer

Primzahltest

Answer

Berechnung des kleinsten gemeinsamen Vielfachen

Question 26

Welches der folgenden Probleme ist NP-vollständig?

Accepted Answer

Traveling-Salesman-Problem

Answer

Dijkstra-Algorithmus

Answer

Bubblesort

Answer

Quicksort

Question 27

Welcher der folgenden Algorithmen hat die höchste Komplexität?

Accepted Answer

Traveling-Salesman-Problem

Answer

Linearer Suchalgorithmus

Answer

Bubblesort-Algorithmus

Answer

Quicksort-Algorithmus

Question 28

Welche der folgenden Aussagen über Algorithmen ist **nicht** korrekt?

Accepted Answer

Algorithmen sind immer endlich.

Answer

Algorithmen haben einen eindeutigen Anfang und ein eindeutiges Ende.

Answer

Algorithmen können sowohl deterministisch als auch nicht deterministisch sein.

Answer

Algorithmen sind eine Reihe von Anweisungen, die ein Problem lösen.

Question 29

Welche der folgenden Aussagen über rekursive Algorithmen ist korrekt?

Accepted Answer

Sie können sich selbst aufrufen.

Answer

Sie sind immer effizienter als iterativ Algorithmen.

Answer

Sie erfordern keinen Stapelspeicher.

Question 30

Welcher der folgenden Algorithmen verwendet Backtracking?

Accepted Answer

N-Queens-Problem

Answer

Dijkstra-Algorithmus

Answer

Quicksort

Question 31

Welche der folgenden Techniken kann verwendet werden, um die Effizienz eines Algorithmus zu verbessern?

Accepted Answer

Memoisierung

Answer

Zurückverfolgung

Answer

Zufällige Suche

Answer

Brute Force

Question 32

Welcher der folgenden Algorithmen ist ein NP-vollständiges Problem?

Accepted Answer

SAT-Problem

Answer

Quicksort

Answer

Dijkstra-Algorithmus

Answer

Binäre Suche

Question 33

Welche der folgenden Aussage über approximative Algorithmen ist **nicht** korrekt?

Accepted Answer

Sie liefern immer genaue Lösungen.

Answer

Sie sind nicht immer deterministisch.

Answer

Sie können auch für große Probleme verwendet werden.

Answer

Sie sind nicht immer effizienter als exakte Algorithmen.

Question 34

Welches der folgenden Diagramme kann verwendet werden, um die Laufzeit eines Algorithmus grafisch darzustellen?

Accepted Answer

Laufzeitdiagramm

Answer

Datenflussdiagramm

Answer

UML-Diagramm

Answer

Flussdiagramm

Question 35

Welcher der folgenden Algorithmen ist ein effizienter Sortieralgorithmus für große Datenmengen?

Accepted Answer

Quicksort

Answer

Bubble Sort

Answer

Selection Sort

Answer

Insertion Sort

Question 36

Welche Komplexitätsnotation betrachtet die worst-case-Laufzeit eines Algorithmus?

Accepted Answer

O-Notation

Answer

f(n)

Answer

Θ-Notation

Answer

Ω-Notation

Question 37

Wie lautet die Rekursionsformel für die Fibonacci-Folge?

Accepted Answer

F(n) = F(n-1) + F(n-2)

Answer

F(n) = F(n)/2

Answer

F(n) = 2 * F(n-1)

Answer

F(n) = n + F(n-1)

Question 38

Welche Datenstruktur ermöglicht eine effiziente Suche nach einem Element in einer sortierten Liste?

Accepted Answer

Binärer Suchbaum

Answer

Array

Answer

Hashtabelle

Answer

Verkettete Liste

Question 39

Welcher Algorithmus durchläuft systematisch alle möglichen Lösungen eines Problems?

Accepted Answer

Backtracking

Answer

Divide-and-Conquer

Answer

Dynamische Programmierung

Answer

Greedy Algorithmus

Question 40

Was beschreibt die Laufzeit eines Algorithmus?

Accepted Answer

Die Anzahl der Schritte, die der Algorithmus zur Lösung eines Problems benötigt.

Answer

Die Komplexität des Algorithmus

Answer

Den Speicherplatzbedarf des Algorithmus

Question 41

Welcher Algorithmus ist ein Polynom-Algorithmus?

Accepted Answer

Algorithmus mit einer Komplexität von O(n^k)

Answer

Algorithmus mit einer Komplexität von O(n!)

Answer

Algorithmus mit einer Komplexität von O(log n)

Answer

Algorithmus mit einer Komplexität von O(2^n)

Question 42

Welcher Algorithmus ist ein Beispiel für einen Divide-and-Conquer-Algorithmus?

Accepted Answer

Quicksort

Answer

Dijkstra-Algorithmus

Answer

Breadth-First-Search

Answer

Bellman-Ford-Algorithmus

Question 43

Was ist das charakteristische Merkmal eines deterministischen Algorithmus?

Accepted Answer

Er erzeugt für gleiche Eingaben stets gleiche Ausgaben.

Answer

Er benötigt weniger Speicherplatz als ein nicht-deterministischer Algorithmus.

Answer

Er ist immer effizienter als ein nicht-deterministischer Algorithmus.

Question 44

Welches Kriterium ist bei der Komplexitätsanalyse von Algorithmen von zentraler Bedeutung?

Accepted Answer

Anzahl der durchgeführten Operationen.

Answer

Speicherverbrauch

Answer

Anzahl der verwendeten Variablen

Answer

Genaue Laufzeit in Sekunden

Question 45

Was unterscheidet einen Algorithmus grundsätzlich von einem Programm?

Accepted Answer

Ein Algorithmus ist eine formale Problembeschreibung, ein Programm hingegen eine konkrete Implementierung.

Answer

Ein Programm kann ohne einen Algorithmus erstellt werden.

Answer

Ein Algorithmus ist immer effizienter als ein Programm.

Question 46

Welcher der folgenden Algorithmen ist nicht deterministisch?

Accepted Answer

Zufallsgenerator

Answer

Quicksort

Answer

Bubblesort

Answer

Binärsuche

Question 47

Welches ist das primäre Ziel einer Komplexitätsanalyse?

Accepted Answer

Vorhersage des Ressourcenbedarfs eines Algorithmus

Answer

Behebung von Syntaxfehlern

Answer

Optimierung der Codequalität

Answer

Erstellung eines Flussdiagramms

Question 48

Welcher der folgenden Faktoren hat Einfluss auf die Komplexität eines Algorithmus?

Accepted Answer

Größe der Eingabe

Answer

Benutzerfreundlichkeit

Answer

Betriebssystem

Answer

Programmiersprache

Question 49

Was beschreibt die asymptotische Notation?

Accepted Answer

Das Verhalten eines Algorithmus bei sehr großen Eingaben

Answer

Eine spezielle Datenstruktur

Answer

Eine mathematische Formel zur Berechnung der Komplexität

Question 50

Welcher der folgenden Algorithmen besitzt die höchste Worst-Case-Komplexität?

Accepted Answer

Quadratische Sortierung

Answer

Binärsuche

Answer

Sortierung durch Zusammenführen

Answer

Lineare Suche

Question 51

Was ist der grundlegende Unterschied zwischen Zeitkomplexität und Raumkomplexität?

Accepted Answer

Zeitkomplexität misst die für die Ausführung eines Algorithmus benötigte Zeit, während Raumkomplexität den für die Speicherung der Daten benötigten Platz misst.

Answer

Zeitkomplexität ist immer höher als Raumkomplexität.

Question 52

Was beschreibt die Zeitkomplexität eines Algorithmus?

Accepted Answer

Die Laufzeit eines Algorithmus als Funktion der Eingabedatenmenge

Answer

Die Anzahl der Befehle, die der Algorithmus ausführt

Answer

Die Anzahl der Variablen, die der Algorithmus verwendet

Question 53

Welches Sortierverfahren basiert auf dem Divide-and-Conquer-Ansatz?

Accepted Answer

Quicksort

Answer

Insertionsort

Answer

Bubblesort

Question 54

Was ist die O-Notation?

Accepted Answer

Eine mathematische Notation zur Beschreibung der asymptotischen Komplexität eines Algorithmus

Answer

Die Anzahl der Schritte, die ein Algorithmus ausführt

Answer

Die Zeitkomplexität eines Algorithmus im besten Fall

Question 55

Welcher der folgenden Algorithmen ist ein rekursiver Algorithmus?

Accepted Answer

Fakultätsberechnung

Answer

Bubblesort

Answer

Liniensuche

Answer

Insertionsort

Question 56

Was ist die Worst-Case-Komplexität von Quicksort?

Accepted Answer

O(n^2)

Answer

O(log n)

Answer

O(n)

Question 57

Welche Datenstruktur kann für eine Warteschlange verwendet werden?

Accepted Answer

Verkettete Liste

Answer

Stapel

Answer

Hashtabelle

Question 58

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

Accepted Answer

Ein Algorithmus ist eine abstrakte Beschreibung eines Verfahrens, während ein Programm eine Implementierung des Algorithmus in einer bestimmten Programmiersprache ist.

Answer

Ein Algorithmus läuft schneller als ein Programm.

Question 59

Welche der folgenden Aussagen über die Zeitkomplexität von Algorithmen ist korrekt?

Accepted Answer

Die Zeitkomplexität hängt typischerweise von der Größe der Eingabedatenmenge ab.

Answer

Die Zeitkomplexität ist unabhängig von der Eingabe.

Answer

Die Zeitkomplexität ist immer konstant.

Question 60

Was ist das Ziel der Algorithmusanalyse?

Accepted Answer

Die Vorhersage der Leistung eines Algorithmus

Answer

Die Überprüfung der Korrektheit von Algorithmen

Answer

Die Entwicklung neuer Algorithmen

Answer

Die Optimierung bestehender Algorithmen