Quiz
AuD ( Fragen 1 - 20 )
Create a free account to finish this quiz
Save your progress and see your final score.
Already have an account? Sign in
Questions in this quiz (20)
1Die Suche nach einem Element in der Datenstruktur Keller/Stapel hat bei n Elementen
den Aufwand O(n).- ATrue
- BFalse
2Welche der folgenden Sortieralgorithmen haben für das Sortieren einer Reihung von n Zahlen im schlechtesten Fall einen Aufwand von O(n^2)?
- ASortieren durch Mischen (Mergesort)
- BSortieren durch Zerlegen (Quicksort)
- CCounting Sort
- DRadix-Sortierung
3Um n Elemente zu sortieren, braucht das Sortieren durch Zerlegen (Quicksort) zusätzlichen Speicherplatz in der Größenordnung von O(log n).
- ATrue
- BFalse
4Die Haldensortierung (Heapsort) hat einen niedrigeren Speicherplatzbedarf als das Sortieren durch Mischen (Mergesort).
- ATrue
- BFalse
5Betrachten Sie eine Streutabelle der Länge n, bei der Konflikte durch quadratisches Sondieren aufgelöst werden.
- ADer Aufwand zum Löschen eines Elements ist in O(log n).
- BWird ein Wert gelöscht und anschließend wieder eingefügt, landet er im selben Feld der Streutabelle.
- CSekundärkollisionen können auftreten.
6Grahams 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.
- ATrue
- BFalse
7Seien f(n) ∈ O(r(n)) und g(n) ∈ O(s(n)), c > 0 konstant. Es gilt:
- Af(n) + g(n) ∈ O(r(n) + s(n))
- Bf(n) − g(n) ∈ O(r(n) − s(n))
- Cf(n) + c ∈ O(r(n))
8Im O-Kalkül verwendet man folgende Definiton:
- AO(f(n)) = {g(n)|∃c > 0 ∃n_0 > 0 ∀n ≥ n_0 : 0 ≤ g(n) ≤ c · f(n)}
- BO(f(n)) = {g(n)|∃c > 0 ∃n_0 > 0 ∀n ≥ n_0 : 0 ≤ c · f(n) ≤ g(n)}
9Für den Nachweis der totalen Korrektheit mittels wp-Kalkül erlaubt die Betrachtung der Invarianten das Weglassen des Terminierungsbeweises.
- ATrue
- BFalse
10Welche der folgenden Zuweisungen können jeweils fehlerfrei übersetzt werden (a, aa und b seien die Variablen auf dem Bild)?
- AI v1=a;
- BI v2=aa;
- CI v3= (AA)aa;
- DI v4=b;
- EA v5=aa;
- FAA v6=a;
- GB v7=new I();
- HB v8= (B) (aa);
11Gegeben 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.
- ADie Hashfunktion ist für die verwendete Zahlenfolge schlecht.
- BDie Suche nach einem Eintrag in einer Hashtabelle mit n Elementen dauert im schlechtesten Fall O(n) (kleinste obere Schranke im O-Kalkül)
- CLöst man Kollisionen durch Open Addressing, so kann man Elemente aus der Hash Tabelle ohne weiteres löschen.
- DIn einer Hashtabelle, die Kollisionen mit Hilfe einer verketteten Liste auflöst, können (ausreichend Arbeitsspeicher vorausgesetzt) beliebig viele Elemente gespeichert werden
- E(4x + 2)%10 ist für die Zahlenfolge eine gute Hashfunktion
12Die oben stehende Abbildung zeigt eine stark vereinfachte Straßenkarte Europas. Geben Sie an, ob die folgenden Aussagen zutreffend sind
- ADer Graph ist stark zusammenhängend.
- BDer Graph kann mit Hilfe einer Tiefensuche vollständig traversiert werden.
- CKnoten G ist von Grad drei.
- DDer Graph ist ein DAG.
13Gegeben ist der beschrifteten Teil der Straßenkarte.
- AFührt man den Algorithmus von Dijkstra von E aus durch, so erhält man denselben Spannbaum wie von J aus.
- BFührt man den Algorithmus von Dijkstra von K aus durch, so erhält man denselben Spannbaum wie von H aus.
- CDer resultierende Spannbaum [mit Dijkstra] entspricht immer dem minimalen Spannbaum.
14Fü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?
- Ay = 2^x
- By = 2^(x+1−i) − 1
- Ci= i -1
15 Geben Sie an, welche der folgende Aussagen richtig sind.
- AO( f(n)) = {g(n)|∃c > 0 : ∃n_0 > 0 : ∀n > n_0 : g(n) < c*f(n)}
- BO(n^2) = O(n^2 − 1)
16Um 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.
- ATrue
- BFalse
17Mit Hilfe einer Invariante kann man im wp-Kalkül nachweisen, dass . . .
- Aeine Methode terminiert
- Beine Schleife terminiert.
- Ceine Schleife korrekt ist.
18Eine Streutabelle, die Kollisionen mit Hilfe einer verketteten Liste auflöst, kann (ausreichend Arbeitsspeicher vorausgesetzt) beliebig viele Elemente speichern.
- ATrue
- BFalse
19Kreuzen Sie das/die stabile(n) Sortierverfahren an.
- AFächersortierung (Bucketsort)
- BHaldensortierung (Heapsort)
- CSortieren durch Mischen (Mergesort)
- DSortieren durch Zerlegen (Quicksort)
20Ein minimaler Spannbaum eines zusammenhängenden Graphen mit n Knoten enthält
- Aexakt n − 1 Kanten.
- Bmindestens n Kanten.
- Cexakt n + 1 Kanten.
Information
- Description
- ATTENTION: There might be errors in the question. I interpretet some questions differently and doupted the FSI solutions. Turned out the FSI solutions are more right, thus please comment the solution from fsi if it divergents. MC-Fragen und angepasste Aufgabenstellungen aus Altklausuren (FSI-Forum).
- Author
- Daniele P.
- Language
- Deutsch
- Views
- 74
- Tags
- Rating
- No ratings yet Rate this quiz