FSI-Zimmer: offen
Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen (Übersicht)
Dies ist eine alte Version des Dokuments!
forum
Lösungsversuch
Aufgabe 1 - Rucksackproblem
a)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | - | [+] | / | / | / | / | / | / | / | / | / | / | / |
| 4 | - | - | / | / | [+] | + | / | / | / | / | / | / | / |
| 7 | - | - | / | / | - | - | / | [+] | + | / | / | + | + |
| 8 | - | - | / | / | - | - | / | - | - | + | / | - | - |
b) 1,4,7 In Tabelle von a) mittels [] eingekreist.
c)
for(int i = 1; i < n; i++) { // Zeilen for(int j = 0; j < m + 1; 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. if(j + k[i+1] <= m) tab[i+1][j+k[i+1]] = MIT; } } }
Aufgabe 2 - ADT
a)
create, add, remove, removeAll
b)
A1: contains(x, create) = 0
A2: contains(x,add(y,M)) = {1+contains(x,M) falls x = y
{0+contains(x,M) sonst
c)
A3: remove(x, create) = create
A4: remove(x,add(y,M)) = M falls x==y
add(y, remove(x, M)) sonst
d)
A5: removeAll(x,create) = create
A6: removeAll(x,add(y,M)) = add(y, removeAll(x, M)) falls x!=y
removeAll(x, M) sonst
Aufgabe 3
a)
- statisch: A, dynamisch: A
- statisch: A, dynamisch: AA
- statisch: B, dynamisch: B
b) Nein, nein, ja, ja, ja, nein, nein, nein
c) 6, 8
Aufgabe 4 - Hashes
a)
| x = | 7 | 26 | 27 | 4 | 47 | 9 | 6 | 36 | 17 | 57 | 56 | 42 | 10 | 77 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| (3x+2)%10 = | 3 | 0 | 3 | 4 | 3 | 9 | 0 | 0 | 3 | 3 | 0 | 8 | 2 | 3 |
| Bucket | verkettete Liste |
|---|---|
| 0 | 26 → 6 → 36 → 56 |
| 1 | |
| 2 | 10 |
| 3 | 7 → 27 → 47 → 17 → 57 → 77 |
| 4 | 4 |
| 5 | |
| 6 | |
| 7 | |
| 8 | 42 |
| 9 | 9 |
b) Nein, diese hat eine schlechte Verteilung und erzeugt somit viele Kollisionen.
c)
- Ja
- Ja
- Ja??
- Ja
d)
| x = | 4 | 7 | 26 | 27 | 47 | 42 | 10 | 56 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| (3x+2)%10 = | 4 | 3 | 0 | 3 | 3 | 8 | 2 | 0 | 9 |
| 1 + 2 (x%2) = | 1 | 3 | 1 | 3 | 3 | 1 | 1 | 1 | 3 |
| Bucket | Inhalt | Kollisionstyp |
|---|---|---|
| 0 | 26 | - |
| 1 | 56 | P |
| 2 | 10 | - |
| 3 | 7 | - |
| 4 | 4 | - |
| 5 | 9 | S |
| 6 | 27 | P |
| 7 | ||
| 8 | 42 | - |
| 9 | 47 | S |
Aufgabe 5
// a) wie bei Mergesort, der Mergeteil: private static Photo[] combinePhotos(Photo[] p1, Photo[] p2){ Photo[] m = new Photo[p1.length + p2.length]; int l = 0; int r = 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; }
Aufgabe 6
// a) private static int findPhotoForDate(Date d, Photo[] p, int start, int end){ // kann Date nicht finden if (end > start) { return -1; } int mid = (end+start) / 2; if (d.equals(p[mid].date)){ 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; }
- c) O (log n)
- d) Nein, Ja
Aufgabe 7
a)
- nein
- ja
- nein
- nein
- nein
- ??
b)
| B | C | D | E | G | H | I | J | K |
|---|---|---|---|---|---|---|---|---|
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | [0] | ∞ |
| 10 | ∞ | ∞ | [7] | ∞ | ∞ | ∞ | 0 | ∞ |
| [10] | ∞ | 25 | 7 | ∞ | ∞ | ∞ | 0 | ∞ |
| 10 | ∞ | 25 | 7 | 53 | ∞ | ∞ | 0 | ∞ |
| 10 | 23 | [18] | 7 | 53 | ∞ | ∞ | 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 |
c)
- Nein
- Ja
- Nein
d)
- K → B → D → I → H → K
- G → E → J
e) CD, AB, ID, EJ, BJ, AC, HG, KH, Ef, HI
f) CD, DI, DB, BA, BJ, JE, EF, IH, HG, HK
Aufgabe 8 - WP
a)
wp('a = 4*b; b = 7-a;', a+b = 7 ^ b = 3)
wp('a=4b;' a + 7 -a = 7 ^ 7-a = 3)
wp(4b + 7 - 4b = 7 ^ 7 - 4b = 3
b)
wp('if a > b then b=a;', a = 7 ^ b = 3)
wp('if a > b then b=a;', a= 7 ^ b = 3) o. wp(' a = 7 ^ b = 3)
[a>b] ^ wp(' b=a;', a= 7 ^ b = 3) o. wp(' a = 7 ^ b = 3)
wp(b=7)
b=7
c) 2. Option ist korrekt! 1 geht nicht, da sie vor der Schleife nicht erfüllt ist und 3 hat kein x und y.
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^(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
- a)
- O(n)
- O(n^2)
- O( n^2)
- O(n log n)
- O(n)
- b)
- O(1)
- O(n)
- O(2^n) sollte nicht O(n) stimmen?? ===Aufgabe 10 - Graphen=== a) ==Adjazenzmatrix== | ^ A ^ B ^ C ^ D ^ E ^ F ^ ^ A | - | + | + | - | - | - | ^ B | + | - | + | + | + | - | ^ C | + | + | - | + | - | - | ^ D | - | + | + | - | + | - | ^ E | - | + | - | + | - | + | ^ F | - | - | - | - | + | - | b) ^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| c) ==binärer Suchbaum:== <code> 7 / \ 2 7 / \ \ 1 5 12 \ / 2 7 \ 9 / 8 / 7 </code> ==ternärer Suchbaum:== <code> 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