Copy and Edit

Multiple Choice Fragen

Description

Fragen eines Algorithmikmoduls auf Masterniveau
Tobias Ranke
Quiz by Tobias Ranke, updated more than 1 year ago
Tobias Ranke
Created by Tobias Ranke over 8 years ago
175
0
0

Resource summary

Question 1

Question
Dijkstras Algorithmus folgt dem Entwurfsprinzip "Divide and Conquer".
Answer
  • True
  • False

Question 2

Question
Ein Fibunacci-Heap mit n Knoten hat maximale Höhe O(log n)?
Answer
  • True
  • False

Question 3

Question
Optimale Suchbäume lassen sich in quadratischer Zeit berechnen.
Answer
  • True
  • False

Question 4

Question
Der Median einer Menge ganzer Zahlen kann gleich ihrem Maximum sein.
Answer
  • True
  • False

Question 5

Question
Bubblesort benötigt auf allen Eingaben mehr Vergleiche als Heapsort.
Answer
  • True
  • False

Question 6

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

Question 7

Question
Der in der Vorlesung behandelte Algorithmus von Stoer und Wagner berechnet einen minimalen Schnitt eines Graphen.
Answer
  • True
  • False

Question 8

Question
Quickselect benötigt im Durchschnitt nicht mehr als 4n Vergleiche auf einem Feld mit n Elementen.
Answer
  • True
  • False

Question 9

Question
Ein Fibunacci-Heap mit n Knoten kann eine Höhe von n erreichen.
Answer
  • True
  • False

Question 10

Question
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)
Answer
  • True
  • False

Question 11

Question
Prims Algorithmus zur Berechnung eines minimalen Spannbaumes folgt dem Entwurfsprinzip "Union-Find"
Answer
  • True
  • False

Question 12

Question
Bubblesort benötigt auf allen Eingaben mehr Vergleiche als Heapsort.
Answer
  • True
  • False

Question 13

Question
Der Algorithmus von Schönhage und Strassen zur schnellen Multiplikation ganzer Zahlen verwendet die schnelle Fouriertransformation.
Answer
  • True
  • False

Question 14

Question
Quickselect benötigt im Mittel mehr als 15n Vergleiche.
Answer
  • True
  • False

Question 15

Question
Es ist kein Algorithmus zur Berechnung optimaler Suchbäume in subkubischer Zeit bekannt.
Answer
  • True
  • False

Question 16

Question
Mergesort benötigt durchschnittlich Theta von (n log n)
Answer
  • True
  • False

Question 17

Question
Wie lautet die Laufzeit von Kruskal?
Answer
  • O(|E|+log |V|)
  • O(|V|+ log log |V|+|E|)

Question 18

Question
Quickselect benötigt O(n²) wenn...
Answer
  • ...das Pivotelement in der Mitte steht.
  • ...das Pivotelement am Ende steht.

Question 19

Question
Die Formel, welche das Dynamische Programm zur Berechnung der optimalen Anzahl an Multiplikationen zur Multiplikation mehrerer Matrizen anwendet lautet:
Answer
  • 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)

Question 20

Question
Die zentrale Operation von Prim ist Union-Find?
Answer
  • True
  • False

Question 21

Question
Eine Hashfamilie heißt universell, wenn gilt:
Answer
  • Hashtafelgröße ist kubisch.
  • Wahrscheinlichkeit (h(x)=h(y))<= 1/m
  • Wahrscheinlichkeit (h(x)=h(y))>= 1/n

Question 22

Question
Damit die Wahrscheinlichkeit , dass eine Hashfunktion h injektiv ist, größer gleich 1/2 ist, muss folgendes gegeben sein:
Answer
  • m=n²
  • m=n³
  • m = n mod |U|

Question 23

Question
Warshalls Algorithmus berechnet im Gegensatz zu Floyds Algorithmus:
Answer
  • die transitive Hülle
  • kürzeste Wege
  • das selbe

Question 24

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

Question 25

Question
Dynamische Programme liegen in der Komplexitätsklasse
Answer
  • Polynomiell
  • Pseudopolynomiell
  • Exponentiell

Question 26

Question
Bei Fibonacci-Heaps haben Merge, Insert, delete_min sowie decrease_key die Laufzeit:
Answer
  • 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)

Question 27

Question
Im Vergleich zur naiven Multiplikation von O(n³) benötigt die Matrizenmultiplikation von Volker Strassen:
Answer
  • O(n^2,81)
  • O(n^2,83)
  • O(nlog(n))
  • O(n)

