AuD ( Fragen 1 - 20 )

Question 1

Question

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

Answer

True
False

Question 2

Question

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

Answer

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

Question 3

Question

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

Answer

True
False

Question 4

Question

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

Answer

True
False

Question 5

Question

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

Answer

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.

Question 6

Question

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.

Answer

True
False

Question 7

Question

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

Answer

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

Question 8

Question

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

Answer

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

Question 9

Question

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

Answer

True
False

Question 10

Question

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

Image:

b67e4a54-901c-4e93-ac37-e32490b95bee (image/png)

Answer

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

Question 11

Question

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.

Image:

49944aa3-6695-4821-8599-b920b935d9aa (image/png)

Answer

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

Question 12

Question

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

Image:

1d0b0e0d-bf5b-4a8a-8d75-cc08e60ffbed (image/png)

Answer

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.

Question 13

Question

Gegeben ist der beschrifteten Teil der Straßenkarte.

Image:

422a28c6-6a3e-41db-aca2-424d8bccef59 (image/png)

Answer

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.

Question 14

Question

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?

Image:

e4fe6366-170c-4fb2-ae97-31970f29483a (image/png)

Answer

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

Question 15

Question

Geben Sie an, welche der folgende Aussagen richtig sind.

Answer

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)

Question 16

Question

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.

Answer

True
False

Question 17

Question

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

Answer

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

Question 18

Question

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

Answer

True
False

Question 19

Question

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

Answer

Fächersortierung (Bucketsort)
Haldensortierung (Heapsort)
Sortieren durch Mischen (Mergesort)
Sortieren durch Zerlegen (Quicksort)

Question 20

Question

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

Answer

exakt n − 1 Kanten.
mindestens n Kanten.
exakt n + 1 Kanten.

Next up

AuD ( Fragen 1 - 20 )

Description

Resource summary

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Question 11

Question 12

Question 13

Question 14

Question 15

Question 16

Question 17

Question 18

Question 19

Question 20

Similar

	Created by Daniele P. about 8 years ago