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:loesungss08 [15.02.2013 13:56] – Dawodopruefungen:bachelor:aud:loesungss08 [23.03.2015 15:00] – Aufgabe 9c) ergänzt, vorher nicht vorhanden. cf AuD-VL 6-16ff bor1
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
Zeile 72: Zeile 72:
   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 95:
   * **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 138:
 ^ 9 | 47 | S | ^ 9 | 47 | S |
  
-=== Aufgabe 5 ===+==== Aufgabe 5 - Sortieren ====
  
 **a)** **a)**
Zeile 185: Zeile 185:
   * **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, p, start, 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 | 
 +| G | 53 | J -> E -> G |
  
 **e)** **e)**
Zeile 263: Zeile 289:
 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 3 hat kein x und y.+Option ist korrekt \\ 
 +\\ 
 +Nummer 1 geht nicht, da sie vor der Schleife nicht erfüllt ist 
 +Nummer 3 geht nicht, da sie werde x noch y 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 | - | 6 | 11 | - | - | - | 
-^ B |  +  |  -  |   +  |  +  | +  |  - | +^ B | 6 | - | 13 | 8 | 14 | - |  
-^ C |  +   |  +  |   -  |  +  |  -   |  -  | +^ C | 11 | 13 | - | 4 | - | - |  
-^ D |  -  |  + |  +  |  -  |   +  |  -  | +^ D | - | 8 | 4 | - | 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 | 6 | 8 | 10 | 12 | 13 | 0 | 4 | 0 | 1 | 1 | 2 | 3 | 5 |
  
 **c)** **c)**
-==binärer Suchbaum:==+Binärer Suchbaum:
 <code> <code>
        7        7
      /   \      /   \
     2     7     2     7
-   / \     \ +   / \      \ 
-  1   5    12 + 1    5      12 
-   \       / +      /     / 
-    2     7 +     2    7 
-          \ +            \ 
-           9 +             9 
-          /  +            /  
-         8 +          8 
-        /+         /
        7        7
 </code> </code>
  
-==ternärer Suchbaum:==+Ternärer Suchbaum:
 <code> <code>
-         7 +           7 
-      /  |  \ +          /| \ 
-   2     7   12  +        /  |   \ 
- / | \   |   / +      /    7    \ 
-1  2  5  7  9 +    /      |      \ 
-           / +   2       7      12  
-           8+ / | \     |     / 
 +1  2  5   7     9 
 +               / 
 +              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**