AuD ( Fragen 1 - 20 )

Pregunta 1 de 20

1

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

Selecciona uno de los siguientes:

VERDADERO
FALSO

Explicación

Pregunta 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)?

Selecciona una de las siguientes respuestas posibles:

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

Explicación

Pregunta 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).

Selecciona uno de los siguientes:

VERDADERO
FALSO

Explicación

Pregunta 4 de 20

1

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

Selecciona uno de los siguientes:

VERDADERO
FALSO

Explicación

Pregunta 5 de 20

1

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

Selecciona una de las siguientes respuestas posibles:

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.

Explicación

Pregunta 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.

Selecciona uno de los siguientes:

VERDADERO
FALSO

Explicación

Pregunta 7 de 20

1

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

Selecciona una o más de las siguientes respuestas posibles:

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

Explicación

Pregunta 8 de 20

1

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

Selecciona una o más de las siguientes respuestas posibles:

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

Explicación

Pregunta 9 de 20

1

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

Selecciona uno de los siguientes:

VERDADERO
FALSO

Explicación

Pregunta 10 de 20

1

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

Selecciona una o más de las siguientes respuestas posibles:

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

Explicación

Pregunta 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.

Selecciona una o más de las siguientes respuestas posibles:

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

Explicación

Pregunta 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

Selecciona una o más de las siguientes respuestas posibles:

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.

Explicación

Pregunta 13 de 20

1

Gegeben ist der beschrifteten Teil der Straßenkarte.

Selecciona una o más de las siguientes respuestas posibles:

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.

Explicación

Pregunta 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?

Selecciona una o más de las siguientes respuestas posibles:

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

Explicación

Pregunta 15 de 20

1

Geben Sie an, welche der folgende Aussagen richtig sind.

Selecciona una o más de las siguientes respuestas posibles:

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)

Explicación

Pregunta 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.

Selecciona uno de los siguientes:

VERDADERO
FALSO

Explicación

Pregunta 17 de 20

1

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

Selecciona una o más de las siguientes respuestas posibles:

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

Explicación

Pregunta 18 de 20

1

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

	Creado por Daniele P. hace más de 7 años

AuD ( Fragen 1 - 20 )

Pregunta 1 de 20

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

Selecciona uno de los siguientes:

Explicación

Pregunta 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)?

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 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).

Selecciona uno de los siguientes:

Explicación

Pregunta 4 de 20

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

Selecciona uno de los siguientes:

Explicación

Pregunta 5 de 20

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

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 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.

Selecciona uno de los siguientes:

Explicación

Pregunta 7 de 20

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

Selecciona una o más de las siguientes respuestas posibles:

Explicación

Pregunta 8 de 20

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

Selecciona una o más de las siguientes respuestas posibles:

Explicación

Pregunta 9 de 20

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

Selecciona uno de los siguientes:

Explicación

Pregunta 10 de 20

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

Selecciona una o más de las siguientes respuestas posibles:

Explicación

Pregunta 11 de 20

Selecciona una o más de las siguientes respuestas posibles:

Explicación

Pregunta 12 de 20

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

Selecciona una o más de las siguientes respuestas posibles:

Explicación

Pregunta 13 de 20

Gegeben ist der beschrifteten Teil der Straßenkarte.

Selecciona una o más de las siguientes respuestas posibles:

Explicación

Pregunta 14 de 20

Selecciona una o más de las siguientes respuestas posibles:

Explicación

Pregunta 15 de 20

Geben Sie an, welche der folgende Aussagen richtig sind.

Selecciona una o más de las siguientes respuestas posibles:

Explicación

Pregunta 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.

Selecciona uno de los siguientes:

Explicación

Pregunta 17 de 20

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

Selecciona una o más de las siguientes respuestas posibles:

Explicación

Pregunta 18 de 20

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

Selecciona uno de los siguientes:

Explicación

Pregunta 19 de 20

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

Selecciona una o más de las siguientes respuestas posibles:

Explicación

Pregunta 20 de 20

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

Selecciona una o más de las siguientes respuestas posibles:

Explicación

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