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 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:
: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 - 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 ^ ^ O(n log n) | O(n²) | O(n log n) | ^ O(n log n) | O(n log n) | O(n log n) | ^ O(n²) | O(n²) | O(n) |