FSI Informatik/pruefungen/bachelor/aud/loesungss15

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

Dies ist eine alte Version des Dokuments!

Inhaltsverzeichnis

Forendiskussionen
Lösungsversuch

Forendiskussionen

Lösungsversuch

Aufgabe 1 - Wissensfragen (16)

a) 1 und 4
b) 1 und 2
c) 2 und 3
d) 1 und 4 (unsicher!). Interfaces weder implementieren noch erben von Object ⇒ siehe JLS: http://docs.oracle.com/javase/specs/jls/se7/html/jls-9.html#jls-9.2
e) 3 und 4
f) 1
g) 2und 3
h) 1 und 4

Aufgabe 2 - Bäume (9)

Aufgabe 3 - Graphen (18)

b) A→B→C→F→E→D, Distanz 7.

B, A
A, D
E, D
E, F
F, C

Alternativ:

B, C
F, C
E, F
E, D
D, A

Stark zusammenhängend: keine
Schwach zusammenhängend: 1, 6
Zusammenhängend: 3
Nicht zusammenhängend: 2, 4, 5

Aufgabe 4 - Rekursion (11)

Aufgabe 5 - Gerichtete azyklische Graphen (15)

Aufgabe 6 - Dynamische Programmierung (17)

Aufgabe 7 - Sortieren (16)

Aufgabe 8 - Backtracking (18)

LinkedList<int[]> helfer(int mL, int kL, int b, int mR, int kR) {
	LinkedList<int[]> erg = new LinkedList<>();
	if(mL < 0 || kL < 0 || mR < 0 || kR < 0) {
		// Abbruch wegen negativer Personenzahl
		return null;
	} else if(mem[mL][kL][b][mR][kR]) {
		// Abbruch weil Zustand schon besucht
		return null;
	} else if((mL > 0 && mL < kL) || (mR > 0 && mR < kR)) {
		// Abbruch zu viele Kannibalen an einem der Ufer
		return null;
	} else if(mL == 0 && kL == 0 && b == 1) {
		// Zielzustand erreicht
		erg.add(new int[] { mL, kL, b, mR, kR });
		return erg;
	} else {
		// zulaessiger Zwischenzustand
		erg.add(new int[] { mL, kL, b, mR, kR });
 
		for(int[] fahrt : denkbar[b]) {
			// probiere jede denkbare fahrt, die am Ufer b beginnt
			mem[mL][kL][b][mR][kR] = true;
			LinkedList<int[]> list = helfer(mL - fahrt[0], kL - fahrt[1], (b + 1) % 2, mR + fahrt[0], kR + fahrt[1]);
			if(list != null) {
				erg.addAll(list);
				return erg;
			}
			mem[mL][kL][b][mR][kR] = false;
		}
	}
	return null;
}