Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Aufgabe 1
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungws17 [05.04.2019 11:57] – SpeedyGonzalez | pruefungen:bachelor:aud:loesungws17 [05.08.2019 15:56] – TOKAMAK | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | **__Aufgabe1__** | + | ==== |
a) 1,3,4 //4 ist falsch, nicht die Argumentfolge, | a) 1,3,4 //4 ist falsch, nicht die Argumentfolge, | ||
b) 2,3 //4 ist wahr, mit dem Konzept des Ergebnisse durchreichen lässt sich eine iterative Methode mit Laufzeit O(n) und vier lokalen Variablen (also konstantem Speicherbedarf) schreiben // | b) 2,3 //4 ist wahr, mit dem Konzept des Ergebnisse durchreichen lässt sich eine iterative Methode mit Laufzeit O(n) und vier lokalen Variablen (also konstantem Speicherbedarf) schreiben // | ||
- | c) 2,4 Ist 2 nicht die Definition von groß-O? //Ja, 2 ist falsch, 3 ist wahr (das ist literally die Definition von Theta)// | + | c) 2,3,4 Ist 2 nicht die Definition von groß-O? //Ja, 2 ist falsch, 3 ist wahr (das ist literally die Definition von Theta)// |
d) 1,4 | d) 1,4 | ||
Zeile 11: | Zeile 10: | ||
e) 1,2 | e) 1,2 | ||
- | **__Aufgabe2__** | + | ==== |
a) | a) | ||
Zeile 24: | Zeile 23: | ||
- | **__Aufgabe3__** | + | ==== |
a) | a) | ||
Zeile 34: | Zeile 33: | ||
for(int i=0; | for(int i=0; | ||
b[i] = true; | b[i] = true; | ||
- | for (int x = i; x< | + | for (int x = i+1; x< |
- | b[x]=true; | + | b[x]=true; |
if(istGut(b)){ | if(istGut(b)){ | ||
- | z=z+1; | + | z++; |
} | } | ||
b[x]=false; | b[x]=false; | ||
Zeile 91: | Zeile 90: | ||
</ | </ | ||
Evtl noch besser: | Evtl noch besser: | ||
+ | ^ ist das " | ||
<code java> | <code java> | ||
public static void naechste(boolean[] b) { | public static void naechste(boolean[] b) { | ||
Zeile 102: | Zeile 102: | ||
} | } | ||
</ | </ | ||
- | c) 2^n | + | |
+ | Evtl noch besserer: | ||
<code java> | <code java> | ||
- | long mgl (int n){ | + | for (int i = 0; i < b.length; i++) { |
- | return (long) Math.pow(2, n); | + | b[i] = b[i]? false : true; |
- | } | + | if(b[i]) break; |
+ | } | ||
</ | </ | ||
- | Aufgabenstellung: | + | |
+ | c) 2^n | ||
<code java> | <code java> | ||
- | | + | long mgl (int n){ |
- | return | + | return 1 << |
- | } | + | } |
</ | </ | ||
- | beide Ansätze sind falsch, ohne Methoden aus der Java-API und ohne weitere Anweisungen, | + | |
d) | d) | ||
Zeile 132: | Zeile 137: | ||
</ | </ | ||
e) | e) | ||
+ | ueber(n - 1, k - 1) und ueber(n - 1, k) | ||
- | ueber(n-1, | + | ==== |
- | + | ||
- | **__Aufgabe4__** | + | |
a) | a) | ||
<code java> | <code java> | ||
- | | + | class Cell { |
List< | List< | ||
int v; | int v; | ||
- | | + | } |
- | | + | class Chain { |
List< | List< | ||
int sum; | int sum; | ||
- | | + | boolean satisfiable() { |
- | int s = 0; | + | int s = 0; |
- | boolean[] vs = new boolean[10]; | + | boolean[] vs = new boolean[10]; |
- | for(Cell c : zs) { | + | |
- | s = s + c.v; | + | |
- | if(c.v != 0 && vs[c.v] == true){ | + | s = s + c.v; |
- | return false;} | + | |
- | | + | |
- | | + | return false; |
- | | + | |
- | | + | //Loesung vs[c.v] erst nach Abfrage auf " |
- | | + | //vs[c.v] = true; |
- | else if(sum != s){ //Hier muss man noch mit !vs[0] verunden, muss ja nur gleich sein, wenn alle Zahlen bekannt sind// | + | } |
- | | + | if (s > sum && |
- | } | + | return false; |
- | | + | } else if (s != sum && |
+ | return false; | ||
} | } | ||
+ | |||
+ | return true; | ||
+ | } | ||
</ | </ | ||
b) | b) | ||
<code java> | <code java> | ||
- | | + | boolean solve (LinkedList< |
- | if(cs.size()< | + | if (cs.size() <= 0) { |
- | | + | return true; |
} | } | ||
- | Cell z = cs.removeFirst(); | + | |
- | for( z.v = 1; z <= 9; z++){ // Schleifenkopf falsch, | + | |
- | | + | // try to assign |
- | | + | for (z.v = 1; z.v <= 9; z.v++) { |
- | | + | boolean ok = true; |
- | | + | for (Chain c : z.ks) { |
- | | + | if (!c.satisfiable()) { |
- | | + | ok = false; |
- | | + | } |
- | | + | } |
- | | + | // if all chains are ok => recurse |
- | | + | |
- | | + | return true; |
- | | + | } |
- | | + | } |
- | | + | |
+ | // backtrack | ||
+ | | ||
+ | cs.addFirst(z); | ||
+ | |||
+ | | ||
+ | } | ||
</ | </ | ||
- | **__Aufgabe5__** | ||
- | a) | + | ==== |
<code java> | <code java> | ||
- | | + | class UndirEdge< |
- | UndirEdge(T v, T w) { this.v = v; this.w = w; } | + | public final T v, |
- | } | + | public final T w; |
+ | | ||
+ | UndirEdge(T v, T w) { | ||
+ | | ||
+ | | ||
+ | | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | a) | ||
+ | <code java> | ||
+ | Map<T, T> initUnionFind(List< | ||
+ | | ||
| | ||
- | | + | |
- | Map<T, T> ufds = new HashMap< | + | |
- | for(UndirEdge | + | |
- | | + | |
- | | + | |
} | } | ||
return ufds; | return ufds; | ||
- | | + | } |
</ | </ | ||
+ | |||
b) | b) | ||
<code java> | <code java> | ||
- | | + | |
ufds.put(v, | ufds.put(v, | ||
} | } | ||
</ | </ | ||
- | c) bitte ergänzen | + | |
+ | c) | ||
<code java> | <code java> | ||
- | Feld 1 | + | T find(Map< |
- | | + | |
+ | // find root of n in ufds: | ||
+ | while (r != udfs.get(r) { | ||
r = udfs.get(r); | r = udfs.get(r); | ||
} | } | ||
- | Feld 2 | + | |
- | | + | // r is now pointing to the root of the partial set tree. |
- | | + | // perform path compression: |
+ | T c = n; | ||
+ | pc = ufds.get(c); | ||
+ | |||
+ | while (pc != r) { | ||
+ | // so lange wir noch nicht bei der Wurzel sind, machen wir die Knoten auf dem Pfad dorthin zu Kindern der Wurzel | ||
+ | | ||
c = pc; | c = pc; | ||
pc = udfs.get(c); | pc = udfs.get(c); | ||
} | } | ||
+ | | ||
+ | } | ||
</ | </ | ||
- | **__Aufgabe6__** | ||
+ | |||
+ | ==== | ||
a) | a) | ||
F(4, | F(4, | ||
Zeile 233: | Zeile 269: | ||
frac2cf(Frac(n, | frac2cf(Frac(n, | ||
- | frac2cf(Frac(n, | + | frac2cf(Frac(n, |
- | ich hätte hier: | ||
- | frac2cf(Frac(n, | ||
c) | c) | ||
- | cf2frac(L(n)) = Frac(n, 1) | ||
- | cf2frac(F(b, cf)) = Frac( num(Frac(b x den(Frac(cf))+den(cf2frac(cf)),den(cf2frac(cf))), | + | cf2frac(L(n)) = Frac(n, 1) |
- | den(Frac(b x den(Frac(cf))+den(cf2frac(cf)), | ||
- | ) | ||
- | |||
- | Ich hätte hier: | ||
cf2frac(F(b, | cf2frac(F(b, | ||
- | Das oben macht ja schon teilweise syntaktisch keinen Sinn | ||
d) | d) | ||
- | same(L(x), L(y)) = if(x==y) then true else false | + | same(L(x), L(y)) = x==y |
- | + | ||
- | //sollte man hier nicht immer "true zurückgeben? | + | |
- | + | ||
- | same(F(x, a), F(y, b)) = if(x==y) && same(a==b) then true else false | + | |
- | + | ||
- | //hier auch einfach true, oder?// | + | |
+ | same(F(x, a), F(y, b)) = x==y && same(a, b) | ||
same(F(x, a),L(y)) = false | same(F(x, a),L(y)) = false | ||
Zeile 265: | Zeile 288: | ||
same(L(x), | same(L(x), | ||
- | **__Aufgabe7__** | + | ==== |
bei a) - d) bin ich mir sicher, beim Rest könnt ihr mich gerne verbessern! Nein, bist du nicht. | bei a) - d) bin ich mir sicher, beim Rest könnt ihr mich gerne verbessern! Nein, bist du nicht. | ||
Zeile 271: | Zeile 294: | ||
a) Alpha | a) Alpha | ||
- | b) Beta, Wenn man den Code abtippt, sieht man, dass Beta ausgeben wird. Ich vermute, dass das Interface Alpha aufgerufen wird, da dies der statische Typ beim Objekt ag ist. Da der Parameter c der Methode omega int ist, wird hier implizit von char zu int gecastet. Dadurch wird omega(int i) (Klasse Beta) statt omega(char c) (Klasse Gamma) aufgerufen, da **int** hier eben besser passt. | + | b) Beta |
c) Gamma | c) Gamma | ||
Zeile 277: | Zeile 300: | ||
d) 4711 | d) 4711 | ||
- | e) Laut API hat out nen static modifier, also Klassenvariable// | + | e) Klassenvariable |
- | + | ||
- | f) öffentlich, | + | |
+ | f) öffentlich, | ||
g) 16 überlädt 6 | g) 16 überlädt 6 |