Analysetechniken in Algorithmen und Datenstrukturen: Online-Quiz für Studierende

Question 1

Welche Laufzeitanalysemethode berücksichtigt die Gesamtzahl der in einer Methode ausgeführten grundlegenden Operationen, auch über mehrere Aufrufe hinweg?

Accepted Answer

Amortisierte Analyse

Answer

Asymptotische Analyse

Answer

Worst-Case-Analyse

Answer

Average-Case-Analyse

Question 2

Welche Notation beschreibt die exponentielle Worst-Case-Laufzeit eines Algorithmus?

Accepted Answer

Ω(2^n)

Answer

O(n^k)

Answer

Θ(log n)

Answer

O(1)

Question 3

Welche Asymptotenklasse beschreibt einen Algorithmus mit exponentieller Laufzeit?

Accepted Answer

O(2^n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 4

Welche Datenstruktur zeichnet sich durch ihre konstanten Einfüge- und Suchzeiten aus?

Accepted Answer

Hash-Tabelle

Answer

Array

Answer

Verknüpfte Liste

Answer

Binärer Suchbaum

Question 5

Welche Aussage zur Analyse von Algorithmen ist falsch?

Accepted Answer

Sie ist nur für parallele Algorithmen anwendbar.

Answer

Sie hilft, die Effizienz von Algorithmen zu vergleichen.

Answer

Sie ermöglicht es, die obere Schranke für die Laufzeit zu bestimmen.

Answer

Sie berücksichtigt die Eingabegröße.

Question 6

Welche Asymptotenklasse beschreibt einen Algorithmus mit linearer Laufzeit?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 7

Welche Datenstruktur ist für die Implementierung einer Prioritätswarteschlange am besten geeignet?

Accepted Answer

Heap

Answer

Array

Answer

Verknüpfte Liste

Answer

Binärer Suchbaum

Question 8

Welche Asymptotenklasse beschreibt einen Algorithmus mit quadratischer Laufzeit?

Accepted Answer

O(n^2)

Answer

O(1)

Answer

O(log n)

Answer

O(2^n)

Question 9

Welches Landau-Symbol bezeichnet eine Funktion, die asymptotisch schneller wächst als jede Potenz?

Accepted Answer

ω(n)

Answer

O(n)

Answer

Θ(n)

Answer

o(n)

Question 10

Welcher der folgenden Algorithmen hat eine Laufzeitkomplexität von O(n^2)?

Accepted Answer

Bubblesort

Answer

Quicksort

Answer

Mergesort

Answer

Binäre Suche

Question 11

Welche der folgenden Techniken wird verwendet, um die amortisierte Analyse durchzuführen?

Accepted Answer

Alle der oben genannten.

Answer

Aggregationsmethode

Answer

Potentialmethode

Answer

Accountingmethode

Question 12

Welche der folgenden Aussagen zur Aggregationsmethode ist falsch?

Accepted Answer

Sie ist immer genauer als die Potentialmethode.

Answer

Sie betrachtet den Gesamtpreis aller Operationen.

Answer

Sie kann negative Kostenwerte berücksichtigen.

Answer

Sie ist einfacher anzuwenden als die Potentialmethode.

Question 13

Welche der folgenden Operationen in einem Binomialheap hat eine Laufzeitkomplexität von O(log n)?

Accepted Answer

Minimum finden

Answer

Einfügen

Answer

Löschen

Answer

Vereinigung

Question 14

Welche der folgenden Ausdrücke ist eine asymptotische Notation?

Accepted Answer

O(n^2)

Answer

3n + 5

Answer

n / 2

Answer

10000

Question 15

Was versteht man unter dem amortisierten Zeitaufwand eines Algorithmus?

Accepted Answer

Den durchschnittlichen Zeitaufwand über alle möglichen Eingaben

Answer

Den maximalen Zeitaufwand für die ungünstigste Eingabe

Answer

Den Zeitaufwand für die häufigste Eingabe

Answer

Den Zeitaufwand für die kürzeste Eingabe

Question 16

Welche Datenstruktur ist für die effiziente Speicherung von Mengen geeignet?

Accepted Answer

Hashtabelle

Answer

Liste

Answer

Stapel

Answer

Warteschlange

Question 17

Was ist ein wesentlicher Unterschied zwischen einer Liste und einem Array?

Accepted Answer

Listen sind dynamisch in ihrer Größe, während Arrays eine feste Größe haben.

Answer

Listen unterstützen nur den sequentiellen Zugriff, während Arrays den direkten Zugriff unterstützen.

Answer

Listen sind unveränderlich, während Arrays veränderlich sind.

Answer

Es gibt keinen wesentlichen Unterschied zwischen Listen und Arrays.

Question 18

Welcher Algorithmentyp ist der Dijkstra-Algorithmus?

Accepted Answer

Greedy-Algorithmus

Answer

Dynamischer Programmierungsalgorithmus

Answer

Backtracking-Algorithmus

Answer

Zufälliger Algorithmus

Question 19

Was ist der Hauptzweck einer Prioritätswarteschlange?

Accepted Answer

Elemente zu verwalten und abzurufen, wobei Elemente mit höherer Priorität zuerst verarbeitet werden.

Answer

Elemente in einer bestimmten Reihenfolge zu speichern.

Answer

Elemente effizient einzufügen und zu löschen.

Answer

Duplikate zu speichern und zu verwalten.

Question 20

Welche Technik zur Laufzeitoptimierung wird durch Memoization erreicht?

Accepted Answer

Die Speicherung von Zwischenergebnissen, um wiederholte Berechnungen zu vermeiden.

Answer

Die Verwendung von parallelen Prozessen zur Beschleunigung der Berechnungen.

Answer

Die Vereinfachung des Algorithmus, um den Zeitaufwand zu reduzieren.

Answer

Die Reduzierung der Eingabegröße, um den Zeitaufwand zu verringern.

Question 21

Was ist der Hauptunterschied zwischen einem Stack und einer Queue?

Accepted Answer

Ein Stack folgt dem LIFO-Prinzip (Last-In-First-Out), während eine Queue dem FIFO-Prinzip (First-In-First-Out) folgt.

Answer

Eine Queue folgt dem LIFO-Prinzip (Last-In-First-Out), während ein Stack dem FIFO-Prinzip (First-In-First-Out) folgt.

Answer

Ein Stack unterstützt nur den sequentiellen Zugriff, während eine Queue den direkten Zugriff unterstützt.

Answer

Es gibt keinen wesentlichen Unterschied zwischen einem Stack und einer Queue.

Question 22

Welche der folgenden Funktionen hat eine Zeitkomplexität von O(log n)?

Accepted Answer

Binäre Suche

Answer

Quicksort

Answer

Bubblesort

Answer

Lineare Suche

Question 23

Welche Aussage über die amortisierte Analyse ist zutreffend?

Accepted Answer

Sie bietet eine genauere Einschätzung der durchschnittlichen Laufzeit von Operationen.

Answer

Sie ist grundsätzlich pessimistischer als die Worst-Case-Analyse.

Answer

Sie ist nur auf linearisierte Datenstrukturen anwendbar.

Question 24

Welcher der folgenden Algorithmen hat für sortierte Eingaben eine Zeitkomplexität von O(n²)?

Accepted Answer

Insertion Sort

Answer

Binäre Suche

Answer

Quicksort

Answer

Hashing

Question 25

Welche der folgenden Aussagen zu Worst-Case-Analysen ist falsch?

Accepted Answer

Sie ist immer optimistischer als die amortisierte Analyse.

Answer

Sie ist für deterministische Algorithmen ausreichend.

Answer

Sie bestimmt eine obere Schranke für die Laufzeit.

Question 26

Welche Analysetechnik dient zur Bestimmung der Effizienz von rekursiven Algorithmen?

Accepted Answer

Rekursionsbaum

Answer

Binäre Suche

Answer

Amortisierte Analyse

Answer

Zeitvergleich

Question 27

Welche Analysetechnik wird verwendet, um die Leistung von Algorithmen mit zufälligen Eingaben zu bestimmen?

Accepted Answer

Wahrscheinlichkeitsanalyse

Answer

Worst-Case-Analyse

Answer

Amortisierte Analyse

Question 28

Welche Aussage zur Big-O-Notation ist richtig?

Accepted Answer

Sie beschreibt die obere Schranke der Wachstumsrate einer Funktion.

Answer

Sie gibt die genaue Laufzeit einer Funktion an.

Answer

Sie gilt ausschließlich für lineare Funktionen.

Question 29

Welche asymptotische Notation beschreibt die beste Laufzeitkomplexität für die Suche eines Elements in einer sortierten Liste?

Accepted Answer

O(log n)

Answer

O(n^2)

Answer

O(n)

Answer

O(1)

Question 30

Welcher der folgenden Algorithmen hat die beste durchschnittliche Fallkomplexität für die Suche eines Elements in einem binären Suchbaum?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(1)

Answer

O(n^2)

Question 31

Welche der folgenden Aussagen über die asymptotische Zeitkomplexität des Bubble-Sort-Algorithmus für n Elemente ist korrekt?

Accepted Answer

O(n^2)

Answer

O(n log n)

Answer

O(log n)

Answer

O(n)

Question 32

Welcher der folgenden Algorithmen hat die beste asymptotische Raumkomplexität für die Suche des Minimums in einem Array?

Accepted Answer

O(1)

Answer

O(log n)

Answer

O(n)

Question 33

Welche der folgenden Aussagen über die Theta-Notation ist korrekt?

Accepted Answer

Sie beschreibt die enge obere und untere Grenze der asymptotischen Komplexität.

Answer

Sie beschreibt nur die obere Grenze der asymptotischen Komplexität.

Answer

Sie beschreibt nur die untere Grenze der asymptotischen Komplexität.

Question 34

Welche Aussage über die amortisierte Analyse des Stacks ist korrekt?

Accepted Answer

Sie berücksichtigt den durchschnittlichen Aufwand pro Operation für alle möglichen Sequenzen von Operationen.

Answer

Sie berücksichtigt nur den Worst-Case-Aufwand einer einzelnen Operation.

Question 35

Welche der folgenden Methoden kann verwendet werden, um Rekursionsalgorithmen zu analysieren?

Accepted Answer

Rückwärtssubstitution oder Auspacken der Rekursionsaufrufe

Answer

Nur Rückwärtssubstitution

Answer

Nur Auspacken der Rekursionsaufrufe

Question 36

Welches der folgenden Maße beschreibt nicht die Komplexität eines Algorithmus?

Accepted Answer

Bitkomplexität

Answer

Raumkomplexität

Answer

Zeitkomplexität

Answer

Best-Case-Komplexität

Question 37

Welche Notationsform beschreibt eine Funktion, die langsamer wächst als eine lineare Funktion?

Accepted Answer

O(log n)

Answer

O(n^2)

Answer

O(2^n)

Answer

O(n)

Question 38

Welche Analysetechnik wird verwendet, um eine Obergrenze für die Worst-Case-Laufzeit eines Algorithmus zu bestimmen?

Accepted Answer

Asymptotische Analyse

Answer

Amortisierte Analyse

Answer

Experimentelle Analyse

Answer

Probabilistische Analyse

Question 39

Mit welcher Big-O-Notation wird eine Funktion beschrieben, deren Laufzeit quadratisch mit der Eingangsgröße wächst?

Accepted Answer

O(n²)

Answer

O(n)

Answer

O(1)

Answer

O(log n)

Question 40

Welche Algorithmenkategorie weist eine Laufzeit von O(2^n) auf?

Accepted Answer

Exponentialalgorithmus

Answer

Linearealgorithmus

Answer

Logarithmischer Algorithmus

Answer

Quadratischer Algorithmus

Question 41

Was beschreibt die Amortisierungsanalyse?

Accepted Answer

Sie analysiert die durchschnittlichen Kosten pro Operation über eine Folge von Operationen.

Answer

Sie ist nur für Algorithmen mit konstanter Laufzeit anwendbar.

Answer

Sie liefert immer eine Untergrenze für die Laufzeit.

Question 42

Was ist ein Vorteil der asymptotischen Analyse?

Accepted Answer

Sie ermöglicht es, die Leistung eines Algorithmus für große Eingaben zu charakterisieren.

Answer

Sie ist genauer als die Amortisierungsanalyse.

Answer

Sie ist einfacher durchzuführen als die experimentelle Analyse.

Question 43

Welche Algorithmenkategorie hat typischerweise eine Laufzeit von O(n log n)?

Accepted Answer

Sortier-Algorithmus

Answer

Einfüge-Algorithmus

Answer

Löschen-Algorithmus

Answer

Such-Algorithmus

Question 44

Wie lautet die Big-Theta-Notation einer Funktion, deren Laufzeit proportional zur Eingabegröße wächst?

Accepted Answer

Θ(n)

Answer

O(1)

Answer

O(n)

Answer

Ω(n)

Question 45

Was ist das Hauptmerkmal der experimentellen Analyse?

Accepted Answer

Sie misst die tatsächliche Laufzeit eines Algorithmus auf einer bestimmten Eingabe.

Answer

Sie liefert eine exakte Vorhersage der Laufzeit.

Answer

Sie ist unabhängig von der verwendeten Hardware.

Question 46

Welcher Aussage zufolge ist die asymptotische Analyse am zutreffendsten?

Accepted Answer

Sie dient dazu, die Leistung eines Algorithmus für sehr große Eingaben zu bewerten.

Answer

Sie analysiert die Laufzeit eines Algorithmus für alle möglichen Eingaben.

Question 47

Welche Notation repräsentiert die Big-O-Notation?

Accepted Answer

O(f(n))

Answer

Ω(f(n))

Answer

Θ(f(n))

Question 48

Welche Technik kann dazu beitragen, die Laufzeit eines Algorithmus mit rekursiven Funktionsaufrufen zu reduzieren?

Accepted Answer

Memoisierung

Answer

Heuristik

Answer

Dynamische Programmierung

Answer

Zweige und Schranken

Question 49

Welche Aussage über die amortisierte Analyse ist falsch?

Accepted Answer

Sie berücksichtigt nur Worst-Case-Szenarien.

Answer

Sie kann verwendet werden, um die durchschnittliche Laufzeit zu bestimmen.

Answer

Sie ist nützlich für Algorithmen mit nichtlinearem Zeitverhalten.

Question 50

Welche Funktion beschreibt die Laufzeit des folgenden Algorithmus: 
For i = 1 to n:
  For j = 1 to i:
    print(i + j))

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(n log n)

