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

~ Hier entsteht in nächster Zeit eine Beispiellösung ~

Forendiskussionen

Lösungsversuch

Aufgabe 1 Wissensfragen

a) 1 und 4

b) 1 und 2

c) 2 und 4

d) 1 und 3

e) 2 und 3

f) 1 und 3

g) 2 und 3

h) 3 und 4

Aufgabe 2 Streupeicherung

a)

TODO

b) Es werden nur die ungeraden Buckets befüllt, da 2 und 8 nicht teilerfremd sind.

c) TODO

Aufgabe 4 RadixSort

a) 

void radixSort (LinkedList<Integer> list) {
	LinkedList<Integer>[] bs = new LinkedList[];
	for (int i = 0; i < bs.length; i++) {
		bs[i] = new LinkedList();
	}
	for (int i = 0; i < 10; i++) {
		for (Integer x: list) {
			int b = (x/Math.pow(10,i)) % 10;
			bs[b].addLast(x);
		}
		list.clear();
		for (int i = 0; i < bs.length; i++) {
			list.addAll(bs[i]);
			bs[i].clear();
		}
	}
}

b) 

...
int b = ((x/Math.pow(10,i)) % 10) + 9;
...

Aufgabe 4 Dynamische Programmierung

a) 

long countNaive(int n) {
	if (n == 0 || n == 1) {
		return 1;
	}
	int sum = 0;
	for (int i = 0; i < n; i++){
		sum = sum + countNaive(i) * countNaive(n-1-i);
	}
	return sum;
}
 
long countDP (int n) {
	long[] mem = new long[];
	mem[0] = 1;
	mem[1] = 1;
	return countDPH(mem, n);
	...
}

Aufgabe 5 Sortieren

a)

L * A1 B1 F A2 B2
A1L*B1F A2B2
A1B1L*F A2B2
A1B1F L*A2B2
A1A2B1F L*B2
A1A2B1B2F L*

b)

Aufgabe 7 Graphen

public class GraphWS15 {
 
void sammle(boolean[][] am, int k, Set<Integer> verb, Set<Integer> bes) {
		if (!bes.contains(k)) {
			verb.add(k);
			bes.add(k);
			for (int i = 0; i < am[k].length; i++) {
				if (am[k][i]){
					sammle(am, i, verb, bes);
				}
			}
 
			for (int i = 0; i < am.length; i++) {
				if (am[i][k]){
					sammle(am, i, verb, bes);
				}
			}
		}
	}
 
	List<Set<Integer>> mszt(boolean[][] am) {
		// Ergebnisliste:
		List<Set<Integer>> ergebnis = new LinkedList<>();
		// Menge besuchter Knoten:
		Set<Integer> bk = new HashSet<>();
		// Ermittle alle Teilgraphen mittels Hilfsmethode sammle:
		for (int k = 0; k < am.length; k++) {
			if (!bk.contains(k)){
				// falls k noch nicht besucht => sammle mit k verbundene Knoten
				Set<Integer> verb = new HashSet();
				sammle(am,k,verb, bk);
				ergebnis.add(verb);
			}
 
		}
 
		return ergebnis;
	}
 
	void itg(boolean[][] am, Set<Integer> vs) {
		for (int i=0;i<am.length;i++){
			for (int j=0;j<am[i].length;j++){
				if (am[i][j]){
					if (vs.contains(i) && vs.contains(j)){
						// ok
					}
					else {
						am[i][j] = false;
					}
				}
			}
 
		}
	}
 
	public static void main(String[] args){
                //Beispielaufruf mit aus 3 Subgraphen bestehendem Graph
		GraphWS15 g = new GraphWS15();
		boolean[][] am = {{false, true, false, true, false, false},
                                              {false, false, false, true, false, false},
                                              {false, false, false, false, true, false},
                                              {false, true, false, false, false, false},
                                              {false, false, false, false, false, false},
                                              {false, false, false, false, false, false}};
		//Set<Integer> verb = new HashSet();
		List<Set<Integer>> n = g.mszt(am);
		System.out.println(n.size()); 
		System.out.println(n.get(0).size()); 		 
		System.out.println(n.get(1).size()); 
		System.out.println(n.get(2).size()); 
	}
}