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 [24.07.2019 08:34] – Kleine Korrektur Aufgabe 5 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 223: | Zeile 237: | ||
</ | </ | ||
- | | + | |
<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 246: | 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 278: | 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 284: | 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 290: | 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 |