===== Forendiskussionen =====
* [[https://fsi.informatik.uni-erlangen.de/forum/thread/11018-Loesungsversuch-Miniklausur]]
===== Lösungsversuch =====
==== Aufgabe 1 - Wissensfragen ====
**a)** falsch: Assertions können selektiv per Flag beim Ausführen ab-/angeschaltet werden. Assertions sind also praktisch nie äquivalent zu anderen Codestücken.\\
**b)** Option 2 und 3 sind richtig \\
**c)** O(n)\\
**d)** richtig\\
**e)** richtig\\
==== Aufgabe 2 (Magisches Quadrat) ====
**a)**
boolean isSolved(int[][] sq){
int n = sq.length;
int checkSum = ((n * n * n) + n) / 2;
int rowSum = 0, colSum = 0, diag1Sum = 0, diag2Sum = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
rowSum += sq[i][j];
colSum += sq[j][i];
}
if(rowSum != checkSum || colSum != checkSum){
return false;
}
else {
rowSum = colSum = 0;
}
}
for(int i = 0; i < n; i++){
diag1Sum += sq[i][i];
diag2Sum += sq[n - 1 - i][i];
}
if(diag1Sum != checkSum || diag2Sum != checkSum){
return false;
}
return true;
}
**b)**
boolean solve(int [][] sq, int pos, boolean [] used) {
int n = sq.length;
int col = pos % n;
int row = (pos - col) / n;
if(pos >= used.length){
return isSolved(sq);
}
else {
for(int i = 1; i <= used.length; i++){
if(used[i-1] == false){
sq[col][row] = i;
used[i-1] = true;
if(solve(sq, pos+1, used)){
return true;
}
sq[col][row] = 0;
used[i-1] = false;
}
}
}
return false;
}
==== Aufgabe 3 (Listen) ====
**a)** head.next = head;
**b)** 13 zwischen den Elementen 11 und 17 einfügen. Die next-Referenz von 11 zeigt dann auf 13, und next von 13 verweist auf 17.
**c)** -2 zwischen dem head-Element und 7 einfügen. Die next-Referenz des Sentinel-Elements zeigt dann auf -2, und next von -2 verweist auf 7.
**d)** O(n), da das Element, nach dem eingefügt werden soll, immer erst per linearer Suche gesucht werden müsste.
**e)**
public void addSorted(Entry toAdd){ //keeps list sorted
Entry cur = head.next;
Entry drag = head;
// Fügt das Element immer hinter gleichen Elementen ein
// z. B. füge 3'' in -1 -> 2 -> 3 -> 3' -> 5 -> ... ein:
// -1 -> 2 -> 3 -> 3' -> 3'' -> 5 -> ...
while(cur.element < toAdd.element && cur != head){
drag = cur;
cur = drag.next;
}
drag.next = toAdd;
toAdd.next = cur;
}
==== Aufgabe 4 (Abstrakte Datentypen) ====
**ops**
create: T --> AA
get: int x AA --> T
set: int x T x AA --> AA
delete: int x AA --> AA
size: AA --> int
**axs**
// Werte überschreiben
// Axiom set(x, val, create) nicht spezifiziert, da es nicht weiter
// aufgelöst werden kann, denn set ist ein Konstruktor.
set(x, val1, set(x, val2, aa)) = set(x, val1, aa)
set(x, val1, set(y, val2, aa)) = set(y, val2, set(x, val1, aa)) wenn x != y
// reihenfolge ist egal bei unterschiedlichen x,y, bei gleichem index wird überschrieben.
get(x,create) = null
get(x, set(y, e, aa)) = e, wenn x = y; sonst: get(x, aa)
delete(x, create) = create
delete(x, set(y, e, aa)) = aa, wenn x = y; sonst: set(y, e, delete(x, aa))
size(create) = 0
size(set(x, e, aa)) = 1 + size(aa), wenn get(x, aa) = null
size(set(x, e, aa)) = size(aa), sont