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

a) falsch

b) 3 - eine Schleife korrekt ist

c) richtig

d) richtig

e) Bucketsort, Mergesort

f) 1 - exakt n-1 Kanten

g) 4 - O(n² * log n)

h) O(n*(log n)²)

i) 1 - kontextsensitiven Grammatiken

Aufgabe 2 - Graphen

a)

A B C D E F Prioritäts-Warteschlange
[0] ∞ ∞ ∞ ∞ ∞ A
0 [4] 5 ∞ ∞ ∞ B,C
0 4 [5] ∞ 5 ∞ C,E
0 4 5 7 [5] ∞ E,D
0 4 5 [6] 5 10 D,F
0 4 5 6 5 [10] F
0 4 5 6 5 10

b)

  • nach B: 4
  • nach C: 5
  • nach D: 6
  • nach E: 5
  • nach F: 10
Aufgabe 3 - Java

a) Java Datei zum selber testen: :pruefungen:bachelor:aud:test.java.txt

ZeileBildschirmausgabe bzw. keine Ausgabe
23 BA
24 AB
27 keine Ausgabe
31 BB
38 CC
39 AA

b)

ZeileBegrundung
7 Compiler: f implementiert nicht die Methode f des Interfaces
19 Compiler: keine cast von double auf int im return Statement
34 Compiler: Instanzvariablen können nicht über den statischen Typ angesprochen werden (nicht A sondern a)
40 Compiler: Man kann nicht von der Ober- auf die Unterklasse konvertieren, nur andersherum
44 Compiler: g ist eine private-Methode. Darauf kann man nicht von i aus zugreifen
Aufgabe 4 - ADT

a) A4: contains(x, create) = false 

A5: contains(x, append(y,l))= 1+contains(x,l)       //falls x=y
                             contains(x,l)          //falls x!=y

b) A → D → create

c) VORSICHT! nicht wirklich sicher!

A1: append(head(append(D, create), append(A, create))

A1: append(head(prepend(D, create), prepend(A, create))

A3: append(D, prepend(A, create)

A2: prepend(A, append(D, create)

A1: prepend(A, prepend(D, create)

Aufgabe 5 - Pseudo-Zufallszahlen

a) 

public static int f(int n) {
	if (n < 3)
		return n + 1;
	else
		return 1 + (((f(n - 1) - f(n - 2)) * f(n - 3)) % 100);
}

b) 

public static int f(int n) {
	return lin(1, 2, 3, n);
}
private static int lin(int a, int b, int c, int steps) {
	if (steps == 0)
		return a;
	else {
		return lin(b,c,1+(((c-b)*a)%100),steps-1);
	}
}

c) 

public static int f(int n) {
	int a = 1, b = 2, c = 3;
	while (n > 0) {
		int tmp = a;
		a = b;
		b = c;
		c = 1 + (((b-a)*tmp)%100);
		n--;
	}
	return a;
}
Aufgabe 6 - Suchbäume

a) 

     27
    /  \
  23	42
 /      / \
7     32  64
            \
             81

b) Schlusselfolge für maximale Höhe: 7, 23, 27, 32, 42, 64, 81 Kosten: O (n²)

Schlusselfolge für minimale Höhe: 32, 64, 42, 81, 23, 7, 27 Kosten: O (n * log n)

c)

:pruefungen:bachelor:aud:ws08-6-c.png

d)

:pruefungen:bachelor:aud:ws08-6-d.png

Rotation an: 64

Einfachrotation, da 81 und 64 links gedreht werden.

Aufgabe 7 - Heap

a) Für jeden Knoten außer der Wurzel gilt A[Vater[i]] >= A[i]

b) 

    13
  6    9
2  5  8

c) 

public int leftChildIndex (int parentIndex) {
     return parentIndex*2+1;
}

d) 

public int parentIndex (int childIndex) {
     return (childIndex-1)/2;
}

e) 

//keine garantie!
public void add (int priority) {
 
   array[n] = priority;
 
   while( j !=0) {
 
        int i = n;
        int j = parentIndex(n);
 
        if( priority > array[j] ) {
              array[i] = array[j];
              array[j] = priority;
        } else {
             break;
        }
    }
 
    n++;
}

f) O(log n)

Aufgabe 8 (wp)

a) a > b-5 && true ⇒ a > b-5