Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

Link zu dieser Vergleichsansicht

Both sides previous revision Vorhergehende Überarbeitung
Nächste Überarbeitung
Vorhergehende Überarbeitung
pruefungen:bachelor:aud:loesungss08 [15.02.2013 14:56]
Dawodo
pruefungen:bachelor:aud:loesungss08 [25.05.2017 15:58] (aktuell)
ab21ajus
Zeile 1: Zeile 1:
-==forum==+===== Forendiskussionen =====
   * [[https://​fsi.informatik.uni-erlangen.de/​forum/​thread/​8015-ADT-Klausuraufgabe-13-Juli-2008]]   * [[https://​fsi.informatik.uni-erlangen.de/​forum/​thread/​8015-ADT-Klausuraufgabe-13-Juli-2008]]
   * [[https://​fsi.informatik.uni-erlangen.de/​forum/​thread/​7081-O-Kalkuel-31-07-2008]]   * [[https://​fsi.informatik.uni-erlangen.de/​forum/​thread/​7081-O-Kalkuel-31-07-2008]]
Zeile 7: Zeile 7:
   * [[https://​fsi.informatik.uni-erlangen.de/​forum/​thread/​8844-Klausur-31-07-2008]] 1c,3a,5b, 6b,c,d   * [[https://​fsi.informatik.uni-erlangen.de/​forum/​thread/​8844-Klausur-31-07-2008]] 1c,3a,5b, 6b,c,d
  
-==== Lösungsversuch ====+===== Lösungsversuch ​=====
  
-=== Aufgabe 1 - Rucksack ===+==== Aufgabe 1 - Rucksack ​====
  
 **a)** **a)**
Zeile 53: Zeile 53:
 {{:​pruefungen:​bachelor:​aud:​rucksack.java.txt|:​pruefungen:​bachelor:​aud:​rucksack.java.txt}} {{:​pruefungen:​bachelor:​aud:​rucksack.java.txt|:​pruefungen:​bachelor:​aud:​rucksack.java.txt}}
  
-=== Aufgabe 2 - ADT ===+==== Aufgabe 2 - ADT ====
 **a)** **a)**
   create, add, remove, removeAll   create, add, remove, removeAll
 +Es wurde nach Konstruktoren gefragt, aber remove und removeAll sind doch nur Hilfskonstruktoren?​ (Vorlesung 10, Folie 10-10)
  
 **b)** **b)**
Zeile 72: Zeile 73:
   removeAll(x,​ add(y, M)) = add(y, removeAll(x,​ M))   removeAll(x,​ add(y, M)) = add(y, removeAll(x,​ M))
  
-=== Aufgabe 3 ===+==== Aufgabe 3 - Java====
 a) a)
   * statisch: A, dynamisch: A   * statisch: A, dynamisch: A
Zeile 95: Zeile 96:
   * **8**   * **8**
  
-=== Aufgabe 4 - Hashes ===+==== Aufgabe 4 - Hashes ​====
 **a)** **a)**
 ^ x =              ^ 7 ^ 26 ^ 27 ^ 4 ^ 47 ^ 9 ^ 6 ^ 36 ^ 17 ^ 57 ^ 56 ^ 42 ^ 10 ^ 77^ ^ x =              ^ 7 ^ 26 ^ 27 ^ 4 ^ 47 ^ 9 ^ 6 ^ 36 ^ 17 ^ 57 ^ 56 ^ 42 ^ 10 ^ 77^
Zeile 138: Zeile 139:
 ^ 9 | 47 | S | ^ 9 | 47 | S |
  
-=== Aufgabe 5 ===+==== Aufgabe 5 - Sortieren ====
  
 **a)** **a)**
Zeile 185: Zeile 186:
   * **Ja**   * **Ja**
  
-===Aufgabe 6===+==== Aufgabe 6 - Suchen ==== 
 + 
 +**a)**
 <code java> <code java>
