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

Forendiskussionen

  • TODO: Noch keiner. Falls welche angelegt, hier eintragen! :)

Lösungsversuch

Aufgabe 1 - Wissensfragen

a) 1 und 4
b) 2 und 4
c) 2 und 3

Aufgabe 2 - Rekursion

static List<List<Long>> potenzmenge(long n) {
	List<List<Long>> pm = new ArrayList<>();
	if (n <= 0) {
		// Basisfall
		pm.add(new ArrayList<Long>());
	} else {
		// Rekursion
		List<List<Long>> rek = potenzmenge(n - 1);
		// Ergebnisse zusammenfuehren
		for (List<Long> ohneN : rek) {
			List<Long> mitN = new ArrayList<>(ohneN); // *noch* ohne n
			mitN.add(n);
			pm.add(mitN);
			pm.add(ohneN);
		}
	}
	return pm;
}

Aufgabe 3 - ADT

isBlack(new, x, y) = false

isBlack(flip(cv, x1, y1), x2, y2) =
    !isBlack(cv, x2, y2)    falls x1=x2 && y1=y2
    isBlack(cv, x2, y2)      sonst

bottom(new) = 0
bottom(flip(cv, x1, y1)) =
    y1               falls y1 < bottom(cv) && !isBlack(cv, x1, y1)
    bottom(cv)       sonst

Aufgabe 4 - Dynamische Programmierung

private long pLR(int n, long[] ps) {
	ps[1] = 2;
	if (n >= 2) {
		ps[n] = pLR(n - 1, ps);
		int i = 0;
		do {
			ps[n]++;
			for (i = 1; i < n && ps[n] % ps[i] != 0; i++) {
			}
		} while (i != n); // kleineren Teiler gefunden?
	}
	return ps[n];
}

Aufgabe 5 - Streuspeicherung

Diese Aufgabe entspricht 1:1 Aufgabe 4 aus der Klausur WS14/15.

Nein, nicht ganz. Hier muss im Gegensatz zur großen Klausur nicht das alte Objekt zurückgegeben werden, falls man auf dieses an der zu besetzenden Stelle trifft. Das erkennt man auch daran, dass in der Miniklausur der return-type „void“ verwendet wurde.

class HashSet<K>  {
    K[][] map;
    int s, b, c;
 
    HashSet(int s, int b, int c) {
        assert 0 < c && c < s;
        this.s = s; //size of map
        this.b = b; //bucket size
        this.c = c; //collision increment
        map = (K[][]) new Object[s][b];
    }
 
    K put(K k, int hk) {
        assert k != null && 0 <= hk && hk < s;
        int pos = hk; //current position during exploration
        do { 
            for(int i = 0; i < b; i++) { //Für jede Stelle b des Buckets
                if(map[pos][i] == null) {
                    map[pos|[i] = k;
                    return;
            }
            pos += c;
            pos %= s; //hiermit wird sichergestellt, dass pos nicht Groesser als s wird und in diesem Fall wieder von vorne beginnt, aber Schrittlänge c beibehaelt
        } while (pos != hk); //pos wird im do-Block geaendert, wenn es also wieder gleich hk werden wuerde, liegt ein Zyklus vor
 
        throw new IllegalArgumentException();
    }
}