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.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungss08 [28.07.2012 16:02] – Aufgabe 10 hinzugefügt matze_ | pruefungen:bachelor:aud:loesungss08 [15.02.2013 15:18] – Dawodo | ||
---|---|---|---|
Zeile 9: | Zeile 9: | ||
==== Lösungsversuch ==== | ==== Lösungsversuch ==== | ||
- | === Aufgabe 1 - Rucksackproblem | + | === Aufgabe 1 - Rucksack |
**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 | + | |
- | | + | // 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) |
- | | + | // Das aktuelle Elemente gehört somit nicht zur Lösung -> OHNE |
- | } | + | if(tab[i |
- | } | + | 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), | ||
+ | // 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][j] = MIT; | ||
+ | } | ||
+ | } | ||
} | } | ||
</ | </ | ||
+ | |||
+ | Vollständiges Programm: \\ | ||
+ | {{: | ||
=== Aufgabe 2 - ADT === | === Aufgabe 2 - ADT === | ||
**a)** | **a)** | ||
- | < | + | |
- | create, add, remove, removeAll | + | |
- | </ | + | |
**b)** | **b)** | ||
- | + | | |
- | < | + | 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, | + | |
- | {0+contains(x, | + | |
- | </ | + | |
**c)** | **c)** | ||
- | < | + | |
- | A3: remove(x, create) = create | + | remove(x, add(x, M)) = M |
- | A4: remove(x, | + | remove(x, add(y, M)) = add(y, remove(x, M)) |
- | add(y, remove(x, M)) sonst | + | |
- | </ | + | |
**d)** | **d)** | ||
- | < | + | |
- | A5: removeAll(x, | + | removeAll(x, |
- | A6: removeAll(x, | + | |
- | | + | |
- | </ | + | |
=== Aufgabe 3 === | === Aufgabe 3 === | ||
Zeile 69: | Zeile 79: | ||
b) | b) | ||
- | Nein, nein, ja, ja, ja, nein, nein, nein | + | * **Nein** |
+ | * **Nein** | ||
+ | * **Ja** | ||
+ | * **Ja** | ||
+ | * **Ja** | ||
+ | * **Nein** | ||
+ | * **Nein** | ||
+ | * **Nein** | ||
+ | |||
+ | Datei zum selbst Ausprobieren: | ||
+ | {{: | ||
c) | c) | ||
- | 6, 8 | + | * **6** |
+ | * **8** | ||
=== Aufgabe 4 - Hashes === | === Aufgabe 4 - Hashes === | ||
**a)** | **a)** | ||
Zeile 91: | Zeile 113: | ||
**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?? | + | * **Nein**, offene Adressierung bedeutet geschlossenes Hashing |
- | * Ja | + | |
**d)** | **d)** | ||
Zeile 118: | Zeile 140: | ||
=== Aufgabe 5 === | === Aufgabe 5 === | ||
+ | **a)** | ||
<code java> | <code java> | ||
- | | + | // 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; | + | |
- | result = combinePhotos(result, | + | |
- | } | + | |
- | 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; | ||
+ | } | ||
</ | </ | ||
- | ===Aufgabe 6=== | + | **b)** |
<code java> | <code java> | ||
- | // a) | + | public |
- | private static int findPhotoForDate(Date d, Photo[] | + | Photo[] result = myPhotos; |
- | // kann Date nicht finden | + | |
- | if (end > start) { | + | for (int i = 0; i < myAlbums.length; i++) { |
- | | + | result |
- | } | + | } |
- | int mid = (end+start) / 2; | + | |
- | if (d.equals(p[mid].date)){ | + | return result; |
- | return mid; | + | } |
- | } else if (d.compareTo(p[mid].date) < 0){ | + | |
- | | + | |
- | } else { | + | |
- | return findPhotoForDate(d, | + | |
- | } | + | |
- | } | + | |
- | // b) hier suchen wir linear nach dem start und end index, das koennte | + | |
- | // man natuerlich auch mit binary search implementieren, | + | |
- | // aber war nicht verlangt | + | |
- | public static Photo[] findAllPhotosForDate(Date d, Photo[] p){ | + | |
- | | + | |
- | if (index == -1) { | + | |
- | return new Photo[0]; | + | |
- | } | + | |
- | // suche startindex | + | |
- | int start = index; | + | |
- | while (start >=0 && p[start].date.equals(d)) { | + | |
- | | + | |
- | } | + | |
- | // suche endindex | + | |
- | int end = index+1; | + | |
- | while (end < p.length && p[end].date.equals(d)) { | + | |
- | end++; | + | |
- | } | + | |
- | | + | |
- | System.arraycopy(p, | + | |
- | return result; | + | |
- | } | + | |
</ | </ | ||
- | | + | |
- | | + | **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 " | ||
+ | } else if(p[mid].moreRecentThan(d) < 0) { | ||
+ | return findPhotoForDate(d, | ||
+ | |||
+ | // Photo[mid] wurde nach dem gewünschten Datum erstellt | ||
+ | // gesuchtes Photo muss " | ||
+ | } else { | ||
+ | return findPhotoForDate(d, | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | **b)** | ||
+ | |||
+ | <code java> | ||
+ | public static Photo[] findAllPhotosForDate(Date d, Photo[] p) { | ||
+ | int index = findPhotoForDate(d, | ||
+ | if (index == -1) | ||
+ | return new Photo[0]; | ||
+ | |||
+ | // suche Startindex | ||
+ | int start = index; | ||
+ | while (start >= 0 && p[start].moreRecentThan(d) == 0) { | ||
+ | start--; | ||
+ | } | ||
+ | start++; | ||
+ | |||
+ | // 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, | ||
+ | |||
+ | return result; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | **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=== | ===Aufgabe 7=== | ||
**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 | + | |
- | * Ja | + | |
- | * Nein | + | |
**d)** | **d)** | ||
- | * K -> B -> D -> I -> H -> K | + | ^ nach Knoten ^ Weglänge ^ Route ^ |
- | | + | | 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)** | ||
Zeile 232: | Zeile 291: | ||
===Aufgabe 8 - WP=== | ===Aufgabe 8 - WP=== | ||
**a)** | **a)** | ||
- | < | + | 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;' | + | wp("a = 4*b;", |
- | wp(4b + 7 - 4b = 7 ^ 7 - 4b = 3 | + | ((4*b) + (7 - (4*b)) |
- | </ | + | (7 = 7 ∧ 7 - 3 = 4*b) = |
+ | (true ∧ 4 = 4*b) = | ||
+ | (4 = 4*b) = | ||
+ | (1 = b) | ||
**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)] = |
- | wp(' | + | [(a > b) ∧ (a = 7 ∧ a = 3)] ∨ false = |
- | [a>b] ^ wp(' b=a;', | + | (a > b) ∧ false = |
- | wp(b=7) | + | |
- | b=7 | + | |
- | </ | + | |
**c)** | **c)** | ||
- | 2. Option ist korrekt! | + | 2. Option ist korrekt |
- | 1 geht nicht, da sie vor der Schleife nicht erfüllt ist und 3 hat kein x und y. | + | \\ |
+ | Nummer | ||
+ | Nummer | ||
**d)** | **d)** | ||
- | < | + | |
- | 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) = |
- | </ | + | (1 = 1) = |
+ | true | ||
+ | |||
+ | | ||
+ | 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)** | ||
- | < | + | ... |
- | 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 |
- | </ | + | ... |
===Aufgabe 9=== | ===Aufgabe 9=== | ||
- | * **a)** | + | **a)** |
- | * O(n) | + | |
- | * O(n^2) | + | |
- | * O( n^2) | + | |
- | * O(n log n) | + | |
- | * O(n) | + | |
- | | + | |
- | * O(1) | + | **b)** |
- | * O(n) | + | |
- | * O(2^n) | + | |
+ | | ||
===Aufgabe 10 - Graphen=== | ===Aufgabe 10 - 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 | + | Binärer |
< | < | ||
7 | 7 | ||
/ | / | ||
2 7 | 2 7 | ||
- | / \ | + | / \ \ |
- | 1 | + | |
- | \ / | + | / |
- | | + | 2 7 |
- | \ | + | \ |
- | | + | |
- | / | + | / |
- | | + | 8 |
- | / | + | |
7 | 7 | ||
</ | </ | ||
- | ==ternärer | + | Ternärer |
< | < | ||
- | 7 | + | 7 |
- | / | \ | + | /| \ |
- | | + | / | \ |
- | / | \ | + | / 7 \ |
- | 1 2 5 7 9 | + | / | |
- | | + | |
- | | + | / | \ |
+ | 1 2 5 | ||
+ | | ||
+ | 8 | ||
</ | </ | ||
**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 |