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