-    // a) +private static int findPhotoForDate(Date d, Photo[] p, int start, int end) { 
-    ​private static int findPhotoForDate(Date d, Photo[] p, int start, int end){ + int mid = (end + start) ​2; 
-        // kann Date nicht finden + 
-        if (end > start{ + if (start > end) 
-            return -1;  + return -1; 
-        ​} ​   + 
-        int mid = (end+start) / 2; + if(p[mid].moreRecentThan(d== 0) { 
-        if (d.equals(p[mid].date)){ + return mid; 
-            return mid; + 
-        } else if (d.compareTo(p[mid].date) < 0){  + // Photo[mid] wurde vor dem gewünschten Datum erstellt 
-            ​return findPhotoForDate(d,​ p, start, mid-1); + // gesuchtes Photo muss "​rechts"​ davon sein 
-        } else { + } else if(p[mid].moreRecentThan(d) < 0) {  
-            ​return findPhotoForDate(d,​ p, mid+1, end);   + return findPhotoForDate(d,​ p, mid + 1, end); 
-        ​} ​   + 
-    }    + // Photo[mid] wurde nach dem gewünschten Datum erstellt 
-    // b) hier suchen wir linear ​nach dem start und end index, das koennte + // gesuchtes Photo muss "​links"​ davon sein 
-    // man natuerlich auch mit binary search implementieren,​ dann waers O(log n),  + } else 
-    // aber war nicht verlangt + return ​findPhotoForDate(d,​ pstart, mid - 1); 
-    public static Photo[] findAllPhotosForDate(Date d, Photo[] p){  +
-        int index = findPhotoForDate(d,​ p);  +
-        if (index == -1) { +
-            return new Photo[0]; +
-        }    +
-        // suche startindex +
-        int start = index;  +
-        while (start >=0 && p[start].date.equals(d)) { +
-            ​start--; +
-        }    +
-        // suche endindex +
-        int end = index+1+
-        while (end < p.length && p[end].date.equals(d)) { +
-            end+++
-           +
-        Photo[] result = new Photo[end-start];​ +
-        System.arraycopy(p,​ start, result, 0,  end-start);​ +
-        return result; +
-      ​+
 </​code>​ </​code>​
-  * **c)** O (log n) 
-  * **d)** Nein, Ja 
  
-===Aufgabe 7===+**b)** 
 + 
 +<code java> 
 +public static Photo[] findAllPhotosForDate(Date d, Photo[] p) { 
 + int index = findPhotoForDate(d,​ p); 
 + if (index == -1) 
 + return new Photo[0]; 
 + 
 + // suche Startindex 
 + int start = index; 
 + while (start >= 0 && p[start].moreRecentThan(d) == 0) { 
 + start--;​ 
 +
 + start++;​ //​ start steht jetzt auf dem Index des ersten Bildes mit dem gesuchten Datum 
 + 
 + // suche Endindex 
 + int end = index; 
 + while (end < p.length && p[end].moreRecentThan(d) == 0) { 
 + end++; 
 +
 + // end steht auf dem Index des ersten Bildes, das nicht mehr dem gesuchten Datum entspricht 
 + 
 + Photo[] result = new Photo[end - start]; 
 + System.arraycopy(p,​ start, result, 0, end - start); 
 + 
 + return result; 
 +
 +</​code>​ 
 + 
 +**c)** 
 +  * **O(n)**, zwar findet man das erste Bild in O(log n), jedoch haben im schlimmsten Fall alle n Bilder das gleiche Datum 
 + 
 +**d)** 
 +  * **Nein** 
 +  * **Ja** 
 + 
 + 
 +==== Aufgabe 7 - Graphen ====
 **a)** **a)**
-  * nein +  * **Nein**, es haben mehr als 2 Knoten einen ungeraden Grad 
-  * ja +  * **Ja**, jeder Knoten ist von jedem anderen aus erreichbar 
-  * nein +  * **Ja** 
-  * nein +  * **Nein**, Knoten G hat den Grad 6 
-  * nein +  * **Nein**, man kann keinen Zyklus bilden, der jede Kante nur genau einmal enthält 
-  * nein (DAG = directed acyclic graph) ​+  * **Nein**, der Graph ist gerichtet und enthält Zyklen
  
 **b)** **b)**
 ^ B ^ C ^D ^ E ^ G ^ H ^ I ^ J ^ K ^ ^ B ^ C ^D ^ E ^ G ^ H ^ I ^ J ^ K ^
- ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | [0] | ∞ |+| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | [0] | ∞ |
 | 10 | ∞ | ∞ | [7] | ∞ | ∞ | ∞ | 0 | ∞ | | 10 | ∞ | ∞ | [7] | ∞ | ∞ | ∞ | 0 | ∞ |
-| [10] | ∞ | 25 | 7 | ∞ | ∞ | ∞ | 0 | ∞ | +| [10] | ∞ | 25 | 7 | 53 | ∞ | ∞ | 0 | ∞ |
-| 10 | ∞ | 25 | 7 | 53 | ∞ | ∞ | 0 | ∞ |+
 | 10 | 23 | [18] | 7 | 53 | ∞ | ∞ | 0 | ∞ | | 10 | 23 | [18] | 7 | 53 | ∞ | ∞ | 0 | ∞ |
 +| 10 | [22] | 18 | 7 | 53 | 53 | 24 | 0 | ∞ |
 | 10 | 22 | 18 | 7 | 53 | 53 | [24] | 0 | ∞ | | 10 | 22 | 18 | 7 | 53 | 53 | [24] | 0 | ∞ |
