AuD ( Fragen 1 - 20 )

Questão 1 de 20

1

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

Selecione uma das opções:

VERDADEIRO
FALSO

Explicação

Questão 2 de 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)?

Selecione uma das seguintes:

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

Explicação

Questão 3 de 20

1

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

Selecione uma das opções:

VERDADEIRO
FALSO

Explicação

Questão 4 de 20

1

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

Selecione uma das opções:

VERDADEIRO
FALSO

Explicação

Questão 5 de 20

1

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

Selecione uma das seguintes:

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.

Explicação

Questão 6 de 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.

Selecione uma das opções:

VERDADEIRO
FALSO

Explicação

Questão 7 de 20

1

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

Selecione uma ou mais das seguintes:

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

Explicação

Questão 8 de 20

1

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

Selecione uma ou mais das seguintes:

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

Explicação

Questão 9 de 20

1

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

Selecione uma das opções:

VERDADEIRO
FALSO

Explicação

Questão 10 de 20

1

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

Selecione uma ou mais das seguintes:

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

Explicação

Questão 11 de 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.

Selecione uma ou mais das seguintes:

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

Explicação

Questão 12 de 20

1

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

Selecione uma ou mais das seguintes:

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.

Explicação

Questão 13 de 20

1

Gegeben ist der beschrifteten Teil der Straßenkarte.

Selecione uma ou mais das seguintes:

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.

Explicação

Questão 14 de 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?

Selecione uma ou mais das seguintes:

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

Explicação

Questão 15 de 20

1

Geben Sie an, welche der folgende Aussagen richtig sind.

Selecione uma ou mais das seguintes:

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)

Explicação

Questão 16 de 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.

Selecione uma das opções:

VERDADEIRO
FALSO

Explicação

Questão 17 de 20

1

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

Selecione uma ou mais das seguintes:

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

Explicação

Questão 18 de 20

1

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

	Criado por Daniele P. mais de 7 anos atrás

AuD ( Fragen 1 - 20 )

Questão 1 de 20

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

Selecione uma das opções:

Explicação

Questão 2 de 20

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

Selecione uma das seguintes:

Explicação

Questão 3 de 20

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

Selecione uma das opções:

Explicação

Questão 4 de 20

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

Selecione uma das opções:

Explicação

Questão 5 de 20

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

Selecione uma das seguintes:

Explicação

Questão 6 de 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.

Selecione uma das opções:

Explicação

Questão 7 de 20

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

Selecione uma ou mais das seguintes:

Explicação

Questão 8 de 20

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

Selecione uma ou mais das seguintes:

Explicação

Questão 9 de 20

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

Selecione uma das opções:

Explicação

Questão 10 de 20

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

Selecione uma ou mais das seguintes:

Explicação

Questão 11 de 20

Selecione uma ou mais das seguintes:

Explicação

Questão 12 de 20

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

Selecione uma ou mais das seguintes:

Explicação

Questão 13 de 20

Gegeben ist der beschrifteten Teil der Straßenkarte.

Selecione uma ou mais das seguintes:

Explicação

Questão 14 de 20

Selecione uma ou mais das seguintes:

Explicação

Questão 15 de 20

Geben Sie an, welche der folgende Aussagen richtig sind.

Selecione uma ou mais das seguintes:

Explicação

Questão 16 de 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.

Selecione uma das opções:

Explicação

Questão 17 de 20

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

Selecione uma ou mais das seguintes:

Explicação

Questão 18 de 20

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

Selecione uma das opções:

Explicação

Questão 19 de 20

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

Selecione uma ou mais das seguintes:

Explicação

Questão 20 de 20

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

Selecione uma ou mais das seguintes:

Explicação

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