Lösungsversuch Miniklausur

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Lösungsversuch Miniklausur
Hallo zusammen!
Ich habe mir gedacht, dass es (zwecks Klasurvorbereitung o. Ä.) ganz hilfreich wäre, eine Lösung für die Miniklausur zusammenzustellen, da der LS 2 (meines Wissens) keine Lösung herausgegeben hat. Ich poste hier mal meinen (teilweisen) Lösungsversuch (keine Garantie auf Korrektheit!). Wer ihr Korrekturen habt oder Lösungen für die anderen Aufgaben, stellt sie einfach hier rein!

1) (MC)
a) falsch: nur bei assert(x < 4711) wären die Codefragmente äquivalent
b) Option 2 und 3 sind richtig
c) O(n)
d) richtig
e) richtig

2a) (magisches Quadrat)

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;
}

3) ADTs
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.

4) ADTs
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
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(x, set(x, e, aa) = size(aa), wenn get(x, aa) = null; sonst: 1 + size(aa)


  1. a) head.next = head; unter keinen Umständen den Konstruktor von Entry aufrufen!

edit: Bei 2a darf checkSum nicht auf 0 gesetzt werden.
edit2: dachte eig. schon, aber nein.


Nope, hier bin ich etwas anderer Meinung, denn die beiden Zeilen koennen IMHO nie äquivalent sein, da fuer Assertions immer das entsprechende Flag beim Programmstart uebergeben werden muss, wohingegen das manuelle Schmeißen der Exception immer passieren kann.


Es gab eine 1f)?

Danke, ich hab es gefixt. (hatte colSum mit CheckSum verwechselt).


Der Sinn von Assertions ist ja schließlich dass man sie abschalten kann, richtig?


Ja. Es geht ja auch nicht um den Sinn von Assertions, sondern darum, ob sich die beiden Codefragmente immer gleich verhalten. Und da man Assertions eben an- und abschalten kann, tun sie das nicht.

1 „Gefällt mir“

2b)
3d) O(n) (schlimmster Fall ist die komplette Liste durchlaufen)

Ich trag hier mal meine 2b) nach, für die Musterlösung:

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;

if(used[i-1] != true){

:-/

if(solve(sq; pos+1; used)){

Nur weil eine Methode drei Parameter hat (und deswegen gewisse Ähnlichkeit zum for-Kopf bestehen?) werden die Kommas nicht durch Strichpunkte ersetzt :wink: Habe das in der Korrektur öfter gesehen, wie kommts?


Schlecht abgetippt. In der Klausur stehen bei mir , :wink:

Und ja klar, ich hätte jetzt auch „== false“ schreiben können…aber ich dacht mir so: Nea. ärgern wir ict ein wenig :stuck_out_tongue:

(Habe meinen Beitrag korrigiert. Fehler sind nicht gestattet!)


Wenn du jetzt noch ein

(!used[i-1])

daraus machst bin ich noch glücklicher :slight_smile:


(used[i-1] == used[i-1] ^ used[i-1])

(Sorry, habe heute von GCC generierten x86-Assembler gesehen.)


Akzeptiert und abgemacht. Ich hoffe, ich konnte dir den Abend etwas versüßen :wink:


Interessant :smiley: War das mit [m]-Os[/m] oder sowas? Denke die machen das, weil man so eine 0 mit etwas erzeugen kann, was man eh aus dem RAM laden muss und sonst keinen Speicherzugriff und keinen Immediate Operand braucht.


Nimm den Post nicht so ernst, er ist nur davon inspiriert, wie GCC (und andere Compiler) Register auf x86 nullen: [m]xor eax, eax[/m]. So Code hat GCC nicht erzeugt (zumindest bei mir nicht, kann nicht ausschließen, dass man ihn doch irgendwie dazu bringen kann ;)).


Ah dachte schon :smiley: Aber ausschließen kann mans nie, deswegen hab ichs dir auch gleich geglaubt…


int test(int arg) {
        return arg == 0;
}

$ gcc -O2 -S -o - test.c -c

        .file   "test.c"
        .text
        .p2align 4,,15
        .globl  test
        .type   test, @function
test:
.LFB0:
        .cfi_startproc
        xorl    %eax, %eax
        testl   %edi, %edi
        sete    %al
        ret
        .cfi_endproc
.LFE0:
        .size   test, .-test
        .ident  "GCC: (Debian 4.8.2-12) 4.8.2"
        .section        .note.GNU-stack,"",@progbits

Fazit: Test auf 0 gibts billiger mit ‘test’, Register nullen für den Rückgabewert funktioniert so in der Tat ohne immediate operand und spart so Speicher.


müsste Zeile 1 im Basisfall nicht „if(pos >= used.length)“ lauten. pos beginnt bei „0“ und geht doch bis „used.length -1“?

Miniklausur WS13/14 Aufgabe 3e)
Hätte hier noch einen Vorschlag für die 3e)

if (toAdd != null) {
	while (cur != head) {
		if (cur.element <= toAdd.element) {
			drag = cur;
			cur = cur.next;
		} else {
			drag.next = toAdd;
			toAdd.next = cur;
			return;
		}
	}
}

Edit: Man kann beides machen und auch „if(pos == used.length)“ funktioniert. Wenn man einen Schritt später als nötig abbricht, sind alle Elemente besucht und man begeht den Inhalt der for-Schleife quasi gar nicht.

Ich habe meinen Fehler vom ehemaligen Post gefunden und gefixt.