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
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) Bucket 1: 27 - 75 Bucket 3: 44 - 4 - 0 Bucket 5: 13 - 65 - 33 Bucket 7: 46 - 26
b) Es werden nur die ungeraden Buckets befüllt, da 2 und 8 nicht teilerfremd sind.
c) Bucket 0: 12 S Bucket 1: 33 D Bucket 2: 66 S Bucket 3: 28 P Bucket 4: 14 D Bucket 5: 6 S Bucket 6: 18 D Bucket 7: 5 D Bucket 8: 15 P Bucket 9: 9 D
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); } private long countDPH (long[] mem, int n) { if (mem[n] != 0) { return mem[n]; } else { int sum = 0; for (int i = 0; i < n; i++){ sum = sum + countDPH(i) * countDPH(n-1-i); } mem[n] = sum; return sum; } } long countIter (int n) { ... for (int k = 2; k < n+1; k++){ for (int i = 0; i < n; i++){ mem[k] = mem[k] + mem[i] * mem[n-1-i]; } } ... }
Aufgabe 5 Graphen
a) Ergebnis: A 14, E 18, H4 6, H7 3, M 2, W 0
b) siehe Tafeluebungsfolien
c) M - H7, M - W, M - H4, A - E, A - H4 oder A - W
d) nein: bei 4 Knoten ungerader Grad nein: nicht mal ein Eulerweg
Aufgabe 6 Rekursion
class MaxFlowMinCut { void erreichbareVerteiler(Verteiler v, List<Verteiler> ev){ if(!ev.contains(v)){ ev.add(v); for(Rohr r : v.rohre){ this.erreichbareVerteiler(r.a, ev); this.erreichbareVerteiler(r.e, ev); } } } double schnittDurchfluss(List<Verteiler> quelleSeite, List<Verteiler> senkeSeite){ double sum = 0; for(Verteiler v : quelleSeite){ for(Rohr r : v.rohre){ if(senkeSeite.contains(r.a) || senkeSeite.contains(r.e)){ sum += r.df; } } } return sum; } double durchfluss(List<Verteiler> quelleSeite, List<Verteiler> senkeSeite, Verteiler senke){ Verteiler[] ssa = senkeSeite.toArray(new Verteiler[senkeSeite.size()]); double df = schnittDurchfluss(quelleSeite, senkeSeite); for(Verteiler v : ssa){ if(!v.equals(senke)){ quelleSeite.add(v); senkeSeite.remove(v); df = Math.min(df, durchfluss(quelleSeite, senkeSeite)); senkeSeite.add(v); quelleSeite.remove(v); } } return df; } }