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 [04.06.2019 13:09] – SpeedyGonzalez | pruefungen:bachelor:aud:loesungws17 [05.08.2019 15:22] – 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; |
- | | + | |
- | | + | //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(); | + | |
- | | + | |
- | | + | // 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__** | ||
- | 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 234: | 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 266: | 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 272: | 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 | + | b) Beta, weil, siehe Vorlesungsfolien " |
c) Gamma | c) Gamma | ||
Zeile 278: | 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 |