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 [26.03.2016 19:35] – Marcel[Inf]pruefungen: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 32: Zeile 33:
 **g)** Bucketsort, Mergesort **g)** Bucketsort, Mergesort
  
-**h)** Richtig+**h)** Richtig, weil: \\ 
 +\\ 
 +Zusammenhänge für die Höhe h eines AVL-Baums mit n Knoten: \\ 
 +log<sub>2</sub>(n + 1) ≤ h < 1,441 * log<sub>2</sub>(n + 2) \\ 
 +\\ 
 +<=> O(log<sub>2</sub>(n + 1)) ≤ h < O(1,441 * log<sub>2</sub>(n + 2)) \\ 
 +<=> O(log<sub>2</sub>(n)) ≤ h < O(log<sub>2</sub>(n + 2)) \\ 
 +<=> O(log<sub>2</sub>(n)) ≤ h < O(log<sub>2</sub>(n)) \\ 
 +\\ 
 +=> h ∈ O(log<sub>2</sub>(n)) \\
  
-**i)** Falsch+ 
 +**i)** Falsch; nur bei gerader Anzahl an Elementen.
  
 **j)** O(1) **j)** O(1)
Zeile 49: 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 69: 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 139: 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 155: Zeile 188:
 **b)** **b)**
   * **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 171: 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 197: 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 228: 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 236: 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 245: 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 256: 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 323: 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>