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

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
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws09 [18.03.2018 22:50] – Evrenpruefungen:bachelor:aud:loesungws09 [17.05.2019 15:09] – SpeedyGonzalez
Zeile 10: Zeile 10:
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8861-Klausur-25-02-2010-Aufgabe-7b-Dijkstra]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8861-Klausur-25-02-2010-Aufgabe-7b-Dijkstra]]
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/9468-Klausur-25-02-2010]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/9468-Klausur-25-02-2010]]
 +  * [[https://fsi.cs.fau.de/forum/thread/17186-Klausur-Ws2009-Frage-zu-ADTs-A8c]]
  
 ===== Lösungsversuch ===== ===== Lösungsversuch =====
Zeile 59: Zeile 60:
 **b)** **b)**
 ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7  ^ ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7  ^
-| 1 | 3 | 6 | 9 | 4 | 12 | 2 | 5 |+| 1<sub>7</sub> | 3<sub>0</sub> | 6<sub>0</sub> | 9<sub>0</sub> | 4<sub>0</sub> | 12<sub>3</sub> | 2<sub>0</sub> | 5<sub>0</sub> |
  
 **c)** **c)**
Zeile 79: Zeile 80:
 private static long[][] b = new long[MAX][MAX]; private static long[][] b = new long[MAX][MAX];
 // Vorinitialisierung des Felds b[][] mit -1 // Vorinitialisierung des Felds b[][] mit -1
 +//Klausurfragestellung nicht ganz eindeutig, gefragt ist hier richtigerweise dynamische Programmierung mittels Memoization
  
-private static long binomFast(int n, int k) {+private static long binom(int n, int k) { 
  if(k > n)  if(k > n)
  return 0;  return 0;
Zeile 149: Zeile 151:
  return true;  return true;
 } }
 +</code>
 +
 +oder rekursive Version:
 +
 +<code java>
 +static boolean insertRec(BinTree b, int value) {
 +        if (value > b.value) {
 +            if (b.right == null) {
 +                b.right = new BinTree(value);
 +                return true;
 +            }
 +            return insertRec(b.right, value);
 +        } else if (value < b.value) {
 +            if (b.left == null) {
 +                b.left = new BinTree(value);
 +                return true;
 +            }
 +            return insertRec(b.left, value);
 +        }
 +        return false;
 +    }
 </code> </code>
  
Zeile 166: Zeile 189:
   * **O(n log n)**   * **O(n log n)**
 Sollte es nicht O(n) sein? In den VL-Folien steht, dass das Aufbauen einer Halde aus einem Array der Länge n nur O(n) ist. (Beweis wurde ausgelassen, aber intuitiv deswegen, weil die obere Hälfte des Arrays keine Kinder in der Halde hat => ein großer Teil fällt schon mal weg!) Sollte es nicht O(n) sein? In den VL-Folien steht, dass das Aufbauen einer Halde aus einem Array der Länge n nur O(n) ist. (Beweis wurde ausgelassen, aber intuitiv deswegen, weil die obere Hälfte des Arrays keine Kinder in der Halde hat => ein großer Teil fällt schon mal weg!)
 +
 +Ja O(n), in der Klausur wurde nach der effizientesten Möglichkeit gesucht. Diese baut den Heap in O(n) auf, wie hier unter 4.2.4 beschrieben: http://linux-related.de/index.html?/coding/sort/sort_heap.htm
  
 **c)** **c)**
Zeile 180: Zeile 205:
  }  }
 } }
 +</code>
 +
 +Das ginge meines Erachtens (bei anderer Angabe noch leichter), oder??:
 +
 +<code java>
 +
 +public static void haldenSortierung(int[] feld){
 +    haldenEigenschaftHerstellen(feld);
 +        
 +    for(int i = feld.length - 1; i > 0; i--){
 +        tausche(feld, 0, i);
 +        versickern(feld, 0, i - 1);
 +    }
 +}   
 </code> </code>
  
Zeile 206: Zeile 245:
 ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^
 | [0] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |  | [0] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 
