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

  • number
  • binop
  • left
  • right
  • commutate

Hinweis: Konstruktoren sind alle Operationen, die Datenobjekte des Typs erzeugen.

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 + 1; j++) {    // Spalten
        if((tab[i][j] == OHNE || tab[i][j] == MIT) && i < n-1) { // Wenn in einer Zeile MIT oder OHNE steht
            tab[i+1][j] = OHNE;         // so muss die Zelle daraunter den Wert OHNE haben.
            if(j + k[i+1] <= m)
                tab[i+1][j+k[i+1]] = MIT;
        }
    }
}

d) unsicher! * nein * ja * nein * ja === 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) <code java> 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); } } } } </code> c) <code java> public class BB { … public int maximum() { if(right != null) return right.maximum(); return schluessel; } } </code> d) Der Wert eines Knotes in einem Max-Heap muss größer sein als der seiner Kinder. e) <code java> public class Heap { … public int maximum() { return schluessel; } } </code> 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) <code java> 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); } </code> 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(k) * 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)