-| 10 | 22 | 18 | 7 | 53 | [44] | 24 | 0 | ∞ |+| 10 | 22 | 18 | 7 | 53 | [44] | 24 | 0 | 60 | 
 +| 10 | 22 | 18 | 7 | 53 | 44 | 24 | 0 | [60] |
 | 10 | 22 | 18 | 7 | 53 | 44 | 24 | 0 | 60 | | 10 | 22 | 18 | 7 | 53 | 44 | 24 | 0 | 60 |
 +
 +\\
 +Kanten (in dieser Reihenfolge):​ \\
 +JE, JB, BD, DC, DI, IH, EG, HK 
  
 **c)** **c)**
-  * Nein +  ​* **Nein**, im neuen Spannbaum würde beispielsweise die Kante ED vorkommen, die aktuell nicht vorkommt 
-  * Ja +  ​* **Ja** 
-  * Nein+  ​* **Nein**
  
 **d)** **d)**
-  * J -> B -> D -> I -> H -> K +^ nach Knoten ^ Weglänge ^ Route ^ 
-  ​* ​G -> E -> J+| K | 60 | J -> B -> D -> I -> H -> K | 
 +| 53 | J -> E -> G |
  
 **e)** **e)**
Zeile 263: Zeile 290:
 CD, DI, DB, BA, BJ, JE, EF, IH, HG, HK CD, DI, DB, BA, BJ, JE, EF, IH, HG, HK
  
-===Aufgabe 8 - WP===+==== Aufgabe 8 - wp-Kalkül ====
 **a)** **a)**
-<​code>​ +  wp("a = 4*b; b = 7 - a; a += b;", a = 7 ∧ b = 3) =  
-wp('a = 4*b; b = 7-a;', a+b = 7 b = 3) +  wp("a = 4*b; b = 7 - a;", a + b = 7 ∧ b = 3)  
-wp('a=4b;' ​a + 7 -a = 7 7-a = 3) +  wp("a = 4*b;", ​a + (7 - a= 7 ∧ (7 - a= 3)  
-wp(4b + 7 - 4b = 7 7 - 4b = 3 +  ((4*b) (7 - (4*b)) ​= 7 ∧ (7 - (4*b)) ​= 3) =  
-</​code>​+  (7 = 7 ∧ 7 - 3 = 4*b) =  
 +  (true ∧ 4 = 4*b) =  
 +  (4 = 4*b) =  
 +  (1 = b) 
  
 **b)** **b)**
-<​code>​ +  ​wp("if a > b then b = a;", a = 7 ∧ b = 3)  
-wp('if a > b then b=a;', a = 7 b = 3) +  [(a > b) ∧ wp("b = a;", a = 7 ∧ b = 3)] ∨ [(a ≤ b) ∧ (a = 7 ∧ b = 3)] =  
-wp('​if ​a > b then b=a;', a= 7 b = 3) o. wp(' ​a = 7 b = 3) +  [(a > b) ∧ (a = 7 ∧ a = 3)] ∨ false =  
-[a>b] ^ wp(' b=a;', ​a= 7 ^ b = 3) o. wp(' a 7 ^ b = 3) +  (a > b) ∧ false =  
-wp(b=7) +  ​false 
-b=7 +
-</​code>​+
  
 **c)** **c)**
-2. Option ist korrekt! +2.\\ 
-1 geht nicht, da sie vor der Schleife nicht erfüllt ist und hat kein und y.+Option ist korrekt ​\\ 
 +\\ 
 +Nummer ​1 geht nicht, da sie vor der Schleife nicht erfüllt ist 
 +Nummer ​geht nicht, da sie werde noch hat
  
 **d)** **d)**
-<​code>​ + 
-wp('y = 1; i = x;', y = 2^(x+1-i) -1) +  ​wp("​y = 1; i = x;", y = 2^(x+1-i) - 1) = 
-wp('y = 1;', y = 2^(x+1-x) -1) +  wp("y = 1;", y = 2^(x+1-x) - 1) = 
-wp('y = 1;', y = 2^(1) -1) +  (1 = 2^(x+1-x) - 1) = 
-wp(1 = 2^(1) -1) +  (1 = 2^(1) - 1) = 
-1=1 +  (1 = 2 - 1) = 
-</​code>​+  (1 = 1) = 
 +  true 
 + 
 +  ​wp('y = 1; i = x;', y = 2^(x+1-i) -1) 
 +  wp('y = 1;', y = 2^(x+1-x) -1) 
 +  wp('y = 1;', y = 2^(1) -1) 
 +  wp(1 = 2^(1) -1) 
 +  1=1
  
 **e)** **e)**
