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:loesungss08 [23.07.2012 15:15] – Aufgabe 7 hinzugefügt matze_pruefungen:bachelor:aud:loesungss08 [25.05.2017 13: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 - Rucksackproblem === 
 **a)** **a)**
 ^    ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^ 12 ^ ^    ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^ 12 ^
-^ 1 |  -  |  + | /  |  / |  /  | /  |  / |  /  |  /  |  /  |   /   |  /  |  /  | +^ 1 | - | [+] | / | / | / | / | / | / | / | / | / | / | / | 
-^ 4 |  -  |  -  | /  |  / |[+] | + |  / |  /  |  /  |  /  |   /   |  /  |  /  | +^ 4 | - | - | / | / | + | [+] | / | / | / | / | / | / | / | 
-^ 7 |  -  |  -  | /  |  / |  -  |  - |  / |  + |  + |  /  |   /   |  + |  + | +^ 7 | - | - | / | / | - | - | / | + | + | / | / | + | [+] | 
-^ 8 |  -  |  -  | /  |  / |  -  |  - |  / |  -  |[+] |  + |   /   |  -  |[+]|+^ 8 | - | - | / | / | - | - | / | - | - | + | / | - | [-] | 
 + 
 +**b)** \\ 
 +Gesucht: Lösung für Rucksack der Größe 12 \\ 
 +Elemente mit den Größen 1, 4, 7 (Pfad mit eckigen Klammern in der Tabelle aus a) markiert) \\ 
 +  Algorithmus: 
 +  P(4, 12) -> k_4 = 8 gehört nicht rein -> P(4, 12) 
 +  P(3, 12) -> k_3 = 7 gehört rein -> P(3, 12 - 7) 
 +  P(2, 5) -> k_2 = 4 gehört rein -> P(2, 5 - 4) 
 +  P(1, 1) -> k_1 = 1 gehört rein -> Rucksack vollständig gefüllt
  
-**b)** 
-8, 4 
-In Tabelle von a) mittels [] eingekreist. 
  
 **c)** **c)**
 <code java> <code java>
-for(int i = 1; i < n; i++) {            // Zeilen +for(int i = 1; i < n; i++) { // Zeilen 
-    for(int j = 0; j < m + 1; j++) {    // Spalten + for(int j = 0; j <= m; j++) { // Spalten 
-        if((tab[i][j] == OHNE || tab[i][j] == MIT) && i < n-1) { // Wenn in einer Zeile MIT oder OHNE steht +  
-            tab[i+1][j] = OHNE;         // so muss die Zelle daraunter den Wert OHNE haben. + // Fall P(n - 1, K): Gibt es in der Zelle direkt darüber eine Lösung, 
-            if(j + k[i+1] <= m) + // dann ist P(n, K) = P(n - 1, K) 
-                tab[i+1][j+k[i+1]] = MIT; + // Das aktuelle Elemente gehört somit nicht zur Lösung -> OHNE 
-        } + if(tab[i - 1][j] != UNMOEGLICH) { 
-    }+ tab[i][j] = OHNE; 
 + 
 + // Fall P(n - 1, K - k_n): Gibt es in der Zeile darüber, nach links versetzt 
 + // eine Lösung (Achtung: ArrayIndexOutOfBoundsException), dann ist 
 + // P(n, K) = P(n - 1, K) + k_n 
 + // Das aktuelle element gehört somit zur Lösung -> MIT 
 + } else if(elements[i] <= j && tab[i - 1][j - elements[i]] != UNMOEGLICH) { 
 + tab[i][j] = MIT; 
 + } 
 + }
 } }
 </code> </code>
  
-=== Aufgabe 2 - ADT ===+Vollständiges Programm: \\ 
 +{{:pruefungen:bachelor:aud:rucksack.java.txt|:pruefungen:bachelor:aud:rucksack.java.txt}} 
 + 
 +==== Aufgabe 2 - ADT ====
 **a)** **a)**
-<code> +  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)
-</code>+
  
 **b)** **b)**
- +  contains(x, create) = 0 
-<code> +  contains(x, add(x, M)) = 1 + contains(x, M) 
-A1: contains(x, create) = 0 +  contains(x, add(y, M)) = contains(x, M)
-A2: contains(x,add(y,M)) = {1+contains(x,M)     falls x = y +
-                           {0+contains(x,M)     sonst +
-</code>+
  
 **c)** **c)**
-<code> +  remove(x, create) = create 
-A3: remove(x, create) = create +  remove(x, add(x, M)) = M 
-A4: remove(x,add(y,M)) = M                      falls x==y +  remove(x, add(y, M)) = add(y, remove(x, M))
-                         add(y, remove(x, M))   sonst +
-</code>+
  
 **d)** **d)**
-<code> +  removeAll(x, create) = create 
-A5: removeAll(x,create) = create +  removeAll(x, add(x, M)) = removeAll(x, M) 
-A6: removeAll(x,add(y,M)) = add(y, removeAll(x, M))     falls x!=y +  removeAll(x, add(y, M)) = add(y, removeAll(x, M))
-                            removeAll(x, M)            sonst +
-</code>+
  
