===== Forendiskussionen =====
* [[https://fsi.informatik.uni-erlangen.de/forum/thread/12767-klausur-WS2014|Aufgabe 1]]
* [[https://fsi.cs.fau.de/forum/thread/12844-WS14-ADT|Aufgabe 6]]
* [[https://fsi.cs.fau.de/forum/thread/17211-Mit-this-keyword-auf-Variablen-zugreifen-WS14-Auf|Aufgabe 7]]
===== Lösungsversuch =====
==== Aufgabe 1 - Wissensfragen (16) ====
^ Teilaufgabe ^ Lösungsmöglichkeit 1 ^ Lösungsmöglichkeit 2 ^ Lösungsmöglichkeit 3 ^ Lösungsmöglichkeit 4 ^
| a | X | X | | |
| b | X | | X | |
| c | | | | X |
| d | | X | | X |
| e | X | | X | |
| f | | X | | X |
| g | X | X | | |
| h | X | | | X |
==== Aufgabe 2 - Sortieren durch Zählen (12) ====
a - c)
public class CountingSort {
public static void sort(char[] in) {
int[] count = new int[256]; //a)
for(int i = 0; i < in.length; i++) { //b)
count[in[i]] += 1;
}
char c = 0; //current char (Teilaufgabe c)
int index = 0; //write index
do {
for(int i = 0; i < count[c]; i++) {
in[index++] = c;
}
c++;
} while (index < in.length);
}
}
d) O(n)\\
e) NEIN, es ist nicht widerlegt, da es sich hier nicht um ein **nicht** vergleichsbasiertes Sortierverfahren handelt!
==== Aufgabe 3 - Prim vs. Kruskal (10) ====
a) (A,B) -- (B,D) -- (B,C)\\
b) (B,D) -- (A,D) -- (D,C)\\
c) NEIN
==== Aufgabe 4 - Streuspeicherung (18) ====
a)
^Bucket -> ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^
|1st key | D | A | E | B | |
|2nd key | F | | G | C | |
b)
class HashSet {
K[][] map;
int s, b, c;
HashSet(int s, int b, int c) {
assert 0 < c && c < s;
this.s = s; //size of map
this.b = b; //bucket size
this.c = c; //collision increment
map = (K[][]) new Object[s][b];
}
K put(K k, int hk) {
assert k != null && 0 <= hk && hk < s;
int pos = hk; //current position during exploration
do { //b)
for(int i = 0; i < b; i++) {
if(map[pos][i] == null || map[pos][i].equals(k)) { //keine NullPointerException dank lazy evaluation
K kold = map[pos][i];
map[pos][i] = k;
return kold;
}
}
pos = (pos + c) % s;
} while (pos != hk);
throw new IllegalArgumentException();
}
}
==== Aufgabe 5 - Dynamische Programmierung (20) ====
a)
long b(int n, int m) {
if(m >= 1 && m <= n-1) {
return (3*(n-1)*b(n-1,m) + m*b(n-1,m-1))/n;
} else if((n
b)
long bDP(int n, int m) {
long[][] mem = new long[n + 1][m + 1];
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= m; j++) {
if(j >= 1 && j <= i-1) {
mem[i][j] = (3*(i-1)*mem[i-1][j] + j*mem[i-1][j-1])/i;
} else if((i
==== Aufgabe 6 - Abstrakte Datentypen (15) ====
a)
axs
peek(empty) = null
peek(push(s, n)) = n
pop(empty) = empty
pop(push(s,n)) = s
b)
axs
nat2bin(zero) = push(empty, zero)
nat2bin(n) = push(nat2bin(div(n, succ(succ(zero)))), mod(n, succ(succ(zero))))
c)
axs
bin2nat(empty) = zero
bin2nat(push(S,N)) = add(N,mult(bin2nat(S),succ(succ(zero)))) // (N + 2*bin2nat(S))
==== Aufgabe 7 - Doppelverkettung (29) ====
a+b)
class DLNode {
DLNode a; //Referenz auf Vorgänger
V v; //Aktuelles Element
DLNode z; //Referenz auf Nachfolger
boolean isDLL() { //Aufgabe (a), checks if this node is part of a Doubly Linked List
DLNode d = this, c = this.a; //drag/current pointers
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 d = this, c = this.a;
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 e = this.z;
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 c = this.a;
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)
class PriorityDeque> {
DLNode h; //highest prio node (null if empty)
V get(boolean high) { //Aufgabe (c)
DLNode r = h; //will finally point to requested node
//list is empty
if(h == null) {
throw new NoSuchElementException("[Error] List is empty!");
}
//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 c = h; //current node (drag)
DLNode n = new DLNode(); n.v = v; n.a = n.z = n;
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);
}
//insert/link n before c, if c exists
if(c != null) {
c.a.z = n;
n.a = c.a;
n.z = c;
c.a = n;
}
}
}