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