Tobias Ranke
Test por , creado hace más de 1 año

Fragen eines Algorithmikmoduls auf Masterniveau

175
0
0
Tobias Ranke
Creado por Tobias Ranke hace más de 8 años
Cerrar

Multiple Choice Fragen

Pregunta 1 de 51

1

Dijkstras Algorithmus folgt dem Entwurfsprinzip "Divide and Conquer".

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 2 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 3 de 51

1

Optimale Suchbäume lassen sich in quadratischer Zeit berechnen.

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 4 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 5 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 6 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 7 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 8 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 9 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 10 de 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)

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 11 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 12 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 13 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 14 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 15 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 16 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 17 de 51

1

Wie lautet die Laufzeit von Kruskal?

Selecciona una de las siguientes respuestas posibles:

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

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

Explicación

Pregunta 18 de 51

1

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

Selecciona una de las siguientes respuestas posibles:

  • ...das Pivotelement in der Mitte steht.

  • ...das Pivotelement am Ende steht.

Explicación

Pregunta 19 de 51

1

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

Selecciona una de las siguientes respuestas posibles:

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

Explicación

Pregunta 20 de 51

1

Die zentrale Operation von Prim ist Union-Find?

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 21 de 51

1

Eine Hashfamilie heißt universell, wenn gilt:

Selecciona una de las siguientes respuestas posibles:

  • Hashtafelgröße ist kubisch.

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

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

Explicación

Pregunta 22 de 51

1

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

Selecciona una de las siguientes respuestas posibles:

  • m=n²

  • m=n³

  • m = n mod |U|

Explicación

Pregunta 23 de 51

1

Warshalls Algorithmus berechnet im Gegensatz zu Floyds Algorithmus:

Selecciona una de las siguientes respuestas posibles:

  • die transitive Hülle

  • kürzeste Wege

  • das selbe

Explicación

Pregunta 24 de 51

1

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

Selecciona una de las siguientes respuestas posibles:

  • decrease_key

  • delete_min

  • insert

Explicación

Pregunta 25 de 51

1

Dynamische Programme liegen in der Komplexitätsklasse

Selecciona una de las siguientes respuestas posibles:

  • Polynomiell

  • Pseudopolynomiell

  • Exponentiell

Explicación

Pregunta 26 de 51

1

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

Selecciona una de las siguientes respuestas posibles:

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

Explicación

Pregunta 27 de 51

1

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

Selecciona una de las siguientes respuestas posibles:

  • O(n^2,81)

  • O(n^2,83)

  • O(nlog(n))

  • O(n)

Explicación

Pregunta 28 de 51

1

Wie viele Übergangskanten hat der Endliche Automat des KMP Algorithmus

Selecciona una de las siguientes respuestas posibles:

  • 2(m + 2)

  • m²-1

  • m/epsilon

Explicación

Pregunta 29 de 51

1

Die Grundform des Mastertheorem 1 ist:

Selecciona una de las siguientes respuestas posibles:

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

Explicación

Pregunta 30 de 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).

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 31 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 32 de 51

1

Der CYK-Algorithmus läuft in:

Selecciona una de las siguientes respuestas posibles:

  • O(n²)

  • O(n³)

  • O(n log(n))

Explicación

Pregunta 33 de 51

1

Welcher dieser Kuchenschneidalgorithmen ist nicht neidfrei?

Selecciona una de las siguientes respuestas posibles:

  • Moving-Knife-Algorithmus

  • Successive-Pairs-Algorithmus

  • Trimming-Algorithmus

Explicación

Pregunta 34 de 51

1

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

Selecciona una de las siguientes respuestas posibles:

  • g(c)<=g(cPhase)

  • g(c)>=g(cPhase)

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

Explicación

Pregunta 35 de 51

1

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

Selecciona una de las siguientes respuestas posibles:

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

Explicación

Pregunta 36 de 51

1

Kruskal hat eine Laufzeit von:

Selecciona una de las siguientes respuestas posibles:

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

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

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

Explicación

Pregunta 37 de 51

1

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

Selecciona una de las siguientes respuestas posibles:

  • O(n²2n)

  • O(n³)

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

Explicación

Pregunta 38 de 51

1

Valiants Algorithmus läuft in:

Selecciona una de las siguientes respuestas posibles:

  • O(n^log7)

  • O(n^1,93)

  • O(n³)

Explicación

Pregunta 39 de 51

1

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

Selecciona una de las siguientes respuestas posibles:

  • n²

  • natürlich der selben Zeit, n³

  • da er nur auf einer Adjazenzmatrix arbeitet in n

Explicación

Pregunta 40 de 51

1

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

Selecciona una de las siguientes respuestas posibles:

  • Zwei Endzustände

  • Ein normaler Zustand, ein Endzustand

  • Ein Startzustand und ein Endzustand

Explicación

Pregunta 41 de 51

1

Negative Kanten sind bei Dijkstra nicht erlaubt?

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 42 de 51

1

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

Selecciona una de las siguientes respuestas posibles:

  • n log(n) Vergleiche

  • 2n log(n) Vergleiche

  • n log log(n) Vergleiche

Explicación

Pregunta 43 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 44 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 45 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 46 de 51

1

Welche Laufzeit hat der Karger-Stein Algorithmus?

Selecciona una de las siguientes respuestas posibles:

  • O(n² log n)

  • O(n²)

  • O(n logn)

Explicación

Pregunta 47 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 48 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 49 de 51

1

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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 50 de 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

Selecciona uno de los siguientes:

  • VERDADERO
  • FALSO

Explicación

Pregunta 51 de 51

1

Prims Algorithmus benötigt:

Selecciona una de las siguientes respuestas posibles:

  • O(n²)

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

  • O(n logn)

Explicación

Anterior
Revisar respuesta
Siguiente