Sie befinden sich hier: Termine » 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 - 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

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

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

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

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 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)

  • J → B → D → I → H → K
  • G → E → J

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

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