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

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungss15 [29.03.2016 13:16] – DP a, b, c, hinzugefügt Marcel[Inf]pruefungen:bachelor:aud:loesungss15 [09.04.2017 18:35] – vrochri
Zeile 3: Zeile 3:
   * [[https://fsi.cs.fau.de/forum/thread/13555-Altklausur-SS15-2-Loesungsvorschlag-Baeume]] Aufgabe 2   * [[https://fsi.cs.fau.de/forum/thread/13555-Altklausur-SS15-2-Loesungsvorschlag-Baeume]] Aufgabe 2
   * [[https://fsi.cs.fau.de/forum/thread/13531-Altklausur-SS15-5-DAG]] Aufgabe 5 - **eingefügt!**   * [[https://fsi.cs.fau.de/forum/thread/13531-Altklausur-SS15-5-DAG]] Aufgabe 5 - **eingefügt!**
-  * [[https://fsi.cs.fau.de/forum/thread/13536-Vorschlag-fuer-Aufgabe-6-Dynamische-Programmierun]] Aufgabe 6+  * [[https://fsi.cs.fau.de/forum/thread/13536-Vorschlag-fuer-Aufgabe-6-Dynamische-Programmierun]] Aufgabe 6 **eingefügt!**
   * [[https://fsi.cs.fau.de/forum/thread/13535-Vorschlag-fuer-Altklausur-SS-15-Aufgabe-7-Sorti]] Aufgabe 7 **eingefügt!**   * [[https://fsi.cs.fau.de/forum/thread/13535-Vorschlag-fuer-Altklausur-SS-15-Aufgabe-7-Sorti]] Aufgabe 7 **eingefügt!**
  
Zeile 11: Zeile 11:
   * a) 1 und 4   * a) 1 und 4
   * b) 1 und 2   * b) 1 und 2
-  * c) 2 und 3 +  * c) 4 *Edit*(und 2) vgl. Vl 14 S. 85 *Edit* 
-  * 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+ 
 +  * 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   * e) 3 und 4
   * f) 1   * f) 1
-  * g) 2und 3+  * g) 2 und 3
   * h) 1 und 4   * h) 1 und 4
 ==== Aufgabe 2 - Bäume (9) ==== ==== Aufgabe 2 - Bäume (9) ====
 +
 +[[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html | Tool]]
 ==== Aufgabe 3 - Graphen (18) ==== ==== Aufgabe 3 - Graphen (18) ====
 +a) Endergebnis: 0,2,4,7,6,7
 +
 b) A->B->C->F->E->D, Distanz 7. b) A->B->C->F->E->D, Distanz 7.
  
Zeile 45: Zeile 50:
  
 ==== Aufgabe 4 - Rekursion (11) ==== ==== Aufgabe 4 - Rekursion (11) ====
 +
 +Live auf ideone.com mit AuD-Beispiel: http://ideone.com/jr02d3
 +
 +<code java>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;
 +}</code>
 ==== Aufgabe 5 - Gerichtete azyklische Graphen (15) ==== ==== Aufgabe 5 - Gerichtete azyklische Graphen (15) ====
 <code java>boolean eval(HashSet<String> tv) { <code java>boolean eval(HashSet<String> tv) {
Zeile 84: Zeile 116:
  fn = dp[n-1];  fn = dp[n-1];
  } else if (n >= 3) { // fn muss noch berechnet werden  } else if (n >= 3) { // fn muss noch berechnet werden
- fn = fDP(n - 2*fDP(n - fDP(n-1))) + 1; 
  if (n <= dp.length) {  if (n <= dp.length) {
 + fn = fDP(n - 2*fDP(n - fDP(n-1))) + 1;
  dp[n-1] = fn;  dp[n-1] = fn;
 + } else {
 + fn = f(n);
  }  }
  }  }
  return fn;  return fn;
  }  }
 +}
 +</code>
 +
 +d)
 +
 +Hier sind viele Varianten denkbar.
 +<code java>
 +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;
 } }
 </code> </code>