-| 0 | 4 | [2] | ∞ | ∞ | ∞ | ∞ | ∞ |  +| | 4<sub>A</sub> | [2<sub>A</sub>] | ∞ | ∞ | ∞ | ∞ | ∞ |  
-| 0 | [3] | 2 | 7 | ∞ | ∞ | ∞ | ∞ |  +| | [3<sub>C</sub>] | | 7<sub>C</sub> | ∞ | ∞ | ∞ | ∞ |  
-| 0 | 3 | 2 | 7 | ∞ | [4] | ∞ | ∞ |  +| | | | 7<sub>C</sub> | ∞ | [4<sub>B</sub>] | ∞ | ∞ |  
-| 0 | 3 | 2 | 7 | [5] | 4 | ∞ | 8 | +| | | | 7<sub>C</sub> | [5<sub>F</sub>] | | ∞ | 8<sub>F</sub> | 
-| 0 | 3 | 2 | [7] | 5 | 4 | 10 | 8 | +| | | | [7<sub>C</sub>] | | | 10<sub>E</sub> | 8<sub>F</sub> | 
-| 0 | 3 | 2 | 7 | 5 | 4 | 10 | [8] | +| | | | | | | 10<sub>E</sub> | [8<sub>F</sub>] | 
-| 0 | 3 | 2 | 7 | 5 | 4 | [9] | 8 |  +| | | | | | | [9<sub>H</sub>] | |   
-| 0 | 3 | 2 | 7 | 5 | 4 | 9 | 8 | + 
 +[9<sub>H</sub>] -> [8<sub>F</sub>] -> [4<sub>B</sub>] -> [3<sub>C</sub>] -> [2<sub>A</sub>] -> [0] 
 + 
 +=> A -> C -> B -> F -> H -> G
  
 **c) Euler** **c) Euler**
Zeile 237: Zeile 279:
 contains(x, put(y, M)) = contains(x, M); contains(x, put(y, M)) = contains(x, M);
 </code> </code>
 +oder 
 +\\ 
 +<code> 
 +axs 
 +contains(s, create()) = FALSE 
 +contains(s, put(a, m)) = { TRUE             falls s = a 
 +                         { contains(s, m)   sonst 
 +</code>
 **b)** **b)**
 <code> <code>
Zeile 245: Zeile 294:
 count(x, put(x, M)) = 1 + count(x, M) count(x, put(x, M)) = 1 + count(x, M)
 count(x, put(y, M)) = count(x, M) count(x, put(y, M)) = count(x, M)
 +</code>
 +oder
 +\\
 +<code>
 +ops
 +count: String x MultiSet   ->   Integer
 +
 +axs
 +count(s, create()) = 0
 +count(s, put(a, m)) = { 1 + count(s, m)  falls s = a
 +                      { count(s, m)      sonst
 </code> </code>
  
Zeile 254: Zeile 314:
 purge(x, put(x, M)) = purge(x, M) purge(x, put(x, M)) = purge(x, M)
 purge(x, put(y, M)) = put(y, purge(x, M)) purge(x, put(y, M)) = put(y, purge(x, M))
 +</code>
 +oder
 +\\
 +<code>
 +ops
 +purge: String x MultiSet   ->   MultiSet
 +
 +axs
 +purge(s, create()) = create()
 +purge(s, put(a, m)) = { purge(s, m)            falls s = a
 +                      { put(a, purge(s, m))    sonst
 </code> </code>
  
Zeile 265: Zeile 336:
 <code> <code>
 wp("a = a*3 - 1; b = 80 - a; b--;", b > 47) = wp("a = a*3 - 1; b = 80 - a; b--;", b > 47) =
 +wp("a = a*3 - 1; b = 80 - a; b = b - 1;", b > 47) =
 wp("a = a*3 - 1; b = 80 - a;", b - 1 > 47) = wp("a = a*3 - 1; b = 80 - a;", b - 1 > 47) =
 wp("a = a*3 - 1;", 80 - a - 1 > 47) = wp("a = a*3 - 1;", 80 - a - 1 > 47) =
Zeile 332: Zeile 404:
 iii) iii)
  
-</code>+<code>
 V = i V = i
 i = n, n > 0 -> V > 0 zu Beginn i = n, n > 0 -> V > 0 zu Beginn
 i = i - k, k > 0 -> i ist monoton fallend i = i - k, k > 0 -> i ist monoton fallend
 </code> </code>