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

Dies ist eine alte Version des Dokuments!

Inhaltsverzeichnis

Forendiskussionen

Lösungsversuch

Aufgabe 1 - Wissensfragen

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

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.

e) 

public void addSorted(Entry toAdd){ //keeps list sorted
   Entry cur = head.next;
   Entry drag = head;
 
   while(cur !=head){
     if(cur.element >toAdd.element){
       drag.next = toAdd;
       toAdd.next = cur;
     }
     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 

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)