Answer

O(2^n)

Question 51

Was ist ein wesentlicher Vorteil der Komplexitätsanalyse?

Accepted Answer

Sie kann dabei helfen, die Praktikabilität eines Algorithmus für unterschiedliche Eingabedatenmengen zu bestimmen.

Answer

Sie ist nur für die Analyse von Algorithmen mit rekursiver Struktur hilfreich.

Question 52

Welche der folgenden Strategien kann verwendet werden, um die worst-Case Laufzeit eines Algorithmus zu verbessern?

Accepted Answer

Verwendung einer effizienteren Datenstruktur

Answer

Reduktion der Anzahl der Schleifen im Algorithmus

Answer

Implementierung des Algorithmus in einer schnelleren Programmiersprache

Answer

Erhöhung des Speicherbedarfs des Algorithmus

Question 53

Welche Analysetechnik wird zur Bestimmung der worst-Case Laufzeit eines Algorithmus verwendet?

Accepted Answer

Asymptotische Analyse

Answer

Stochastische Analyse

Answer

Amortierte Analyse

Question 54

Welche Notation wird zur Darstellung der asymptotischen oberen Schranke der Laufzeit eines Algorithmus verwendet?

Accepted Answer

O-Notation

Answer

Θ-Notation

Answer

Ω-Notation

