Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen (Übersicht)
Inhaltsverzeichnis
Forendiskussionen
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
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
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