===== Forendiskussionen =====
* [[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/7083-Graphen-31-07-2008]]
* [[https://fsi.informatik.uni-erlangen.de/forum/thread/7082-ADT-31-07-2008]]
* [[https://fsi.informatik.uni-erlangen.de/forum/thread/8828-31-Juli-2008-Aufgabe-7]]
* [[https://fsi.informatik.uni-erlangen.de/forum/thread/8844-Klausur-31-07-2008]] 1c,3a,5b, 6b,c,d
===== Lösungsversuch =====
==== Aufgabe 1 - Rucksack ====
**a)**
^ ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^ 12 ^
^ 1 | - | [+] | / | / | / | / | / | / | / | / | / | / | / |
^ 4 | - | - | / | / | + | [+] | / | / | / | / | / | / | / |
^ 7 | - | - | / | / | - | - | / | + | + | / | / | + | [+] |
^ 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
**c)**
for(int i = 1; i < n; i++) { // Zeilen
for(int j = 0; j <= m; j++) { // Spalten
// Fall P(n - 1, K): Gibt es in der Zelle direkt darüber eine Lösung,
// dann ist P(n, K) = P(n - 1, K)
// 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;
}
}
}
Vollständiges Programm: \\
{{:pruefungen:bachelor:aud:rucksack.java.txt|:pruefungen:bachelor:aud:rucksack.java.txt}}
==== Aufgabe 2 - ADT ====
**a)**
create, add, remove, removeAll
Es wurde nach Konstruktoren gefragt, aber remove und removeAll sind doch nur Hilfskonstruktoren? (Vorlesung 10, Folie 10-10)
**b)**
contains(x, create) = 0
contains(x, add(x, M)) = 1 + contains(x, M)
contains(x, add(y, M)) = contains(x, M)
**c)**
remove(x, create) = create
remove(x, add(x, M)) = M
remove(x, add(y, M)) = add(y, remove(x, M))
**d)**
removeAll(x, create) = create
removeAll(x, add(x, M)) = removeAll(x, M)
removeAll(x, add(y, M)) = add(y, removeAll(x, M))
==== Aufgabe 3 - Java====
a)
* statisch: A, dynamisch: A
* statisch: A, dynamisch: AA
* statisch: B, dynamisch: B
b)
* **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)
* **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, die Hash-Funktion ist genauso schlecht, da sie Werte mit der gleichen letzten Ziffer ebenfalls dem selben Bucket zuteilt.
**c)**
* **Ja**
* **Ja**
* **Nein**, offene Adressierung bedeutet geschlossenes Hashing
* **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 - Sortieren ====
**a)**
// merge von MergeSort
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;
}
**c)**
* **Ja**
==== Aufgabe 6 - Suchen ====
**a)**
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);
}
}
**b)**
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;
}
**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)**
* **Nein**, es haben mehr als 2 Knoten einen ungeraden Grad
* **Ja**, jeder Knoten ist von jedem anderen aus erreichbar
* **Ja**
* **Nein**, Knoten G hat den Grad 6
* **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 ^ C ^D ^ E ^ G ^ H ^ I ^ J ^ K ^
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | [0] | ∞ |
| 10 | ∞ | ∞ | [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 | 53 | [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 |
\\
Kanten (in dieser Reihenfolge): \\
JE, JB, BD, DC, DI, IH, EG, HK
**c)**
* **Nein**, im neuen Spannbaum würde beispielsweise die Kante ED vorkommen, die aktuell nicht vorkommt
* **Ja**
* **Nein**
**d)**
^ nach Knoten ^ Weglänge ^ Route ^
| K | 60 | J -> B -> D -> I -> H -> K |
| G | 53 | J -> E -> G |
**e)**
CD, AB, ID, EJ, BD, BJ, HG, KH, EF, HI
**f)**
CD, DI, DB, BA, BJ, JE, EF, IH, HG, HK
==== Aufgabe 8 - wp-Kalkül ====
**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;", 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:
7
/ \
2 7
/ \ \
1 5 12
/ /
2 7
\
9
/
8
/
7
Ternärer Suchbaum:
7
/| \
/ | \
/ 7 \
/ | \
2 7 12
/ | \ | /
1 2 5 7 9
/
8
**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**