Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen, bei Fragen bitte: (Übersicht)
Dies ist eine alte Version des Dokuments!
Inhaltsverzeichnis
Forendiskussionen, bei Fragen bitte:
- Allgemeiner Thread: https://fsi.cs.fau.de/forum/post/160770;nocount
- Aufgabe 1 (Wissensfragen): https://fsi.cs.fau.de/forum/post/160771;nocount
- Aufgabe 2 (Dynamische Programmierung):https://fsi.cs.fau.de/forum/post/160772;nocount
Lösungsversuch WS 18/19
Aufgabe 1 (Wissensfragen)
a)
- Richtig, es werden nur die drei Variablen
xMax
,xSuf
sowiei
zusätzlich angelegt. - Falsch, sie liegt in
x.length
. - Falsch, es werden zusätzlich die Arrays
r
undrn
angelegt, die in jeder Schleiteniteration ungefähr doppelt so groß gewählt ist - Richtig. Das sich aber zu überlegen, ist aber nicht ganz so einfach. Der Graycode erstellt eine Sortierung aller Binärwörter der Länge n (also insgesamt 2^n Wörter), sodass die Hamming-Distanz zweier aufeinanderfolgender Wörter genau 1 ist. Der eigentliche Algorithmus beginnt dabei beim Trivialfall n = 1. Alle anderen Fälle n werden aufgebaut, indem der Fall n - 1 verwendet wird. Die Laufzeit ist also ungefähr 2^1 + 2^2 + … 2^n = 2^(n + 1) - 1. Nicht berücksichtigt in dieser Überlegung ist u. a., dass das Feld
rn
in jedem Schritt um eine weitere Reihex
ergänzt wird. Ansonsten kann man auch durch die Betrachtung des Quellcodes auf ähnliche Ergebnisse kommen.
Anmerkung zum O-Kalkül: Grundsätzlich beschreibt das O-Kalkül immer eine obere Schranke, wenn z. B. eine Funktion f(n) in O(n) liegt, liegt sie auch in O(n^2), aber nicht unbedingt in O(1) (vgl. dazu auch Lösungsvorschlag der Miniklausur dieses Semesters).
b)
- Falsch,
CatRoom
ist Unterklasse vonCatBase
- Richtig.
- Falsch, es ist nur ein einfaches Feld. Bei der Notation muss man allgemein wissen, dass Felder immer an der gegenüberliegenden Seite der Beziehung notiert werden.
- Richtig, zu jedem
CatRoom
gibt es maximal einCatHouse
, also wird jederCatRoom
von höchsten einemCatHouse
referenziert (in KonzMod-Logik würde also insbesondere die funktionale AbhängigkeitCatRoom
→CatHouse
gelten).
c)
- Richtig. Das ist ein bisschen gemein, da in der Aufgabenstellung einfach die Variabeln n und c vertauscht wurden. Trotzdem ist die Aussage korrekt ist, auch wenn die eigentliche Intention dieser Variablen nicht mehr erfüllt ist.
- Richtig, das Omega-Kalkül beschreibt alle Funktionen, die mindestens so schnell wachsen wie eine gegebene Funktion.
- Falsch, n liegt in O(n^2), n^2 aber nicht in O(n).
- Falsch, liege f(n) = n^2 in O(n), und g(n) = n in O(n^2), dann liegt f(n) - g(n) = n^2 - n nicht in O(n).
d)
- Richtig, man kann von jedem Knoten aus jeden anderen erreichen.
- Falsch, der Graph enthält Zyklen, z.B. v0>v1>v3>v0
- Falsch, die Tiefensuche müsste nach dem Besuchen von Knoten v1 den Knoten v3 besuchen.
- Richtig, man muss hier halt wissen, wie die Adjazenzfelddarstellung aussieht.
e)
- Richtig, genau das tut der Algorithmus von Floyd.
- Falsch, ein Spannbaum für einen Graphen mit n Knoten hat immer genau n - 1 Kanten.
- Richtig, der Algorithmus von Krukal beginnt mit einem „leeren“ Spannbaum und fügt in jedem Schritt eine Kante hinzu.
- Falsch, die Laufzeit liegt in O(|V| log|V|).
f)
- Falsch, der
finally
-Block wird immer ausgeführt. - Richtig.
- Richtig. Wenn
a
undb
erfüllt ist, wird der CodeX
ausgeführt, ista
wahr undb
falsch, wird der CodeY
ausgeführt, ansonsten, also wenna
nicht erfüllt ist, muss die BedingungQ
ohne Änderung erfüllt sein. - Falsch. wp(„A“, Q) bezeichnet die schwächste Vor-Bedingung, die gelten muss, damit nach der Ausführung von „A“ Q erfüllt ist. Eine Bedingung P müsste mindestens so stark wie wp(„A“, Q) sein, d. h. man müsste P ⇒ wp(„A“, Q) zeigen.
Aufgabe 2 (Dynamische Programmierung)
a)
b)
public static int maxPathDP(int[][] a) { int n = a.length; int best = 0; //Feld initialisieren und letzte Spalte befüllen int[][] mem = new int[n][n]; for(int row = n-1; row >=0; row--) { mem[row][n-1] = a[row][n-1]; } int b = 0; //von der vorletzten Spalte bis zur vordersten for(int col = n-2; col >= 0; col--) { //Suche den Grössten Nachbarn in der rechten Spalte in einer Reihe //darüber, darunter oder gleicher Reihe und speichere dessen Wert in b for(int row = n-1; row >= 0; row--) { if (row == 0) { b = Math.max(mem[row][col+1], mem[row+1][col+1]); } else if(row == n-1) { b = Math.max(mem[row][col+1], mem[row-1][col+1]); } else { for(int r = row-1; r <= row+1; r++) { b = Math.max(mem[r][col+1], b); } } //Der neue Wert in mem ist der alte in a plus b mem[row][col] = a[row][col] + b; } } //Suche das Maximum in der ersten Spalte for( int i = 0; i < mem.length; i++) { if(mem[i][0] > best) { best = mem[i][0]; } } return best; }
Aufgabe 3 (Streuspeicherung)
a)
Fach | k (verkettete Liste, zuletzt eingetragener Schlüssel rechts) |
---|---|
0 | E ⇒ K |
1 | |
2 | ? ⇒ |
3 | |
4 | Y ⇒ ! ⇒ A |
5 | B ⇒ |
6 | |
7 | D ⇒ |
b)
k | sondierte Fächer und Art der Kollision |
---|---|
B | 5 |
Y | 4 |
E | 0 |
! | 4 (P)⇒ 5 (P)⇒ 6 |
A | 4 (P)⇒ 5 (P)⇒ 6 (S)⇒ 7 |
U | 0 (P)⇒ 1 |
D | 7 (S)⇒ 0 (P)⇒ 1 (S)⇒ 2 |
? | 2 (S)⇒ 3 |
c)
Fach | k | Streufunktion (i) |
---|---|---|
0 | E | 0 |
1 | A | 1 |
2 | U | 1 |
3 | ! | 1 |
4 | Y | 0 |
5 | B | 0 |
6 | ? | 2 |
7 | D | 0 |
Aufgabe 4 (Artikulationspunkte)
Aufgabe 5 (Abstrakte Datentypen)
a)
push4(ts, x, y) = Push(Push(Push(Push(ts, x+1, y ), x, y+1), x-1, y ), x, y-1 )
b)
paintHLine(c, x, y, n, nc) = To-Do
c)
getCol(New,x,y) = White getCol(Paint(c, a, b, col), x, y) = To-Do
d)
floodH(c,Empty,oc,nc) = c oc = FoldC, nc = FnewC, FoldC ̸= FnewC floodH(c,Push(ts,x,y),oc,nc) =To-Do