Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen (Übersicht)
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:bachelor:aud:loesungws14 [29.07.2015 12:44] – added aufgabe6c bin2nat(push(s,n)) schrolli | pruefungen:bachelor:aud:loesungws14 [08.04.2022 06:49] (aktuell) – Ich bin dumm, Änderung rückgängig BobbyB | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ===== Forendiskussion | + | ===== Forendiskussionen |
- | https:// | + | * [[https:// |
+ | * [[https:// | ||
+ | * [[https:// | ||
===== Lösungsversuch ===== | ===== Lösungsversuch ===== | ||
Zeile 40: | Zeile 42: | ||
</ | </ | ||
d) O(n)\\ | d) O(n)\\ | ||
- | e) NEIN, es ist nicht widerlegt, da es sich hier nicht um ein vergleichsbasiertes | + | e) NEIN, es ist nicht widerlegt, da es sich hier nicht um ein **nicht** |
==== Aufgabe 3 - Prim vs. Kruskal (10) ==== | ==== Aufgabe 3 - Prim vs. Kruskal (10) ==== | ||
Zeile 72: | Zeile 74: | ||
int pos = hk; //current position during exploration | int pos = hk; //current position during exploration | ||
do { //b) | do { //b) | ||
- | for(int i = 0; i < map[pos].length; i++) { | + | for(int i = 0; i < b; i++) { |
- | if(map[pos][i] == null) { | + | if(map[pos][i] == null || map[pos][i].equals(k)) { //keine NullPointerException dank lazy evaluation |
- | map[pos|[i] = k; | + | |
- | return null; | + | |
- | } else if(map[pos][i].equals(k)) { | + | |
K kold = map[pos][i]; | K kold = map[pos][i]; | ||
map[pos][i] = k; | map[pos][i] = k; | ||
Zeile 82: | Zeile 81: | ||
} | } | ||
} | } | ||
- | pos += c; | + | |
- | pos %= map.length; | + | |
} while (pos != hk); | } while (pos != hk); | ||
| | ||
Zeile 110: | Zeile 108: | ||
long bDP(int n, int m) { | long bDP(int n, int m) { | ||
long[][] mem = new long[n + 1][m + 1]; | long[][] mem = new long[n + 1][m + 1]; | ||
- | for(int i = 0; i < n; i++) { | + | for(int i = 0; i <= n; i++) { |
- | for(int j = 0; j < m; j++) { | + | for(int j = 0; j <= m; j++) { |
if(j >= 1 && j <= i-1) { | if(j >= 1 && j <= i-1) { | ||
mem[i][j] = (3*(i-1)*mem[i-1][j] + j*mem[i-1][j-1])/ | mem[i][j] = (3*(i-1)*mem[i-1][j] + j*mem[i-1][j-1])/ | ||
Zeile 144: | Zeile 142: | ||
< | < | ||
axs | axs | ||
- | bin2nat(empty) = null | + | bin2nat(empty) = zero |
- | bin2nat(push(s,n)) = add(n,mul(bin2nat(s), | + | bin2nat(push(S,N)) = add(N,mult(bin2nat(S), |
</ | </ | ||
==== Aufgabe 7 - Doppelverkettung (29) ==== | ==== Aufgabe 7 - Doppelverkettung (29) ==== | ||
Zeile 182: | Zeile 181: | ||
| | ||
return true; | return true; | ||
+ | } | ||
+ | | ||
+ | // Andere Lösung, die weniger Vergleiche hat | ||
+ | // IMHO ist jeweils ein Vergleich in den jeweils ersten IFs in den WHILEs redundant. | ||
+ | // Außerdem überprüft diese Lösung, ob die DLL auch in beide Richtungen zirkulär ist, wenn sie in eine Richtung zirkulär ist. | ||
+ | | ||
+ | boolean isDLL() { | ||
+ | DLNode< | ||
+ | | ||
+ | while (c != this && c != null) { | ||
+ | if (c.z != d) { | ||
+ | return false; | ||
+ | } | ||
+ | d = c; | ||
+ | c = c.z; //Anmerkung anderer Student: müsste mMn c = c.a sein | ||
+ | } | ||
+ | | ||
+ | // Anmerkung anderer Student: Das Zuruecksetzen von d fehlt mMn, da man ja unten mit dem oben veraenderten c weitermacht . Hab es mal hier drunter eingefuegt | ||
+ | d = this; | ||
+ | | ||
+ | DLNode< | ||
+ | while (e != this && e != null) { | ||
+ | if (e.a != d) { | ||
+ | return false; | ||
+ | } | ||
+ | d = e; | ||
+ | e = e.a; //Anmerkung anderer Student: müsste mMn e = e.z sein | ||
+ | } | ||
+ | |||
+ | // Either both null (non-circular) or both not null (circular in both directions!) | ||
+ | return ((c == null && e == null) || (c != null && e != null)); | ||
} | } | ||
| | ||
Zeile 190: | Zeile 220: | ||
} else { | } else { | ||
while(c != this) { | while(c != this) { | ||
- | c = c.a; | + | |
if(c == null) { | if(c == null) { | ||
return false; | return false; | ||
} | } | ||
+ | c = c.a; | ||
} | } | ||
c = this.z; | c = this.z; | ||
while(c != this) { | while(c != this) { | ||
- | c = c.z; | ||
if(c == null) { | if(c == null) { | ||
return false; | return false; | ||
} | } | ||
+ | c = c.z; | ||
} | } | ||
return true; | return true; | ||
Zeile 219: | Zeile 250: | ||
} | } | ||
//list has only on single node - just empty the deque | //list has only on single node - just empty the deque | ||
- | else if(h.a == null && | + | else if(h.a == null || h.a == h) { |
h = null; | h = null; | ||
} | } |