FSI-Zimmer: geschlossen
Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen
Inhaltsverzeichnis
Forendiskussionen
- https://fsi.cs.fau.de/forum/thread/13531-Altklausur-SS15-5-DAG Aufgabe 5 - eingefügt!
Lösungsversuch
Aufgabe 1 - Wissensfragen (16)
- a) 1 und 4
- b) 1 und 2
- c) 4 *Edit*(und 2) vgl. Vl 14 S. 85 *Edit*
- Erneuter Edit von jemand anderem: 4 ist nicht richtig, der Laufzeitaufwand bei Prim ist O(n*log n + e). O(n + m) = O(max(n, m)), n*log(n) ist hier max, darum stimmt O(n*log(n)). Ausserdem ist 3 sehr wohl richtig: Das steht exakt so in der Vorlesung, Kruskal hat O(e*log e).
- d) 1 und 4 (zu 2: 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) 2 und 3
- h) 1 und 4
Aufgabe 2 - Bäume (9)
Aufgabe 3 - Graphen (18)
a) Endergebnis: 0,2,4,7,6,7 —> Falsch: Von A nach F kommt man mit Pfad A→B→C→F mit Kosten 5, 7 kann also nicht stimmen. Lösung ist: 0,2,4,7,6,5)
b) A→B→C→F→E→D, Distanz 7.
c)
- B, A
- A, D
- E, D
- E, F
- F, C
Alternativ:
- B, C
- F, C
- E, F
- E, D
- D, A
d)
- Stark zusammenhängend: keine
- Schwach zusammenhängend: 1, 6
- Zusammenhängend: 3
- Nicht zusammenhängend: 2, 4, 5
Aufgabe 4 - Rekursion (11)
Live auf ideone.com mit AuD-Beispiel: http://ideone.com/jr02d3
static <T> List<List<T>> helfer(T[] s, int idx) { // Rückgabe pms ist Potenzmenge von s ab index idx List<List<T>> pms = new ArrayList<List<T>>(); if (idx >= s.length) { // Basisfall pms.add(new ArrayList<T>()); } else { // aktuelles Kopfelement bestimmen T kopf = s[idx]; // Potenzmenge der Restliste bestimmen List<List<T>> potRest = helfer(s, idx + 1); // Ergebnisse zusammenführen for (List<T> ohneKopf : potRest) { List<T> mitKopf = new ArrayList<>(ohneKopf); // *nocH* ohne Kopf mitKopf.add(kopf); pms.add(ohneKopf); pms.add(mitKopf); } } return pms; }
Aufgabe 5 - Gerichtete azyklische Graphen (15)
boolean eval(HashSet<String> tv) { if (this == BDD.TRUE) return true; if (this == BDD.FALSE) return false; return tv.contains(v) ? trueC.eval(tv) : falseC.eval(tv); } boolean isDAG(HashSet<BDD> p) { if (p.contains(this)) return false; p.add(this); if (trueC != null && !trueC.isDAG(p)) { return false; } if (falseC != null && !falseC.isDAG(p)) { return false; } p.remove(this); return true; }
Aufgabe 6 - Dynamische Programmierung (17)
a) Verschachtelte Rekursion
b, c)
class DynProg { private int[] dp; public DynProg(int max) { dp = new int[max]; } int fDP(int n) { // Dynamische Programmierung int fn = 1; // Basisfall n < 3 trivial // fn schon einmal berechnet? if (n <= dp.length && dp[n-1] != 0) { fn = dp[n-1]; } else if (n >= 3) { // fn muss noch berechnet werden if (n <= dp.length) { fn = fDP(n - 2*fDP(n - fDP(n-1))) + 1; dp[n-1] = fn; } else { fn = f(n); } } return fn; } }
d)
Hier sind viele Varianten denkbar.
public static int fIter(int n) { // Iterativ int k = 1; // Zähler int fk = 1; int z = 2; for (; k<=n; k++) { if (z == 0) { fk++; z = 2 * fk - 1; } else { z--; } } return fk; }
Aufgabe 7 - Sortieren (16)
Mit System.out.println() Aufrufen zum Testen:
public class MergeSortUsing4Lists { public static void mergeSortExtern(LinkedList<Integer> b) { assert b != null; assert b.size() > 0; LinkedList<Integer> b0 = new LinkedList<>(); LinkedList<Integer> b1 = new LinkedList<>(b.subList(0, b.size() / 2)); LinkedList<Integer> b2 = new LinkedList<>(b.subList(b.size() / 2, b.size())); LinkedList<Integer> b3 = new LinkedList<>(); merge(1, b0, b1, b2, b3); b.clear(); b.addAll(b0); b.addAll(b1); } public static void merge(int len, LinkedList<Integer> b0, LinkedList<Integer> b1, LinkedList<Integer> b2, LinkedList<Integer> b3) { LinkedList<Integer> target = b0; // alternating between b0 and b3 do { System.out.println(); System.out.println(b0); System.out.println(b1); System.out.println(b2); System.out.println(b3); System.out.println(); int z1 = 0, z2 = 0; // counter for the already stored integers from // b1/b2 up to len // if possible, store integers from b1 AND b2 while (!b1.isEmpty() && !b2.isEmpty() && z1 < len && z2 < len) { // Wegen <= ist es stabil if (b1.getFirst() <= b2.getFirst()) { target.addLast(b1.removeFirst()); z1++; } else { target.add(b2.removeFirst()); z2++; } } // if there are still integers from b1 while (!b1.isEmpty() && z1 < len) { target.addLast(b1.removeFirst()); z1++; } // if there are still integers from b2 while (!b2.isEmpty() && z2 < len) { target.addLast(b2.removeFirst()); z2++; } target = target == b0 ? b3 : b0; } while (!b1.isEmpty() || !b2.isEmpty()); // b3 is not empty => recursion call! if (!b3.isEmpty()) { merge(2 * len, b1, b0, b3, b2); } else { System.out.println(); System.out.println(b0); System.out.println(b1); System.out.println(b2); System.out.println(b3); System.out.println(); } } public static void main(String[] args) { LinkedList<Integer> a_empty = new LinkedList<Integer>(); mergeSortExtern(a_empty); LinkedList<Integer> a = new LinkedList<Integer>( Arrays.asList(10, 2, 1, 7, 6, 9, 13, 6, 3, 5, 8, 4, 11, 2, 6, 42)); mergeSortExtern(a); // odd number of elements (added number 19) LinkedList<Integer> a_odd = new LinkedList<Integer>( Arrays.asList(10, 2, 1, 7, 6, 9, 19, 13, 6, 3, 5, 8, 4, 11, 2, 6, 42)); mergeSortExtern(a_odd); } }
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; }