Question 28

Question
Wie viele Übergangskanten hat der Endliche Automat des KMP Algorithmus
Answer
  • 2(m + 2)
  • m²-1
  • m/epsilon

Question 29

Question
Die Grundform des Mastertheorem 1 ist:
Answer
  • 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.

Question 30

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

Question 31

Question
Der in der Vorlesung behandelte Algorithmus von Stoer und Wagner berechnet einen minimalen Schnitt eines Graphen.
Answer
  • True
  • False

Question 32

Question
Der CYK-Algorithmus läuft in:
Answer
  • O(n²)
  • O(n³)
  • O(n log(n))

Question 33

Question
Welcher dieser Kuchenschneidalgorithmen ist nicht neidfrei?
Answer
  • Moving-Knife-Algorithmus
  • Successive-Pairs-Algorithmus
  • Trimming-Algorithmus

Question 34

Question
Welche dieser Aussagen über den Stör-Wagner-Algorithmus ist zutreffend?
Answer
  • g(c)<=g(cPhase)
  • g(c)>=g(cPhase)
  • g(c)<=G(cPhase+1)

Question 35

Question
Diese Frage bezieht sich auf Fibonacci Heaps: Verliert ein Knoten mehr als ein Kind, dann...
Answer
  • 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.

Question 36

Question
Kruskal hat eine Laufzeit von:
Answer
  • O(|E|*log|V|)
  • O(|V|*log|E|)
  • O(|V|²+|E|)

Question 37

Question
Das Rucksackproblem lässt sich durch Branch and Bound in:
Answer
  • O(n²2n)
  • O(n³)
  • O(n log(n)* n²)

Question 38

Question
Valiants Algorithmus läuft in:
Answer
  • O(n^log7)
  • O(n^1,93)
  • O(n³)

Question 39

Question
Warshalls Algorithmus läuft im Gegensatz zu Floyds Algorithmus in:
Answer
  • n²
  • natürlich der selben Zeit, n³
  • da er nur auf einer Adjazenzmatrix arbeitet in n

Question 40

Question
Was ist die Abbruchbedingung für den Äquivalenztest Endlicher Automaten?
Answer
  • Zwei Endzustände
  • Ein normaler Zustand, ein Endzustand
  • Ein Startzustand und ein Endzustand

Question 41

Question
Negative Kanten sind bei Dijkstra nicht erlaubt?
Answer
  • True
  • False

Question 42

Question
Bottom-up Heapsort benötigt im Vergleich zu Standardheapsort nur:
Answer
  • n log(n) Vergleiche
  • 2n log(n) Vergleiche
  • n log log(n) Vergleiche

Question 43

Question
Die Laufzeit des Äquivalenztests endlicher Automaten beträgt O(n2)
Answer
  • True
  • False

Question 44

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

Question 45

Question
Der Algorithmus von Matiyasevich, Knuth, Morris und Pratt testet endliche Automaten auf Aquivalenz.
Answer
  • True
  • False

Question 46

Question
Welche Laufzeit hat der Karger-Stein Algorithmus?
Answer
  • O(n² log n)
  • O(n²)
  • O(n logn)

Question 47

Question
Bei Heapsort werden immer mehr als die Halfte der Vergleiche waehrend des Heapaufbaus ausgefuhrt.
Answer
  • True
  • False

Question 48

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

Question 49

Question
Bei Union-Find mit Pfadverkürzung sind die Kosten O(n*inverseAckermannfkt(n))?
Answer
  • True
  • False

Question 50

Question
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
Answer
  • True
  • False

Question 51

Question
Prims Algorithmus benötigt:
Answer
  • O(n²)
  • O(|E|+|V|²)
  • O(n logn)
Show full summary Hide full summary

Want to create your own Quizzes for free with GoConqr? Learn more.

Similar

ein kleines Informatik Quiz
AntonS
Wirtschaftsinformatik Teil 2
Sabrina Heckler
Informatik
Tom Kühling
Information Technology
Ausizio Talan
PHP Grundlagen
chrisi.0605
Informatik 1 - Einführung
Svenja
Codierung
Tom Kühling
Wirtschaftsinformatik Teil 1
Sabrina Heckler
Quantitative Forschungsmethoden
heidi.depner
Einführung in das Studium Informatik
Daniel Doe
Wissenschaftstheoretische Grundlagen Prüfung Übung
Sophie Ladewig
Browse Library