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
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws09 [16.02.2013 14:13] – Dawodopruefungen:bachelor:aud:loesungws09 [17.05.2019 15:09] – SpeedyGonzalez
Zeile 1: Zeile 1:
-==forum==+===== Forendiskussionen =====
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8082-Klausur-25-02-2010]] 4c   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8082-Klausur-25-02-2010]] 4c
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8048-Klausuren-Wissensfragen]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8048-Klausuren-Wissensfragen]]
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 =====
  
 +==== Aufgabe 1 - Wissensfragen ====
  
-=== Aufgabe 1 - Wissensfragen (14P) === 
 **a)** Richtig **a)** Richtig
  
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 40: Zeile 51:
 **k)** O(n) **k)** O(n)
  
------ 
  
-=== Aufgabe 2 - Streutabellen (13P) ===+==== Aufgabe 2 - Streutabellen ====
 **a)** **a)**
 ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7  ^ ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7  ^
Zeile 50: 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 57: Zeile 67:
 Ein Schlüssel kann so unter Umständen nicht der Hashtabelle hinzugefügt werden, obwohl noch Buckets frei wären. Ein Schlüssel kann so unter Umständen nicht der Hashtabelle hinzugefügt werden, obwohl noch Buckets frei wären.
  
------ 
  
-== Aufgabe 3 ==+==== Aufgabe 3 -Rekursion ====
  
 **a)** **a)**
Zeile 71: 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 86: Zeile 96:
 </code> </code>
  
------ 
  
-== Aufgabe 4 ==+==== Aufgabe 4 - Suchbäume ====
  
 **a)** **a)**
Zeile 144: Zeile 153:
 </code> </code>
  
------+oder rekursive Version:
  
-== Aufgabe 5 ==+<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> 
 + 
 + 
 +==== Aufgabe 5 - Halde ====
 **a)** **a)**
  
Zeile 159: 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!)
 +
 +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 173: 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 183: Zeile 229:
   * haldenSortierung: **O(n log n)**   * haldenSortierung: **O(n log n)**
  
------ +==== Aufgabe 6 - UML ====
- +
-== Aufgabe 6 UML ==+
  
 {{:pruefungen:bachelor:aud:2010.02.25.aufgabe_6_uml_korrekt.png|:pruefungen:bachelor:aud:2010.02.25.aufgabe_6_uml_korrekt.png}} {{:pruefungen:bachelor:aud:2010.02.25.aufgabe_6_uml_korrekt.png|:pruefungen:bachelor:aud:2010.02.25.aufgabe_6_uml_korrekt.png}}
  
------+==== Aufgabe 7 - Graphen ====
  
-== Aufgabe 7 - Graphen (15P)== 
 **a) Adjazenzmatrix** **a) Adjazenzmatrix**
 ^   ^ A ^ B ^ C ^ D ^  ^   ^ A ^ B ^ C ^ D ^ 
Zeile 202: 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 225: Zeile 271:
 Die Kante DC wird nicht genommen, da nur Kanten hinzugefügt werden, die zu einem noch nicht besuchten Knoten führen. Die Kante DC wird nicht genommen, da nur Kanten hinzugefügt werden, die zu einem noch nicht besuchten Knoten führen.
  
------ 
  
-=== Aufgabe 8 – Abstrakte Datentypen (15P) ===+==== Aufgabe 8 – Abstrakte Datentypen ====
 **a)** **a)**
 <code> <code>
Zeile 234: 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 242: 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 251: 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 258: Zeile 332:
 create, put create, put
  
------ +==== Aufgabe 9 - wp-Kalkül ====
- +
-== Aufgabe 9 ==+
 **a)** **a)**
 <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 274: Zeile 347:
 <code> <code>
 wp("if (x < 0 || x > 7) {x = 7 - x;} else {x = 8 + x;}", x != 7) =  wp("if (x < 0 || x > 7) {x = 7 - x;} else {x = 8 + x;}", x != 7) = 
-[(x < 0 ∨ x > 7) ∧ wp("x = 7 - x;", x = 7)] ∨ [¬(x < 0 ∨ x > 7) ∧ wp("x = 8 + x;", x != 7)] = +[(x < 0 ∨ x > 7) ∧ wp("x = 7 - x;", x != 7)] ∨ [¬(x < 0 ∨ x > 7) ∧ wp("x = 8 + x;", x != 7)] = 
 [(x < 0 ∨ x > 7) ∧ (7 - x != 7)] ∨ [(x ≥ 0) ∧ (x ≤ 7) ∧ (8 + x != 7)] =  [(x < 0 ∨ x > 7) ∧ (7 - x != 7)] ∨ [(x ≥ 0) ∧ (x ≤ 7) ∧ (8 + x != 7)] = 
 [(x < 0 ∨ x > 7) ∧ (x != 0)] ∨ [(x ≥ 0) ∧ (x ≤ 7) ∧ (x != -1)] =  [(x < 0 ∨ x > 7) ∧ (x != 0)] ∨ [(x ≥ 0) ∧ (x ≤ 7) ∧ (x != -1)] = 
Zeile 331: Zeile 404:
 iii) iii)
  
-  V = i +<code> 
-  i = n, n > 0 -> V > 0 zu Beginn +V = i 
-  i = i - k, k > 0 -> i ist monoton fallend +i = n, n > 0 -> V > 0 zu Beginn 
 +i = i - k, k > 0 -> i ist monoton fallend 
 +</code>