Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen

Forendiskussionen

Lösungsversuch

Aufgabe 1 - Binärsuche

a) O(n)

b)

static int rateZahlSchnell(int n) {
	if(n < 0)
		return -1;
 
	int start = 0;
	int end = n;
 
	do {
		int mid = (start + end) / 2;
		int ret = testeLoesung(mid);
 
		if(ret == 0)
			return mid;
 
		if(ret > 0)
			start = mid + 1;
 
		if(ret < 0)
			end = mid - 1;
 
 
	} while(start <= end);
 
	return -1;
}
 
static int testeLoesung(int lsg) {
	int number = 42;
 
	if(lsg < number) {
		return 1;
	} else if(lsg > number) {
		return -1;
	} else {
		return 0;
	}
}

c) O(log n)

Aufgabe 2 - Graphen

a)

  • Ja
  • Ja, ein Wurzelgraph ist ein DAG mit nur einer Wurzel
  • Nein, es ist Tiefensuche
  • Nein, in O(n)
  • Nein, sie ist iterativ

b)

  • Nein, es gibt Zyklen und der Graph ist ungerichtet
  • Nein, es gibt Knoten, die mit nur einer Kante mit dem restlichen Graphen verbunden sind (Beispiel: Knoten C)
  • Nein, es gibt Zyklen
  • Ja, jeder Knoten ist von jedem anderen aus erreichbar
  • Nein, nicht jeder Knoten hat einen geraden Grad

c)

A B C D E F G H I
[0]
[10] 0 12
21 10 0 [12]
[21] 10 21 0 12
28 21 10 [21] 0 12
28 [24] 21 10 21 0 12
[25] 24 21 10 21 0 12
29 25 [27] 24 21 10 21 0 12

d) 27

e)

:pruefungen:bachelor:aud:ss08-2-e.png

AB, BD, BC, DG, GE, GI, IF, FH

f)

:pruefungen:bachelor:aud:ss08-2-f.png

BD, BC, DG, BA, FI, GE, GI, FH

Aufgabe 3 - Java

a) Java Datei zum Ausprobieren: :pruefungen:bachelor:aud:test.java-ws07.txt

Zeile Fehler bzw. Ausgabe
32 5
33 13
34 6
35 13
38 5
39 21
40 21
41 7
44 FEHLER
45 21
46 FEHLER
47 7

b)

Zeile Fehlerbeschreibung oder korrigierte Anweisung
6 fehlender Cast von double zu int
8 Vergleich („==“) statt Zuweisung („=“)
12 Variable „i“ hier nicht deklariert
14 Zuweisung („=“) statt Vergleich („==“) für booleschen Ausdruck
15 überzähliges „{“ am Ende der if-Bedingung

c) Nein, eine Instanziierung von abstrakten Klassen ist nicht möglich.

Aufgabe 4 - Arithmetische Ausdrücke - Grammatik

(nicht mehr Stoff aktueller Semester)

Aufgabe 5 - ADT

a) Primärkonstruktoren:

  • number
  • binop

Sekundärkonstruktoren (war nicht gefragt):

  • left
  • right
  • commutate

Projektionen:

  • numops

b)

  • numops(number(q)) = 0
  • numops(binop(a,op,b)) = 1 + numops(a) + numops(b)

c)

  • commutate(number(q)) = number(q)
  • commutate(binop(a,*,b) = binop(communtate(b),*,commutate(a))
  • commutate(binop(a,+,b) = binop(communtate(b),+,commutate(a))
  • commutate(binop(a,-,b) = binop(communtate(a),-,commutate(b))
  • commutate(binop(a,/,b) = binop(communtate(a),/,commutate(b))

d)

binop(left(commutate(binop(4,+,7))),*,right(binop(binop(1,-,1),+,binop(3,*,4)))) = 
//commutate// 
= binop(left(binop(7,+,4)),*,right(binop(binop(1,-,1),+,binop(3,*,4)))) = 
//right// 
= binop(left(binop(7,+,4)),*,binop(3,*,4)) = 
//left// 
= binop(7,*,binop(3,*,4)) 

e)

double left = left.evaluate();
double right = right.evaluate();
 
switch(op) {
    case '+': return left + right;
    case '-': return left - right;
    case '*': return left * right;
    case '/': return left / right;
}

Aufgabe 6 - Rucksackproblem

a)

0 1 2 3 4 5 6 7 8 9 10 11 12
1 - [+] / / / / / / / / / / /
3 - [-] / + + / / / / / / / /
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(5, 12) -> k_5 = 8 gehört nicht rein -> P(4, 12)
P(4, 12) -> k_4 = 7 gehört rein -> P(3, 12 - 7)
P(3, 5) -> k_3 = 4 gehört rein -> P(2, 5 - 4)
P(2, 1) -> k_2 = 3 gehört nicht rein -> P(1, 1)
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

d)

  • Ja
  • Ja
  • Ja, durch sukzessives Ausprobieren für Kapazitäten < m
  • Nein, das Verfahren verwendet eine Integer-DP-Tabelle bzw. greift auf Indizes basierend auf der Elementgröße zu

Aufgabe 7 - Binäre Bäume

a) Der Binärbaum muss eine totale Ordnung aufweisen:
Alle Knoten im linken Teilbaum müssen einen echt kleineren, alle im rechten Teilbaum einen echt größeren Wert als der aktuelle Knoten haben.

b)

public class BB {
	...
 
	public void einfuegen(int schluessel) {
		if(this.schluessel == schluessel)
			return;
 
		if(schluessel < this.schluessel) {
			if(left != null) {
				left.einfuegen(schluessel);
			} else {
				left = new BB(schluessel);
			}
		} else {
			if(right != null) {
				right.einfuegen(schluessel);
			} else {
				right = new BB(schluessel);
			}
		}
	}
}

