Tobias Ranke
Quiz by , created more than 1 year ago

Fragen eines Algorithmikmoduls auf Masterniveau

175
0
0
Tobias Ranke
Created by Tobias Ranke over 8 years ago
Close

Multiple Choice Fragen

Question 1 of 51

1

Dijkstras Algorithmus folgt dem Entwurfsprinzip "Divide and Conquer".

Select one of the following:

  • True
  • False

Explanation

Question 2 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 3 of 51

1

Optimale Suchbäume lassen sich in quadratischer Zeit berechnen.

Select one of the following:

  • True
  • False

Explanation

Question 4 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 5 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 6 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 7 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 8 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 9 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 10 of 51

1

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)

Select one of the following:

  • True
  • False

Explanation

Question 11 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 12 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 13 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 14 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 15 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 16 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 17 of 51

1

Wie lautet die Laufzeit von Kruskal?

Select one of the following:

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

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

Explanation

Question 18 of 51

1

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

Select one of the following:

  • ...das Pivotelement in der Mitte steht.

  • ...das Pivotelement am Ende steht.

Explanation

Question 19 of 51

1

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

Select one of the following:

  • 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)

Explanation

Question 20 of 51

1

Die zentrale Operation von Prim ist Union-Find?

Select one of the following:

  • True
  • False

Explanation

Question 21 of 51

1

Eine Hashfamilie heißt universell, wenn gilt:

Select one of the following:

  • Hashtafelgröße ist kubisch.

  • Wahrscheinlichkeit (h(x)=h(y))<= 1/m

  • Wahrscheinlichkeit (h(x)=h(y))>= 1/n

Explanation

Question 22 of 51

1

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

Select one of the following:

  • m=n²

  • m=n³

  • m = n mod |U|

Explanation

Question 23 of 51

1

Warshalls Algorithmus berechnet im Gegensatz zu Floyds Algorithmus:

Select one of the following:

  • die transitive Hülle

  • kürzeste Wege

  • das selbe

Explanation

Question 24 of 51

1

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

Select one of the following:

  • decrease_key

  • delete_min

  • insert

Explanation

Question 25 of 51

1

Dynamische Programme liegen in der Komplexitätsklasse

Select one of the following:

  • Polynomiell

  • Pseudopolynomiell

  • Exponentiell

Explanation

Question 26 of 51

1

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

Select one of the following:

  • 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)

Explanation

Question 27 of 51

1

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

Select one of the following:

  • O(n^2,81)

  • O(n^2,83)

  • O(nlog(n))

  • O(n)

Explanation

Question 28 of 51

1

Wie viele Übergangskanten hat der Endliche Automat des KMP Algorithmus

Select one of the following:

  • 2(m + 2)

  • m²-1

  • m/epsilon

Explanation

Question 29 of 51

1

Die Grundform des Mastertheorem 1 ist:

Select one of the following:

  • 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.

Explanation

Question 30 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 31 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 32 of 51

1

Der CYK-Algorithmus läuft in:

Select one of the following:

  • O(n²)

  • O(n³)

  • O(n log(n))

Explanation

Question 33 of 51

1

Welcher dieser Kuchenschneidalgorithmen ist nicht neidfrei?

Select one of the following:

  • Moving-Knife-Algorithmus

  • Successive-Pairs-Algorithmus

  • Trimming-Algorithmus

Explanation

Question 34 of 51

1

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

Select one of the following:

  • g(c)<=g(cPhase)

  • g(c)>=g(cPhase)

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

Explanation

Question 35 of 51

1

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

Select one of the following:

  • 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.

Explanation

Question 36 of 51

1

Kruskal hat eine Laufzeit von:

Select one of the following:

  • O(|E|*log|V|)

  • O(|V|*log|E|)

  • O(|V|²+|E|)

Explanation

Question 37 of 51

1

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

Select one of the following:

  • O(n²2n)

  • O(n³)

  • O(n log(n)* n²)

Explanation

Question 38 of 51

1

Valiants Algorithmus läuft in:

Select one of the following:

  • O(n^log7)

  • O(n^1,93)

  • O(n³)

Explanation

Question 39 of 51

1

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

Select one of the following:

  • n²

  • natürlich der selben Zeit, n³

  • da er nur auf einer Adjazenzmatrix arbeitet in n

Explanation

Question 40 of 51

1

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

Select one of the following:

  • Zwei Endzustände

  • Ein normaler Zustand, ein Endzustand

  • Ein Startzustand und ein Endzustand

Explanation

Question 41 of 51

1

Negative Kanten sind bei Dijkstra nicht erlaubt?

Select one of the following:

  • True
  • False

Explanation

Question 42 of 51

1

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

Select one of the following:

  • n log(n) Vergleiche

  • 2n log(n) Vergleiche

  • n log log(n) Vergleiche

Explanation

Question 43 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 44 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 45 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 46 of 51

1

Welche Laufzeit hat der Karger-Stein Algorithmus?

Select one of the following:

  • O(n² log n)

  • O(n²)

  • O(n logn)

Explanation

Question 47 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 48 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 49 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 50 of 51

1

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

Select one of the following:

  • True
  • False

Explanation

Question 51 of 51

1

Prims Algorithmus benötigt:

Select one of the following:

  • O(n²)

  • O(|E|+|V|²)

  • O(n logn)

Explanation

Previous
Check answer
Next