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)
AB, BD, BC, DG, GE, GI, IF, FH
f)
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 5 - ADT
a)
- number
- binop
- left
- right
- commutate
Hinweis: Konstruktoren sind 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) 1,4,7 In Tabelle von a) mittels [] eingekreist.
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 haben als der aktuelle Knoten.
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:
Max-Heap:
g)
* Nein
* Nein
* Ja, wenn es sich um einen Min-Heap handelt
* Nein, man muss eines Tiefensuche vewenden
=== Aufgabe 8 - Binäre Bäume ===
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) |