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
pruefungen:bachelor:aud:loesungws09 [10.12.2017 18:05] – ep2910pruefungen:bachelor:aud:loesungws09 [20.06.2020 14:09] (aktuell) – BierBaron69
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. Naja es hängt in v.a. auch von der Wahl des Pivot-Elementes ab.
  
 **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 156: 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 170: 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 196: 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 227: 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 235: 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 244: 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 255: 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 322: 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>