Changing the way you learn

Question 1

Question

Dijkstras Algorithmus folgt dem Entwurfsprinzip "Divide and Conquer".

Answer

True
False

Question 2

Question

Ein Fibunacci-Heap mit n Knoten hat maximale Höhe O(log n)?

Answer

True
False

Question 3

Question

Optimale Suchbäume lassen sich in quadratischer Zeit berechnen.

Answer

True
False

Question 4

Question

Der Median einer Menge ganzer Zahlen kann gleich ihrem Maximum sein.

Answer

True
False

Question 5

Question

Bubblesort benötigt auf allen Eingaben mehr Vergleiche als Heapsort.

Answer

True
False

Question 6

Question

Verwendet man Fibonacci-Heaps zur Implementierung von Heapsort, so erreicht man eine Worst-Case-Laufzeit von O(n log log n).

Answer

True
False

Question 7

Question

Der in der Vorlesung behandelte Algorithmus von Stoer und Wagner berechnet einen minimalen Schnitt eines Graphen.

Answer

True
False

Question 8

Question

Quickselect benötigt im Durchschnitt nicht mehr als 4n Vergleiche auf einem Feld mit n Elementen.

Answer

True
False

Question 9

Question

Ein Fibunacci-Heap mit n Knoten kann eine Höhe von n erreichen.

Answer

True
False

Question 10

Question

Verwendet man Fibunacci-Heaps zur Implementierung von Dijkstras Algorithmus zur Berechnung kürzester Wege, so ist die Laufzeit in O (|E|+|V|log|V|) für einen Graphen G = (V,E,Lamda)

Answer

True
False

Question 11

Question

Prims Algorithmus zur Berechnung eines minimalen Spannbaumes folgt dem Entwurfsprinzip "Union-Find"

Answer

True
False

Question 12

Question

Bubblesort benötigt auf allen Eingaben mehr Vergleiche als Heapsort.

Answer

True
False

Question 13

Question

Der Algorithmus von Schönhage und Strassen zur schnellen Multiplikation ganzer Zahlen verwendet die schnelle Fouriertransformation.

Answer

True
False

Question 14

Question

Quickselect benötigt im Mittel mehr als 15n Vergleiche.

Answer

True
False

Question 15

Question

Es ist kein Algorithmus zur Berechnung optimaler Suchbäume in subkubischer Zeit bekannt.

Answer

True
False

Question 16

Question

Mergesort benötigt durchschnittlich Theta von (n log n)

Answer

True
False

Question 17

Question

Wie lautet die Laufzeit von Kruskal?

Answer

O(|E|+log |V|)
O(|V|+ log log |V|+|E|)

Question 18

Question

Quickselect benötigt O(n²) wenn...

Answer

...das Pivotelement in der Mitte steht.
...das Pivotelement am Ende steht.

Question 19

Question

Die Formel, welche das Dynamische Programm zur Berechnung der optimalen Anzahl an Multiplikationen zur Multiplikation mehrerer Matrizen anwendet lautet:

Answer

min SummeUeberK (cost(i,k)+cost(k+1,j)+n(i-1)*n(k)*n(j) für i<=k<j)
min SummeUeberk (cost(i,k)+cost(k-1,j)+n(i+1)*n(k)*n(j) für i<k<=j)
min SummeUeberi (cost(i-1,k)+cost(k-1,j)+n(i+1)*n(k)*n(j) für i<k<=j)

Question 20

Question

Die zentrale Operation von Prim ist Union-Find?

Answer

True
False

Question 21

Question

Eine Hashfamilie heißt universell, wenn gilt:

Answer

Hashtafelgröße ist kubisch.
Wahrscheinlichkeit (h(x)=h(y))<= 1/m
Wahrscheinlichkeit (h(x)=h(y))>= 1/n

Question 22

Question

Damit die Wahrscheinlichkeit , dass eine Hashfunktion h injektiv ist, größer gleich 1/2 ist, muss folgendes gegeben sein:

Answer

m=n²
m=n³
m = n mod |U|

Question 23

Question

Warshalls Algorithmus berechnet im Gegensatz zu Floyds Algorithmus:

Answer

die transitive Hülle
kürzeste Wege
das selbe

Question 24

Question

Bei welcher Operation werden bei Fibonacci-Heaps größere Bäume (ausgehend von deren Wurzel) unter die Wurzel des kleineren gehangen?

Answer

decrease_key
delete_min
insert

Question 25

Question

Dynamische Programme liegen in der Komplexitätsklasse

Answer

Polynomiell
Pseudopolynomiell
Exponentiell

Question 26

Question

Bei Fibonacci-Heaps haben Merge, Insert, delete_min sowie decrease_key die Laufzeit:

Answer

O(1), O(1), O(T+log n) und O(1)+O(k)
O(n), O(1), O(nlog n) und O(1)+O(k)
O(1)+O(K), O(1), O(T+log n) und O(n)

Question 27

Question

Im Vergleich zur naiven Multiplikation von O(n³) benötigt die Matrizenmultiplikation von Volker Strassen:

Answer

O(n^2,81)
O(n^2,83)
O(nlog(n))
O(n)

Question 28

Question

Wie viele Übergangskanten hat der Endliche Automat des KMP Algorithmus

Answer

