5963638
Beschreibung
Quiz von Tobias Ranke, aktualisiert more than 1 year ago
|
Erstellt von Tobias Ranke
vor fast 8 Jahre
|
|
Frage 1
Frage
Dijkstras Algorithmus folgt dem Entwurfsprinzip "Divide and Conquer".
Antworten
- True
- False
Frage 2
Frage
Ein Fibunacci-Heap mit n Knoten hat maximale Höhe O(log n)?
Antworten
- True
- False
Frage 3
Frage
Optimale Suchbäume lassen sich in quadratischer Zeit berechnen.
Antworten
- True
- False
Frage 4
Frage
Der Median einer Menge ganzer Zahlen kann gleich ihrem
Maximum sein.
Antworten
- True
- False
Frage 5
Frage
Bubblesort benötigt auf allen Eingaben mehr Vergleiche als
Heapsort.
Antworten
- True
- False
Frage 6
Frage
Verwendet man Fibonacci-Heaps zur Implementierung von
Heapsort, so erreicht man eine Worst-Case-Laufzeit von
O(n log log n).
Antworten
- True
- False
Frage 7
Frage
Der in der Vorlesung behandelte Algorithmus von Stoer und Wagner berechnet einen minimalen Schnitt eines Graphen.
Antworten
- True
- False
Frage 8
Frage
Quickselect benötigt im Durchschnitt nicht mehr als 4n Vergleiche auf einem Feld mit n Elementen.
Antworten
- True
- False
Frage 9
Frage
Ein Fibunacci-Heap mit n Knoten kann eine Höhe von n erreichen.
Antworten
- True
- False
Frage 10
Frage
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)
Antworten
- True
- False
Frage 11
Frage
Prims Algorithmus zur Berechnung eines minimalen Spannbaumes folgt dem Entwurfsprinzip "Union-Find"
Antworten
- True
- False
Frage 12
Frage
Bubblesort benötigt auf allen Eingaben mehr Vergleiche als Heapsort.
Antworten
- True
- False
Frage 13
Frage
Der Algorithmus von Schönhage und Strassen zur schnellen Multiplikation ganzer Zahlen verwendet die schnelle Fouriertransformation.
Antworten
- True
- False
Frage 14
Frage
Quickselect benötigt im Mittel mehr als 15n Vergleiche.
Antworten
- True
- False
Frage 15
Frage
Es ist kein Algorithmus zur Berechnung optimaler Suchbäume in subkubischer Zeit bekannt.
Antworten
- True
- False
Frage 16
Frage
Mergesort benötigt durchschnittlich Theta von (n log n)
Antworten
- True
- False
Frage 17
Frage
Wie lautet die Laufzeit von Kruskal?
Antworten
-
O(|E|+log |V|)
-
O(|V|+ log log |V|+|E|)
Frage 18
Frage
Quickselect benötigt O(n²) wenn...
Antworten
-
...das Pivotelement in der Mitte steht.
-
...das Pivotelement am Ende steht.
Frage 19
Frage
Die Formel, welche das Dynamische Programm zur Berechnung der optimalen Anzahl an Multiplikationen zur Multiplikation mehrerer Matrizen anwendet lautet:
Antworten
-
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)
Frage 20
Frage
Die zentrale Operation von Prim ist Union-Find?
Antworten
- True
- False
Frage 21
Frage
Eine Hashfamilie heißt universell, wenn gilt:
Antworten
-
Hashtafelgröße ist kubisch.
-
Wahrscheinlichkeit (h(x)=h(y))<= 1/m
-
Wahrscheinlichkeit (h(x)=h(y))>= 1/n
Frage 22
Frage
Damit die Wahrscheinlichkeit , dass eine Hashfunktion h injektiv ist, größer gleich 1/2 ist, muss folgendes gegeben sein:
Antworten
-
m=n²
-
m=n³
-
m = n mod |U|
Frage 23
Frage
Warshalls Algorithmus berechnet im Gegensatz zu Floyds Algorithmus:
Antworten
-
die transitive Hülle
-
kürzeste Wege
-
das selbe
Frage 24
Frage
Bei welcher Operation werden bei Fibonacci-Heaps größere Bäume (ausgehend von deren Wurzel) unter die Wurzel des kleineren gehangen?
Antworten
-
decrease_key
-
delete_min
-
insert
Frage 25
Frage
Dynamische Programme liegen in der Komplexitätsklasse
Antworten
-
Polynomiell
-
Pseudopolynomiell
-
Exponentiell
Frage 26
Frage
Bei Fibonacci-Heaps haben Merge, Insert, delete_min sowie decrease_key die Laufzeit:
Antworten
-
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)
Frage 27
Frage
Im Vergleich zur naiven Multiplikation von O(n³) benötigt die Matrizenmultiplikation von Volker Strassen:
Antworten
-
O(n^2,81)
-
O(n^2,83)
-
O(nlog(n))
-
O(n)
Frage 28
Frage
Wie viele Übergangskanten hat der Endliche Automat des KMP Algorithmus
Antworten
-
2(m + 2)
-
m²-1
-
m/epsilon
Frage 29
Frage
Die Grundform des Mastertheorem 1 ist:
Antworten
-
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.
Frage 30
Frage
Verwendet man Fibonacci-Heaps zur Implementierung von
Heapsort, so erreicht man eine Worst-Case-Laufzeit von
O(e*log n+ n*log n).
Antworten
- True
- False
Frage 31
Frage
Der in der Vorlesung behandelte Algorithmus von Stoer und Wagner
berechnet einen minimalen Schnitt eines Graphen.
Antworten
- True
- False
Frage 32
Frage
Der CYK-Algorithmus läuft in:
Antworten
-
O(n²)
-
O(n³)
-
O(n log(n))
Frage 33
Frage
Welcher dieser Kuchenschneidalgorithmen ist nicht neidfrei?
Antworten
-
Moving-Knife-Algorithmus
-
Successive-Pairs-Algorithmus
-
Trimming-Algorithmus
Frage 34
Frage
Welche dieser Aussagen über den Stör-Wagner-Algorithmus ist zutreffend?
Antworten
-
g(c)<=g(cPhase)
-
g(c)>=g(cPhase)
-
g(c)<=G(cPhase+1)
Frage 35
Frage
Diese Frage bezieht sich auf Fibonacci Heaps:
Verliert ein Knoten mehr als ein Kind, dann...
Antworten
-
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.
Frage 36
Frage
Kruskal hat eine Laufzeit von:
Antworten
-
O(|E|*log|V|)
-
O(|V|*log|E|)
-
O(|V|²+|E|)
Frage 37
Frage
Das Rucksackproblem lässt sich durch Branch and Bound in:
Antworten
-
O(n²2n)
-
O(n³)
-
O(n log(n)* n²)
Frage 38
Frage
Valiants Algorithmus läuft in:
Antworten
-
O(n^log7)
-
O(n^1,93)
-
O(n³)
Frage 39
Frage
Warshalls Algorithmus läuft im Gegensatz zu Floyds Algorithmus in:
Antworten
-
n²
-
natürlich der selben Zeit, n³
-
da er nur auf einer Adjazenzmatrix arbeitet in n
Frage 40
Frage
Was ist die Abbruchbedingung für den Äquivalenztest Endlicher Automaten?
Antworten
-
Zwei Endzustände
-
Ein normaler Zustand, ein Endzustand
-
Ein Startzustand und ein Endzustand
Frage 41
Frage
Negative Kanten sind bei Dijkstra nicht erlaubt?
Antworten
- True
- False
Frage 42
Frage
Bottom-up Heapsort benötigt im Vergleich zu Standardheapsort nur:
Antworten
-
n log(n) Vergleiche
-
2n log(n) Vergleiche
-
n log log(n) Vergleiche
Frage 43
Frage
Die Laufzeit des Äquivalenztests endlicher Automaten beträgt O(n2)
Antworten
- True
- False
Frage 44
Frage
Sei M eine Menge reeler Zahlen mit 3 <=|M| < unendlich. Der Median von M kann gleich dem
Minimum von M sein.
Antworten
- True
- False
Frage 45
Frage
Der Algorithmus von Matiyasevich, Knuth, Morris und Pratt testet endliche Automaten auf Aquivalenz.
Antworten
- True
- False
Frage 46
Frage
Welche Laufzeit hat der Karger-Stein Algorithmus?
Antworten
-
O(n² log n)
-
O(n²)
-
O(n logn)
Frage 47
Frage
Bei Heapsort werden immer mehr als die Halfte der Vergleiche waehrend des Heapaufbaus ausgefuhrt.
Antworten
- True
- False
Frage 48
Frage
Der in der Vorlesung behandelte Algorithmus von Karger und Stein zur Berechnung eines minimalen Schnitts liefert immer ein korrektes Ergebnis.
Antworten
- True
- False
Frage 49
Frage
Bei Union-Find mit Pfadverkürzung sind die Kosten O(n*inverseAckermannfkt(n))?
Antworten
- True
- False
Frage 50
Frage
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
Antworten
- True
- False
Frage 51
Frage
Prims Algorithmus benötigt:
Antworten
-
O(n²)
-
O(|E|+|V|²)
-
O(n logn)
Möchten Sie mit GoConqr kostenlos Ihre eigenen Quiz erstellen? eigenen Mehr erfahren.