-=== Aufgabe 3 ===+==== Aufgabe 3 - Java====
 a) a)
   * statisch: A, dynamisch: A   * statisch: A, dynamisch: A
Zeile 69: Zeile 80:
  
 b)  b) 
-Nein, nein, ja, ja, ja, nein, nein, nein+  * **Nein** 
 +  * **Nein** 
 +  * **Ja** 
 +  * **Ja** 
 +  * **Ja** 
 +  * **Nein** 
 +  * **Nein** 
 +  * **Nein** 
 + 
 +Datei zum selbst Ausprobieren: \\ 
 +{{:pruefungen:bachelor:aud:test-07-08.java.txt|:pruefungen:bachelor:aud:test-07-08.java.txt}}
  
 c) c)
-6, 8 +  * **6** 
-=== Aufgabe 4 - Hashes ===+  * **8** 
 + 
 +==== 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 91: Zeile 114:
  
 **b)** **b)**
-Nein, diese hat eine schlechte Verteilung und erzeugt somit viele Kollisionen.+Nein, die Hash-Funktion ist genauso schlecht, da sie Werte mit der gleichen letzten Ziffer ebenfalls dem selben Bucket zuteilt.
  
 **c)** **c)**
-  * Ja +  * **Ja** 
-  * Ja +  * **Ja** 
-  * Ja?? +  * **Nein**, offene Adressierung bedeutet geschlossenes Hashing 
-  * Ja+  * **Ja**
  
 **d)** **d)**
Zeile 116: Zeile 139:
 ^ 9 | 47 | S | ^ 9 | 47 | S |
  
-=== Aufgabe 5 ===+==== Aufgabe 5 - Sortieren ====
  
 +**a)**
 <code java> <code java>
-    // a) wie bei Mergesort, der Mergeteil: +// merge von MergeSort 
-    private static Photo[] combinePhotos(Photo[] p1, Photo[] p2){ +private static Photo[] combinePhotos(Photo[] p1, Photo[] p2) { 
-        Photo[] m = new Photo[p1.length + p2.length]; + Photo[] m = new Photo[p1.length + p2.length]; 
-        int l = 0; + int l = 0; 
-        int r = 0;   + int r = 0; 
-        int k = 0; + int k = 0;
-        while (l < p1.length && r < p2.length){ +
-            if (p1[l].compareTo(p2[r]) < 0){  +
-                m[k++] = p1[l++]; +
-            }    +
-            else { +
-                m[k++] = p2[r++]; +
-            }    +
-        }    +
-        while(l < p1.length){ +
-            m[k++] = p1[l++]; +
-        }    +
-        while(r < p2.length){ +
-            m[k++] = p2[r++]; +
-        }    +
-        return m; +
-    }    +
-    // b) +
-    public Photo[] getAllPhotosSorted(){ +
-        Photo[] result = myPhotos; +
-        for (int i = 0; i < myAlbums.length; i++){ +
-            result = combinePhotos(result, myAlbums[i].getAllPhotosSorted()); +
-        }    +
-        return result; +
-    }   +
  
 + while (l < p1.length && r < p2.length) {
 + if (p1[l].compareTo(p2[r]) < 0) {
 + m[k++] = p1[l++];
 + } else {
 + m[k++] = p2[r++];
 + }
 + }
 +
 + while (l < p1.length) {
 + m[k++] = p1[l++];
 + }
 +
 + while (r < p2.length) {
 + m[k++] = p2[r++];
 + }
 +
 + return m;
 +}
 </code> </code>
  
-===Aufgabe 6===+**b)**
 <code java> <code java>
-    // a) +public Photo[] getAllPhotosSorted() { 
-    private static int findPhotoForDate(Date d, Photo[] p, int start, int end){ + Photo[] result = myPhotos; 
-        // kann Date nicht finden + 
-        if (end > start) { + for (int i = 0; i < myAlbums.length; i++) { 
-            return -1;  + result = combinePhotos(result, myAlbums[i].getAllPhotosSorted()); 
-        }    + } 
-        int mid = (end+start) / 2; + 
-        if (d.equals(p[mid].date)){ + return result; 
-            return mid; +}
-        } else if (d.compareTo(p[mid].date) < 0){  +
-            return findPhotoForDate(d, p, start, mid-1); +
-        } else { +
-            return findPhotoForDate(d, p, mid+1, end);   +
-        }    +
-    }    +
-    // b) hier suchen wir linear nach dem start und end index, das koennte +
-    // man natuerlich auch mit binary search implementieren, dann waers O(log n),  +
-    // aber war nicht verlangt +
-    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===+**c)** 
 +  * **Ja** 
 + 
 +==== Aufgabe 6 - Suchen ==== 
 + 
 +**a)** 
 +<code java> 
 +private static int findPhotoForDate(Date d, Photo[] p, int start, int end) { 
 + int mid = (end + start) / 2; 
 + 
 + if (start > end) 
 + return -1; 
 + 
 + if(p[mid].moreRecentThan(d) == 0) { 
 + return mid; 
 + 
 + // Photo[mid] wurde vor dem gewünschten Datum erstellt 
 + // gesuchtes Photo muss "rechts" davon sein 
 + } else if(p[mid].moreRecentThan(d) < 0) {  
 + return findPhotoForDate(d, p, mid + 1, end); 
 + 
 + // Photo[mid] wurde nach dem gewünschten Datum erstellt 
 + // gesuchtes Photo muss "links" davon sein 
 + } else { 
 + return findPhotoForDate(d, p, start, mid - 1); 
 + } 
 +}  
 +</code> 
 + 
 +**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**, 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)**
