Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Aufgabe 1 (Übersicht)
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungLetzte ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungws17 [24.07.2019 08:29] – Kleine Korrektur in Aufgabe 5a) dom | 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 103: | 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 133: | 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; |
- | | + | |
- | | + | // |
- | } | + | //vs[c.v] = true; |
- | else if(sum != s){ | + | |
- | | + | |
- | } | + | |
- | | + | |
} | } | ||
+ | if (s > sum && vs[0] == true) { // i) | ||
+ | return false; | ||
+ | } else if (s != sum && vs[0] == false) { // i) | ||
+ | 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(); | + | |
- | | + | |
- | | + | // try to assign 1 to 9 to its v and check all chains that z belongs to |
- | | + | |
- | | + | 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__** | + | ==== |
<code java> | <code java> | ||
class UndirEdge< | class UndirEdge< | ||
- | public final T v, w; | + | public final T v, |
+ | public final T w; | ||
| | ||
UndirEdge(T v, T w) { | UndirEdge(T v, T w) { | ||
Zeile 208: | Zeile 222: | ||
| | ||
| | ||
- | for(UndirEdge< | + | for (UndirEdge< |
| | ||
| | ||
Zeile 215: | Zeile 229: | ||
} | } | ||
</ | </ | ||
+ | |||
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 242: | 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(L(n)) = Frac(n, 1) | ||
- | cf2frac(F(b, | ||
- | |||
- | 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 274: | 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. | + | |
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 286: | Zeile 298: | ||
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 |