Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen
Inhaltsverzeichnis
Forendiskussionen
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