2(m + 2)
m²-1
m/epsilon

Question 29

Question

Die Grundform des Mastertheorem 1 ist:

Answer

a*T(n/b)+g(n) für n>=b.
a*T(n/b)*g(n) für n>=1.
a*T(b/n)*g(n) für n>b.

Question 30

Question

Verwendet man Fibonacci-Heaps zur Implementierung von Heapsort, so erreicht man eine Worst-Case-Laufzeit von O(e*log n+ n*log n).

Answer

True
False

Question 31

Question

Der in der Vorlesung behandelte Algorithmus von Stoer und Wagner berechnet einen minimalen Schnitt eines Graphen.

Answer

True
False

Question 32

Question

Der CYK-Algorithmus läuft in:

Answer

O(n²)
O(n³)
O(n log(n))

Question 33

Question

Welcher dieser Kuchenschneidalgorithmen ist nicht neidfrei?

Answer

Moving-Knife-Algorithmus
Successive-Pairs-Algorithmus
Trimming-Algorithmus

Question 34

Question

Welche dieser Aussagen über den Stör-Wagner-Algorithmus ist zutreffend?

Answer

g(c)<=g(cPhase)
g(c)>=g(cPhase)
g(c)<=G(cPhase+1)

Question 35

Question

Diese Frage bezieht sich auf Fibonacci Heaps: Verliert ein Knoten mehr als ein Kind, dann...

Answer

Wird geprüft, dass nicht mehr als 2 Bäume des selben Ranges sich auf einem Level befinden.
Wird der Teilbaum am verlustreichen Knoten mitsamt diesem abgetrennt und der Knoten wird zur Wurzel.

Question 36

Question

Kruskal hat eine Laufzeit von:

Answer

O(|E|*log|V|)
O(|V|*log|E|)
O(|V|²+|E|)

Question 37

Question

Das Rucksackproblem lässt sich durch Branch and Bound in:

Answer

O(n²2n)
O(n³)
O(n log(n)* n²)

Question 38

Question

Valiants Algorithmus läuft in:

Answer

O(n^log7)
O(n^1,93)
O(n³)

Question 39

Question

Warshalls Algorithmus läuft im Gegensatz zu Floyds Algorithmus in:

Answer

n²
natürlich der selben Zeit, n³
da er nur auf einer Adjazenzmatrix arbeitet in n

Question 40

Question

Was ist die Abbruchbedingung für den Äquivalenztest Endlicher Automaten?

Answer

Zwei Endzustände
Ein normaler Zustand, ein Endzustand
Ein Startzustand und ein Endzustand

Question 41

Question

Negative Kanten sind bei Dijkstra nicht erlaubt?

Answer

True
False

Question 42

Question

Bottom-up Heapsort benötigt im Vergleich zu Standardheapsort nur:

Answer

n log(n) Vergleiche
2n log(n) Vergleiche
n log log(n) Vergleiche

Question 43

Question

Die Laufzeit des Äquivalenztests endlicher Automaten beträgt O(n2)

Answer

True
False

Question 44

Question

Sei M eine Menge reeler Zahlen mit 3 <=|M| < unendlich. Der Median von M kann gleich dem Minimum von M sein.

Answer

True
False

Question 45

Question

Der Algorithmus von Matiyasevich, Knuth, Morris und Pratt testet endliche Automaten auf Aquivalenz.

Answer

True
False

Question 46

Question

Welche Laufzeit hat der Karger-Stein Algorithmus?

Answer

O(n² log n)
O(n²)
O(n logn)

Question 47

Question

Bei Heapsort werden immer mehr als die Halfte der Vergleiche waehrend des Heapaufbaus ausgefuhrt.

Answer

True
False

Question 48

Question

Der in der Vorlesung behandelte Algorithmus von Karger und Stein zur Berechnung eines minimalen Schnitts liefert immer ein korrektes Ergebnis.

Answer

True
False

Question 49

Question

Bei Union-Find mit Pfadverkürzung sind die Kosten O(n*inverseAckermannfkt(n))?

Answer

True
False

Question 50

Question

Angenommen Alice beabsichtigt, an Bob über Oskar ein unterschriebenes Dokument (x, h(x)) zu senden, der jedoch (y, s) mit x ungleich y weitergibt. Oskar wählt die ”Unterschrift” s ∈ Fp bzgl. irgendeiner selbstgewählten Strategie. Dann ist die Wahrscheinlichkeit= 1/p², dass Bob von der Sache Wind bekommt

Answer

True
False

Question 51

Question

Prims Algorithmus benötigt:

Answer

O(n²)
O(|E|+|V|²)
O(n logn)

	Created by Tobias Ranke over 7 years ago

Next up

Multiple Choice Fragen

Description

Resource summary

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Question 11

Question 12

Question 13

Question 14

Question 15

Question 16

Question 17

Question 18

Question 19

Question 20

Question 21

Question 22

Question 23

Question 24

Question 25

Question 26

Question 27

Question 28

Question 29

Question 30

Question 31

Question 32

Question 33

Question 34

Question 35

Question 36

Question 37

Question 38

Question 39

Question 40

Question 41

Question 42

Question 43

Question 44

Question 45

Question 46

Question 47

Question 48

Question 49

Question 50

Question 51

Similar