Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen
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:loesungws14 [08.07.2015 12:55] – Phreek90 | pruefungen:bachelor:aud:loesungws14 [09.07.2021 11:58] – BobbyB | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ===== Forendiskussion | + | ===== Forendiskussionen |
- | https:// | + | * [[https:// |
+ | * [[https:// | ||
+ | * [[https:// | ||
===== Lösungsversuch ===== | ===== Lösungsversuch ===== | ||
Zeile 31: | Zeile 33: | ||
int index = 0; //write index | int index = 0; //write index | ||
do { | do { | ||
- | for(int i = 0; i < in[c]; i++) { | + | for(int i = 0; i < count[c]; i++) { |
- | in[index++] | + | in[index++] = c; |
} | } | ||
c++; | c++; | ||
- | } while (c < count.length && | + | } while (index < in.length); |
} | } | ||
} | } | ||
</ | </ | ||
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; | ||
return kold; | return kold; | ||
} | } | ||
- | pos += c; | ||
- | pos %= map.length; | ||
} | } | ||
+ | pos = (pos + c) % s; | ||
} 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((n<m) || (m == 0 && | + | if(j >= 1 && j <= i-1) { |
+ | mem[i][j] = (3*(i-1)*mem[i-1][j] + j*mem[i-1][j-1])/ | ||
+ | } else if((i<j) || (j == 0 && | ||
mem[i][j] = 0; | mem[i][j] = 0; | ||
- | } else if(n == m) { | + | } else if(i == j) { |
mem[i][j] = 1; | mem[i][j] = 1; | ||
- | } else { | ||
- | mem[i][j] = (3*(n-1)*b(n-1, | ||
} | } | ||
} | } | ||
Zeile 140: | Zeile 138: | ||
nat2bin(n) = push(nat2bin(div(n, | nat2bin(n) = push(nat2bin(div(n, | ||
</ | </ | ||
- | c) ??? | + | c) |
+ | < | ||
+ | axs | ||
+ | bin2nat(empty) = zero | ||
+ | bin2nat(push(S, | ||
+ | |||
+ | </ | ||
==== Aufgabe 7 - Doppelverkettung (29) ==== | ==== Aufgabe 7 - Doppelverkettung (29) ==== | ||
+ | |||
+ | a+b) <code java> | ||
+ | class DLNode< | ||
+ | DLNode< | ||
+ | V v; //Aktuelles Element | ||
+ | DLNode< | ||
+ | | ||
+ | boolean isDLL() { //Aufgabe (a), checks if this node is part of a Doubly Linked List | ||
+ | DLNode< | ||
+ | boolean searchedEverything = false; | ||
+ | while(!searchedEverything) { | ||
+ | if(!(d.z.a == d && d.a.z == d)) { | ||
+ | return false; | ||
+ | } | ||
+ | d = d.z; | ||
+ | if(d == this || d == null || (d.z == null && d.a.z == d)) { | ||
+ | searchedEverything = true; | ||
+ | break; | ||
+ | } | ||
+ | } | ||
+ | d = this; | ||
+ | searchedEverything = false; | ||
+ | while(!searchedEverything) { | ||
+ | if(!(d.z.a == d && d.a.z == d)) { | ||
+ | return false; | ||
+ | } | ||
+ | d = d.a; | ||
+ | if(d == this || d == null || (d.a == null && d.z.a == d)) { | ||
+ | searchedEverything = true; | ||
+ | break; | ||
+ | } | ||
+ | } | ||
+ | | ||
+ | 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)); | ||
+ | } | ||
+ | | ||
+ | boolean isLoopedDLL() { //Aufgabe (b), checks if this node is part of a Looped DLL | ||
+ | DLNode< | ||
+ | if(!isDLL()) { | ||
+ | return false; | ||
+ | } else { | ||
+ | while(c != this) { | ||
+ | // Zuerst null-Check, c kann hier bereits null sein! | ||
+ | if(c == null) { | ||
+ | return false; | ||
+ | } | ||
+ | c = c.a; | ||
+ | } | ||
+ | c = this.z; | ||
+ | while(c != this) { | ||
+ | if(c == null) { | ||
+ | return false; | ||
+ | } | ||
+ | c = c.z; | ||
+ | } | ||
+ | return true; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | c+d) <code java> | ||
+ | class PriorityDeque< | ||
+ | DLNode< | ||
+ | | ||
+ | V get(boolean high) { //Aufgabe (c) | ||
+ | DLNode< | ||
+ | //list is empty | ||
+ | if(h == null) { | ||
+ | throw new NoSuchElementException(" | ||
+ | } | ||
+ | //list has only on single node - just empty the deque | ||
+ | else if(h.a == null || h.a == h) { | ||
+ | h = null; | ||
+ | } | ||
+ | //user requested head - reconfigure internal head pointer | ||
+ | else if(high) { | ||
+ | h = h.z; | ||
+ | } | ||
+ | //user requested node that preceeds head - retarget r | ||
+ | else { | ||
+ | r = h.a; | ||
+ | } | ||
+ | //unlink requested node r and return its value | ||
+ | r.a.z = r.z; | ||
+ | r.z.a = r.a; | ||
+ | return r.v; | ||
+ | } | ||
+ | | ||
+ | void put(V v) { //Aufgabe (d) | ||
+ | DLNode< | ||
+ | DLNode< | ||
+ | if(c == null || c.v.compareTo(v) < 0) { | ||
+ | //n becomes new head | ||
+ | h = n; | ||
+ | } else { | ||
+ | //search node c that immediately succeeds n | ||
+ | do { | ||
+ | c = c.z; | ||
+ | } while (c.v.compareTo(v) >= 0 && c != h); | ||
+ | } | ||
+ | // | ||
+ | if(c != null) { | ||
+ | c.a.z = n; | ||
+ | n.a = c.a; | ||
+ | n.z = c; | ||
+ | c.a = n; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </ |