AuD ( Fragen 1 - 20 )

Question 1 of 20

1

Die Suche nach einem Element in der Datenstruktur Keller/Stapel hat bei n Elementen
den Aufwand O(n).

Select one of the following:

True
False

Explanation

Question 2 of 20

1

Welche der folgenden Sortieralgorithmen haben für das Sortieren einer Reihung von n Zahlen im schlechtesten Fall einen Aufwand von O(n^2)?

Select one of the following:

Sortieren durch Mischen (Mergesort)
Sortieren durch Zerlegen (Quicksort)
Counting Sort
Radix-Sortierung

Explanation

Question 3 of 20

1

Um n Elemente zu sortieren, braucht das Sortieren durch Zerlegen (Quicksort) zusätzlichen Speicherplatz in der Größenordnung von O(log n).

Select one of the following:

True
False

Explanation

Question 4 of 20

1

Die Haldensortierung (Heapsort) hat einen niedrigeren Speicherplatzbedarf als das Sortieren durch Mischen (Mergesort).

Select one of the following:

True
False

Explanation

Question 5 of 20

1

Betrachten Sie eine Streutabelle der Länge n, bei der Konﬂikte durch quadratisches Sondieren aufgelöst werden.

Select one of the following:

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.

Explanation

Question 6 of 20

1

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.

Select one of the following:

True
False

Explanation

Question 7 of 20

1

Seien f(n) ∈ O(r(n)) und g(n) ∈ O(s(n)), c > 0 konstant. Es gilt:

Select one or more of the following:

f(n) + g(n) ∈ O(r(n) + s(n))
f(n) − g(n) ∈ O(r(n) − s(n))
f(n) + c ∈ O(r(n))

Explanation

Question 8 of 20

1

Im O-Kalkül verwendet man folgende Deﬁniton:

Select one or more of the following:

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

Explanation

Question 9 of 20

1

Für den Nachweis der totalen Korrektheit mittels wp-Kalkül erlaubt die Betrachtung der Invarianten das Weglassen des Terminierungsbeweises.

Select one of the following:

True
False

Explanation

Question 10 of 20

1

Welche der folgenden Zuweisungen können jeweils fehlerfrei übersetzt werden (a, aa und b seien die Variablen auf dem Bild)?

Select one or more of the following:

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

Explanation

Question 11 of 20

1

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 zutreﬀend sind.

Select one or more of the following:

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 auﬂöst, können (ausreichend Arbeitsspeicher vorausgesetzt) beliebig viele Elemente gespeichert werden
(4x + 2)%10 ist für die Zahlenfolge eine gute Hashfunktion

Explanation

Question 12 of 20

1

Die oben stehende Abbildung zeigt eine stark vereinfachte Straßenkarte Europas. Geben Sie an, ob die folgenden Aussagen zutreﬀend sind

Select one or more of the following:

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.

Explanation

Question 13 of 20

1

Gegeben ist der beschrifteten Teil der Straßenkarte.

Select one or more of the following:

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.

Explanation

Question 14 of 20

1

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?

Select one or more of the following:

y = 2^x
y = 2^(x+1−i) − 1
i= i -1

Explanation

Question 15 of 20

1

Geben Sie an, welche der folgende Aussagen richtig sind.

Select one or more of the following:

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)

Explanation

Question 16 of 20

1

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.

Select one of the following:

True
False

Explanation

Question 17 of 20

1

Mit Hilfe einer Invariante kann man im wp-Kalkül nachweisen, dass . . .

Select one or more of the following:

eine Methode terminiert
eine Schleife terminiert.
eine Schleife korrekt ist.

Explanation

Question 18 of 20

1

Eine Streutabelle, die Kollisionen mit Hilfe einer verketteten Liste auflöst, kann (ausreichend Arbeitsspeicher vorausgesetzt) beliebig viele Elemente speichern.

	Created by Daniele P. about 7 years ago

AuD ( Fragen 1 - 20 )

Question 1 of 20

Die Suche nach einem Element in der Datenstruktur Keller/Stapel hat bei n Elementen den Aufwand O(n).

Select one of the following:

Explanation

Question 2 of 20

Welche der folgenden Sortieralgorithmen haben für das Sortieren einer Reihung von n Zahlen im schlechtesten Fall einen Aufwand von O(n^2)?

Select one of the following:

Explanation

Question 3 of 20

Um n Elemente zu sortieren, braucht das Sortieren durch Zerlegen (Quicksort) zusätzlichen Speicherplatz in der Größenordnung von O(log n).

Select one of the following:

Explanation

Question 4 of 20

Die Haldensortierung (Heapsort) hat einen niedrigeren Speicherplatzbedarf als das Sortieren durch Mischen (Mergesort).

Select one of the following:

Explanation

Question 5 of 20

Betrachten Sie eine Streutabelle der Länge n, bei der Konﬂikte durch quadratisches Sondieren aufgelöst werden.

Select one of the following:

Explanation

Question 6 of 20

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.

Select one of the following:

Explanation

Question 7 of 20

Seien f(n) ∈ O(r(n)) und g(n) ∈ O(s(n)), c > 0 konstant. Es gilt:

Select one or more of the following:

Explanation

Question 8 of 20

Im O-Kalkül verwendet man folgende Deﬁniton:

Select one or more of the following:

Explanation

Question 9 of 20

Für den Nachweis der totalen Korrektheit mittels wp-Kalkül erlaubt die Betrachtung der Invarianten das Weglassen des Terminierungsbeweises.

Select one of the following:

Explanation

Question 10 of 20

Welche der folgenden Zuweisungen können jeweils fehlerfrei übersetzt werden (a, aa und b seien die Variablen auf dem Bild)?

Select one or more of the following:

Explanation

Question 11 of 20

Select one or more of the following:

Explanation

Question 12 of 20

Die oben stehende Abbildung zeigt eine stark vereinfachte Straßenkarte Europas. Geben Sie an, ob die folgenden Aussagen zutreﬀend sind

Select one or more of the following:

Explanation

Question 13 of 20

Gegeben ist der beschrifteten Teil der Straßenkarte.

Select one or more of the following:

Explanation

Question 14 of 20

Select one or more of the following:

Explanation

Question 15 of 20

Geben Sie an, welche der folgende Aussagen richtig sind.

Select one or more of the following:

Explanation

Question 16 of 20

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.

Select one of the following:

Explanation

Question 17 of 20

Mit Hilfe einer Invariante kann man im wp-Kalkül nachweisen, dass . . .

Select one or more of the following:

Explanation

Question 18 of 20

Eine Streutabelle, die Kollisionen mit Hilfe einer verketteten Liste auflöst, kann (ausreichend Arbeitsspeicher vorausgesetzt) beliebig viele Elemente speichern.

Select one of the following:

Explanation

Question 19 of 20

Kreuzen Sie das/die stabile(n) Sortierverfahren an.

Select one or more of the following:

Explanation

Question 20 of 20

Ein minimaler Spannbaum eines zusammenhängenden Graphen mit n Knoten enthält

Select one or more of the following:

Explanation

Die Suche nach einem Element in der Datenstruktur Keller/Stapel hat bei n Elementen
den Aufwand O(n).