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)

0123456 7 8 9 10 11 12 13 14
13 10 8 7 9 6 2 4 1 8 3 5

* Ja