Question 55

Welche Analysetechnik wird verwendet, um die erwartete Laufzeit eines Algorithmus zu bestimmen?

Accepted Answer

Amortierte Analyse

Answer

Asymptotische Analyse

Answer

Experimentelle Analyse

Answer

Statistische Analyse

Question 56

Welche der folgenden Operationen hat eine Laufzeit von O(log n)?

Accepted Answer

Binäre Suche

Answer

Hashing

Answer

Lineare Suche

Answer

Sortierung

Question 57

Welche der folgenden Operationen hat eine Laufzeit von O(n^2)?

Accepted Answer

Bubblesort

Answer

Merge Sort

Answer

Hashing

Answer

Binäre Suche

Question 58

Welche Analysetechnik kann verwendet werden, um den Speicherbedarf eines Algorithmus zu bestimmen?

Accepted Answer

Asymptotische Analyse

Answer

Experimentelle Analyse

Answer

Statistische Analyse

Answer

Amortierte Analyse

Question 59

Welche der folgenden Notationen wird verwendet, um die asymptotische untere Schranke der Laufzeit eines Algorithmus auszudrücken?

Accepted Answer

Ω-Notation

Answer

O-Notation

Answer

o-Notation

Answer

Θ-Notation

Question 60

Welche der folgenden Notationen wird verwendet, um die asymptotisch enge Schranke für die Laufzeit eines Algorithmus auszudrücken?

Accepted Answer

Theta-Notation

Answer

O-Notation

Answer

Groß-o-Notation

Answer

Omega-Notation