-<​code>​ +  ... 
-wp('y = y*2; y = y+1; i = i-1', y = 2^(x+1-i) -1) +  wp('y = y*2; y = y+1; i = i-1', y = 2^(x+1-i) -1) 
-wp('y = y*2; y = y+1;', y = 2^(x+1-(i-1)) -1) +  wp('y = y*2; y = y+1;', y = 2^(x+1-(i-1)) -1) 
-wp('y = y*2;', y+1 = 2^(x+1-i+1) -1) +  wp('y = y*2;', y+1 = 2^(x+1-i+1) -1) 
-(y*2) +1 = 2^(x+1-i+1) -1 +  (y*2) +1 = 2^(x+1-i+1) -1 
-y = 1^(x+2+1) -1  +  y = 1^(x+2+1) -1  
-</​code>​+  ...
  
-===Aufgabe 9=== +==== Aufgabe 9 - O-Kalkül ==== 
-  ​* ​**a)**  +**a)**  
-    * O(n) +    ​* **O(n)** 
-    * O(n^2) +    ​* **O(n^2)** 
-    * O( n^2) +    ​* **O(n^2)** 
-    * O(n log n+    ​* **O(n log n)** 
-    * O(n) +    * **O(n)**
-  * **b)**  +
-    * O(1) +
-    ​* O(n) +
-    ​O(2^n) //sollte nicht O(n) stimmen??+
  
-===Aufgabe 10 - Graphen===+**b)**  
 +    * **O(1)** 
 +    * **O(n)** 
 +    * **O(2^n)** 
 + 
 +**c)** 
 +    * **Nein** 
 +    * **Ja** 
 + 
 +==== Aufgabe 10 - Darstellung von Graphen ​====
 **a)** **a)**
-==Adjazenzmatrix==+ 
 +**Adjazenzmatrix** 
 |     ^ A ^ B ^ C ^ D ^ E ^ F ^ |     ^ A ^ B ^ C ^ D ^ E ^ F ^
-^ A |   ​  ​+ ​  +  ​  ​   ​   +^ A | - | 11 | - | - | - | 
-^ B |  ​+  ​    +  ​ ​+  ​+  ​ - | +^ B | | - | 13 14 | - |  
-^ C |  ​+ ​   ​+  ​  ​  ​+  ​   ​  +^ C | 11 13 | - | | - | - |  
-^ D |    ​+ ​ ​+  ​    +  ​  +^ D | - | | - | 18 | - |  
-^ E |    ​+ ​   ​ ​+  ​  ​  ​+  ​+^ E | - | 14 | - | 18 | - | 19 |  
-^ F |          ​+  ​ -  ​|+^ F | - | - | - | - | 19 | -  
  
 **b)** **b)**
 ^0=A ^1=B ^2=C ^3=D ^4=E ^5=F ^6 ^7 ^8 ^9 ^10^ 11 ^12 ^13 ^ ^0=A ^1=B ^2=C ^3=D ^4=E ^5=F ^6 ^7 ^8 ^9 ^10^ 11 ^12 ^13 ^
-0|6|8|10|12|0|0|4|0|1|7|9|3|5|+| 6 | 8 | 10 | 12 | 13 | 0 | 4 | 0 | 1 | | 3 | 5 |
  
 **c)** **c)**
-==binärer ​Suchbaum:==+Binärer ​Suchbaum:
 <​code>​ <​code>​
        7        7
      / ​  \      / ​  \
     2     7     2     7
-   / \     ​+   / \      
-    ​   12 + ​1 ​        12 
-   \       +      / ​    
-    ​2     +     2    7 
-          +            
-           ​+             ​
-          /  +            /  
-         ​+          
-        /+         ​/
        7        7
 </​code>​ </​code>​
  
-==ternärer ​Suchbaum:==+Ternärer ​Suchbaum:
 <​code>​ <​code>​
-         +           
-       |  \ +          /| 
-   ​2 ​    ​  ​12  +        /  |   \ 
- / | \   ​  ​+      /    7    \ 
-1  2  5   +    /      |      ​
-           ​+   ​2 ​      ​     12  
-           ​8+ / | \     ​    ​
 +1  2  5   ​    ​
 +               ​
 +              8
 </​code>​ </​code>​
  
 **d)** **d)**
 ^0^1^2^3^4^5^6 ^7 ^8 ^9 ^10^ 11 ^12 ^13 ^14^ ^0^1^2^3^4^5^6 ^7 ^8 ^9 ^10^ 11 ^12 ^13 ^14^
-| 13|10|8|7|9|6|2|4|1|8|3|5| | | |+| 13 | 10 | 8 | 7 | 9 | 6 | 2 | 4 | 1 | 8 | 3 | 5 | | | |
  
-Ja+* **Ja**