c)

public class BB {
	...
 
	public int maximum() {
		if(right != null)
			return right.maximum();
 
		return schluessel;
	}
}

d) Der Wert eines Knotes in einem Max-Heap muss größer sein als der seiner Kinder.

e)

public class Heap {
	...
 
	public int maximum() {
		return schluessel;
	}
}

f) Suchbaum:
:pruefungen:bachelor:aud:02-2008-7f1.png
Max-Heap:
:pruefungen:bachelor:aud:02-2008-7f2.png

g)

  • Nein
  • Nein
  • Ja, wenn es sich um einen Min-Heap handelt
  • Nein, man muss eines Tiefensuche vewenden

Aufgabe 8 - Sortieren

a)

[35] 70 42 11 99 1 20
[35] 70 42 11 99 1 20
[35] 20 42 11 99 1 70
[35] 20 42 11 99 1 70
[35] 20 42 11 99 1 70
[35] 20 1 11 99 42 70
[35] 20 1 11 99 42 70
[35] 20 1 11 99 42 70
[35] 20 1 11 99 42 70
11 20 1 35 99 42 70

Linkes Teil-Array:

[11] 20 1
[11] 20 1
[11] 1 20
[11] 1 20
1 11 20

Linkes Teil-Array:

[1]

Rechtes Teil-Array:

[20]

Rechtes Teil-Array:

[99] 42 70
[99] 42 70
[99] 42 70
70 42 99
70 42 99

Linkes Teil-Array:

[70] 42
[70] 42
42 70

Linkes Teil-Array:

[42]

Sortierte Folge:

1 11 20 35 42 70 99

b)

MyArray sort(MyArray a) {
	int len = a.getLength();
	int halfLen = len / 2;
 
	if(len <= 1)
		return a;
 
	MyArray left = sort(getLeftSideSplit(halfLen));
	MyArray right = sort(getRightSideSplit(halfLen));
 
	return merge(left, right);
}

c)

/ mittlere Laufzeit schlechteste Laufzeit beste Laufzeit
QuickSort O(n log n) O(n²) O(n log n)
MergeSort O(n log n) O(n log n) O(n log n)
BubbleSort O(n²) O(n²) O(n)

Aufgabe 9 - Aufwände, O-Kalkül

a)

  • O(log n)
  • O(n), da k * n/2
  • O(n²)
  • O(n)
  • O(n³)

b)

  • Ja, Logarithmen zu verschiedenen Basen unterscheiden sich nur durch konstanten Faktor
  • Ja, gültige Regel
  • Nein, für Subtraktion und Division gibt es keine Sonderregeln
  • Nein, O(n log n) steigt stärker

Aufgabe 10 - WP-Kalkül

a)

wp("b = 5*a - 3; c = 2*a; b = b + 3 * c;", b = 8) =  
wp("b = 5*a - 3; c = 2*a;", b + 3*c = 8) = 
wp("b = 5*a - 3;", b + 3*(2*a) = 8) = 
((5*a - 3) + 3*(2*a) = 8) = 
(5*a - 3 + 6*a = 8) = 
(11*a = 11) = 
(a = 1)

b)

wp("b = 2*a + 1; c = a*a; a = c + b*b;", a >= 0) = 
wp("b = 2*a + 1; c = a*a;", c + b*b >= 0) = 
wp("b = 2*a + 1;", a*a + b*b >= 0) = 
(a*a + (2*a + 1)*(2*a + 1) >= 0) = 
(a² + 4*a² + 4*a + 1 >= 0) = 
(5* a² + 4*a + 1 >= 0) = 
(true)

c)

wp("if (a == b) then a = 2*a; b = 2*b; else a = a + 1; b = b + 1; endif;", a = b) =
[(a == b) ∧ wp("a = 2*a; b = 2*b;", a = b)] ∨ [(a != b) ∧ wp("a = a + 1; b = b + 1;", a = b)] =
[(a == b) ∧ wp("a = 2*a;", a = 2*b)] ∨ [(a != b) ∧ wp("a = a + 1; b = b + 1;", a = b)] = 
[(a == b) ∧ (2*a = 2*b)] ∨ [(a != b) ∧ wp("a = a + 1; b = b + 1;", a = b)] = 
[(a == b) ∧ (2*a = 2*b)] ∨ [(a != b) ∧ wp("a = a + 1;", a = b + 1)] = 
[(a == b) ∧ (2*a = 2*b)] ∨ [(a != b) ∧ (a + 1 = b + 1)] = 
[(a == b) ∧ (a = b)] ∨ [(a != b) ∧ (a + 1 = b + 1)] = 
(true) ∨ [(a != b) ∧ (a + 1 = b + 1)] = 
(true) ∨ (false) = 
(true)

d)

  • Nein, gilt nur vor der Schleife, nicht im Schleifenrumpf
  • Ja, gilt vor der Schleife nicht, jedoch: {I ∧ b} ⇒ wp(A, I)
  • Nein, gilt nur vor der Schleife, nicht im Schleifenrumpf
  • Ja, true ist immer Schleifeninvariante

e)

Invariante
(y - y0) / (x - x0) = m
Es gilt:
x = x0; y = y0;
x = x + 1; y = y + m;
m unverändert
((y - y0) / (x - x0) = m) = 
((y + m - y0) / (x + 1 - x0) = m) = 
((y0 + m - y0) / (x0 + 1 - x0) = m) = 
(m / 1 = m) = 
(m = m) = 
(true)