-  * K -> 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)**
-CD, AB, ID, EJ, BJ, AC, HG, KH, Ef, HI+CD, AB, ID, EJ, BD, BJ, HG, KH, EF, HI
  
 **f)** **f)**
 CD, DI, DB, BA, BJ, JE, EF, IH, HG, HK CD, DI, DB, BA, BJ, JE, EF, IH, HG, HK
  
-===Aufgabe 9=== +==== Aufgabe 8 - wp-Kalkül ==== 
-  * **a)** O(n) , O(n^2) ?, O( n^2), O(n log n), O(n) +**a)** 
-  * **b)** O(1) , O(n), O(2^n)+  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;", a + (7 - a) = 7 ∧ (7 - a) = 3) =  
 +  ((4*b) + (7 - (4*b)) = 7 ∧ (7 - (4*b)) = 3) =  
 +  (7 = 7 ∧ 7 - 3 = 4*b) =  
 +  (true ∧ 4 = 4*b) =  
 +  (4 = 4*b) =  
 +  (1 = b) 
 + 
 + 
 +**b)** 
 +  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)] =  
 +  [(a > b) ∧ (a = 7 ∧ a = 3)] ∨ false =  
 +  (a > b) ∧ false =  
 +  false 
 + 
 + 
 +**c)** 
 +2.\\ 
 +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)** 
 + 
 +  wp("y = 1; i = x;", y = 2^(x+1-i) - 1) = 
 +  wp("y = 1;", y = 2^(x+1-x) - 1) = 
 +  (1 = 2^(x+1-x) - 1) = 
 +  (1 = 2^(1) - 1) = 
 +  (1 = 2 - 1) = 
 +  (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)** 
 +  ... 
 +  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+1 = 2^(x+1-i+1) -1) 
 +  (y*2) +1 = 2^(x+1-i+1) -1 
 +  y = 1^(x+2+1) -1  
 +  ... 
 + 
 +==== Aufgabe 9 - O-Kalkül ==== 
 +**a)**  
 +    * **O(n)** 
 +    * **O(n^2)** 
 +    * **O(n^2)** 
 +    * **O(n log n)** 
 +    * **O(n)** 
 + 
 +**b)**  
 +    * **O(1)** 
 +    * **O(n)** 
 +    * **O(2^n)** 
 + 
 +**c)** 
 +    * **Nein** 
 +    * **Ja** 
 + 
 +==== Aufgabe 10 - Darstellung von Graphen ==== 
 +**a)** 
 + 
 +**Adjazenzmatrix** 
 + 
 +|     ^ A ^ B ^ C ^ D ^ E ^ F ^ 
 +^ A | - | 6 | 11 | - | - | - | 
 +^ B | 6 | - | 13 | 8 | 14 | - |  
 +^ C | 11 | 13 | - | 4 | - | - |  
 +^ D | - | 8 | 4 | - | 18 | - |  
 +^ E | - | 14 | - | 18 | - | 19 |  
 +^ F | - | - | - | - | 19 | - |   
 + 
 +**b)** 
 +^0=A ^1=B ^2=C ^3=D ^4=E ^5=F ^6 ^7 ^8 ^9 ^10^ 11 ^12 ^13 ^ 
 +| 6 | 6 | 8 | 10 | 12 | 13 | 0 | 4 | 0 | 1 | 1 | 2 | 3 | 5 | 
 + 
 +**c)** 
 +Binärer Suchbaum: 
 +<code> 
 +       7 
 +     /   \ 
 +    2     7 
 +   / \      \ 
 + 1    5      12 
 +      /     / 
 +     2    7 
 +            \ 
 +             9 
 +            /  
 +          8 
 +         / 
 +       7 
 +</code> 
 + 
 +Ternärer Suchbaum: 
 +<code> 
 +           7 
 +          /| \ 
 +        /  |   \ 
 +      /    7    \ 
 +    /      |      \ 
 +   2       7      12  
 + / | \     |     / 
 +1  2  5   7     9 
 +               / 
 +              8 
 +</code> 
 + 
 +**d)** 
 +^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 | | | | 
 + 
 +* **Ja**