7824605
Descrição
Quiz por Daniele P., atualizado more than 1 year ago
|
Criado por Daniele P.
mais de 7 anos atrás
|
|
Questão 1
Questão
Die Suche nach einem Element in der Datenstruktur Keller/Stapel hat bei n Elementen
den Aufwand O(n).
Responda
- True
- False
Questão 2
Questão
Welche der folgenden Sortieralgorithmen haben für das Sortieren einer Reihung von n Zahlen im schlechtesten Fall einen Aufwand von O(n^2)?
Responda
-
Sortieren durch Mischen (Mergesort)
-
Sortieren durch Zerlegen (Quicksort)
-
Counting Sort
-
Radix-Sortierung
Questão 3
Questão
Um n Elemente zu sortieren, braucht das Sortieren durch Zerlegen (Quicksort) zusätzlichen Speicherplatz in der Größenordnung von O(log n).
Responda
- True
- False
Questão 4
Questão
Die Haldensortierung (Heapsort) hat einen niedrigeren Speicherplatzbedarf als das Sortieren durch Mischen (Mergesort).
Responda
- True
- False
Questão 5
Questão
Betrachten Sie eine Streutabelle der Länge n, bei der Konflikte durch quadratisches Sondieren aufgelöst werden.
Responda
-
Der Aufwand zum Löschen eines Elements ist in O(log n).
-
Wird ein Wert gelöscht und anschließend wieder eingefügt, landet er im selben Feld der Streutabelle.
-
Sekundärkollisionen können auftreten.
Questão 6
Questão
Grahams Einpack-Algorithmus besteht aus einer Sortierphase mit Aufwand O(n·logn) und einer Knotendurchlaufphase. Diese hat den Aufwand O(n), weil beim Streichen von provisorisch in die Hülle eingefügten Knoten jedesmal höchstens ein Knoten gestrichen wird.
Responda
- True
- False
Questão 7
Questão
Seien f(n) ∈ O(r(n)) und g(n) ∈ O(s(n)), c > 0 konstant. Es gilt:
Responda
-
f(n) + g(n) ∈ O(r(n) + s(n))
-
f(n) − g(n) ∈ O(r(n) − s(n))
-
f(n) + c ∈ O(r(n))
Questão 8
Questão
Im O-Kalkül verwendet man folgende Definiton:
Responda
-
O(f(n)) = {g(n)|∃c > 0 ∃n_0 > 0 ∀n ≥ n_0 : 0 ≤ g(n) ≤ c · f(n)}
-
O(f(n)) = {g(n)|∃c > 0 ∃n_0 > 0 ∀n ≥ n_0 : 0 ≤ c · f(n) ≤ g(n)}
Questão 9
Questão
Für den Nachweis der totalen Korrektheit mittels wp-Kalkül erlaubt die Betrachtung der Invarianten das Weglassen des Terminierungsbeweises.
Responda
- True
- False
Questão 10
Questão
Welche der folgenden Zuweisungen können jeweils fehlerfrei übersetzt werden (a, aa und b seien die Variablen auf dem Bild)?
Responda
-
I v1=a;
-
I v2=aa;
-
I v3= (AA)aa;
-
I v4=b;
-
A v5=aa;
-
AA v6=a;
-
B v7=new I();
-
B v8= (B) (aa);
Questão 11
Questão
Gegeben ist die Hashfunktion h(x) = (3x + 2)%10 mit der abgebildeten Hashtabelle und der Zahlenfolge
7, 26, 27, 4, 47, 9, 6, 36, 17, 57, 56, 42, 10, 77, welche in eine Hashtabelle mit 0 bis 9 Buckets eingefügt werden soll. Dabei werden Konflikte über eine verkettete Liste gelöst.
Geben Sie an, welche der folgenden Aussagen zutreffend sind.
Responda
-
Die Hashfunktion ist für die verwendete Zahlenfolge schlecht.
-
Die Suche nach einem Eintrag in einer Hashtabelle mit n Elementen dauert im schlechtesten Fall O(n) (kleinste obere Schranke im O-Kalkül)
-
Löst man Kollisionen durch Open Addressing, so kann man Elemente aus der Hash Tabelle ohne weiteres löschen.
-
In einer Hashtabelle, die Kollisionen mit Hilfe einer verketteten Liste auflöst, können (ausreichend Arbeitsspeicher vorausgesetzt) beliebig viele Elemente gespeichert werden
-
(4x + 2)%10 ist für die Zahlenfolge eine gute Hashfunktion
Questão 12
Questão
Die oben stehende Abbildung zeigt eine stark vereinfachte Straßenkarte Europas. Geben Sie an, ob die folgenden Aussagen zutreffend sind
Responda
-
Der Graph ist stark zusammenhängend.
-
Der Graph kann mit Hilfe einer Tiefensuche vollständig traversiert werden.
-
Knoten G ist von Grad drei.
-
Der Graph ist ein DAG.
Questão 13
Questão
Gegeben ist der beschrifteten Teil der Straßenkarte.
Responda
-
Führt man den Algorithmus von Dijkstra von E aus durch, so erhält man denselben Spannbaum wie von J aus.
-
Führt man den Algorithmus von Dijkstra von K aus durch, so erhält man denselben Spannbaum wie von H aus.
-
Der resultierende Spannbaum [mit Dijkstra] entspricht immer dem minimalen Spannbaum.
Questão 14
Questão
Für eine Schleife der Form while b do A ist der logische Ausdruck I eine Schleifeninvariante,wenn gilt I ∧ b ⇒ wp(A, I). Dies ist insbesondere erfüllt, wenn wp(A, I) = I. Betrachten Sie nun den abgebildeten Programmcode (alle Variablen sind vom Typ int).
Welche der folgenden Ausdrücke ist eine Schleifeninvarianten der while-Schleife?
Responda
-
y = 2^x
-
y = 2^(x+1−i) − 1
-
i= i -1
Questão 15
Questão
Geben Sie an, welche der folgende Aussagen richtig sind.
Responda
-
O( f(n)) = {g(n)|∃c > 0 : ∃n_0 > 0 : ∀n > n_0 : g(n) < c*f(n)}
-
O(n^2) = O(n^2 − 1)
Questão 16
Questão
Um mittels binärer Suche auf einem Feld mit n Elementen einen maximalen Aufwand von O(log n) zu erhalten, muss das Feld die Haldeneigenschaft erfüllen.
Responda
- True
- False
Questão 17
Questão
Mit Hilfe einer Invariante kann man im wp-Kalkül nachweisen, dass . . .
Responda
-
eine Methode terminiert
-
eine Schleife terminiert.
-
eine Schleife korrekt ist.
Questão 18
Questão
Eine Streutabelle, die Kollisionen mit Hilfe einer verketteten Liste auflöst, kann (ausreichend Arbeitsspeicher vorausgesetzt) beliebig viele Elemente speichern.
Responda
- True
- False
Questão 19
Questão
Kreuzen Sie das/die stabile(n) Sortierverfahren an.
Responda
-
Fächersortierung (Bucketsort)
-
Haldensortierung (Heapsort)
-
Sortieren durch Mischen (Mergesort)
-
Sortieren durch Zerlegen (Quicksort)
Questão 20
Questão
Ein minimaler Spannbaum eines zusammenhängenden Graphen mit n Knoten enthält
Responda
-
exakt n − 1 Kanten.
-
mindestens n Kanten.
-
exakt n + 1 Kanten.
Quer criar seus próprios Quizzes gratuitos com a GoConqr? Saiba mais.