Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen

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