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 (13P)
a) [noch nicht in Vorlesung durchgenommen]
b) O (log2n) O (n²)
O(2 hoch n)
c) falsch
d) falsch (geht nur andersherum)
e) richtig
f) richtig
g) falsch
h) O(n²)
i) [nicht in Vorlesung durchgenommen]
Aufgabe 2
a)
abstract class EierLegend implements Haustier{ protected int eierSammeln(); } class Schaf extends WolleGebend implements Schlachtvieh, MilchErzeugend{ public static final int SCHWARZ =1; private static int anzahl=0; public float melken(); public final void schlachten(); protected static int zaehlen(); }
b) java lässt keine mehrfachvererbung zu ( extends MilchErzeugend,Eierlegend,… n.a.)
c) ???
d) ??
Aufgabe 3
a) Verschränkte Rekursion
b)
public static int foo(int n) { int ret; if (n == 0) { ret = 3; } else if (n == 1) { ret = 1; } else { ret = foo(n - 1) + bar (n - 2); } return ret; }
c)
d) Es werden immer wieder die selben Wert neu berechnet z. b. foo(2). Optimierung durch dynamische Programmierung
e)
public static int foo(int n) { int ret; if (fooTable[n] != UNKNOWN) { return fooTable[n]; } //... //... fooTable[n] = ret; return ret; }
e) LZ: O(n²) S-Pl: O(n)
Aufgabe 4
a) Von hinten nach vorne, also erst die letze stelle, dann die vorletzte usw.
b)
| Stelle | Reihung | |||||
|---|---|---|---|---|---|---|
| 420 | 234 | 142 | 123 | 432 | 230 | |
| 3 | 420 | 230 | 142 | 432 | 123 | 234 |
| 2 | 420 | 123 | 230 | 432 | 234 | 142 |
| 1 | 123 | 142 | 230 | 234 | 420 | 432 |
c)
Aufgabe 5 (Graphen)
a)
| A | E | H4 | H7 | M | W | Warteschlange |
|---|---|---|---|---|---|---|
| ∞ | ∞ | ∞ | ∞ | ∞ | [0] | W |
| 15 | ∞ | ∞ | ∞ | [2] | 0 | M, A |
| 15 | ∞ | 6 | [3] | 2 | 0 | H7, H4, A |
| 15 | 21 | [6] | 3 | 2 | 0 | H4, A |
| [14] | 20 | 6 | 3 | 2 | 0 | A, E |
| 14 | [18] | 6 | 3 | 2 | 0 | E |
| 14 | 18 | 6 | 3 | 2 | 0 |
b)
c) Eulerpfad: Nein, da man mindestens eine Kante mehrmals benutzen müsste. Es weisen mehr als 2 Knoten einen ungeraden Grad auf.
Eulerzyklus: Nein, es haben nicht alle Knoten einen geraden Grad.
d)
Dijkstra: O((|V| + |E|)* log|V|)
Gesamtaufwand mit Fibonacci Halde: O(|V| * log|V| + |E|)
Kruskal: O(|E| · log |V |)
Aufgabe 6 (Streutabellen)
a)
| Bucket | keys (linkedList) |
|---|---|
| 0 | |
| 1 | 27 → 75 |
| 2 | |
| 3 | 44 → 4 → 0 |
| 4 | |
| 5 | 13 → 65 → 33 |
| 6 | |
| 7 | 46 → 26 |
b) viele Kolissionen, schlechte Verteilung, ???
c)
| Bucket | key | P, S oder D |
|---|---|---|
| 0 | 12 | S |
| 1 | 33 | D |
| 2 | 66 | S |
| 3 | 28 | S |
| 4 | 14 | D |
| 5 | 6 | S |
| 6 | 18 | D |
| 7 | 5 | D |
| 8 | 15 | P |
| 9 | 9 | D |
Aufgabe 7
a)
wp('a+= ++b -2; ' , a+b>0)
wp('b=b+1;a=a+(b-2);',a+b > 0)
wp('b=b+1;',a+b-2+b > 0)
wp(",a+(b+1) - 2+(b+1) >0)
=a+b+b+1+1-2 = a+2b >0
b)
[(b & wp(A,Q)] | [ ab & wp (A,Q)]
[(a > -2b & b>0) & wp("a+=++b-2", a+b>0)] | [( ! (a>-2b & b>0) & wp( " b-= --a", a+b > 0)] // wp("a+=++b-2", a+b>0) wurde bei a) schon berechnet
=> [(a > -2b & b>0) & a+2b>0)] | [( ! (a>-2b & b>0) & a+b > 0)]
=> [a+2b > 0 & b>0)] | [ a<= -2b & b>0]
=> b>0 & (a+2b > = | a <=-2b)
=> b>0 & (a+2b > 0 | a+2b<=0)
=> b>0
c) i) Invariante I = e= (a!)/(a-e-1)! & d= (e-1)
c) ii) Invariante nachweisen:
Formel : I & b => wp (A,I)
wp('c=c*(a-e+1),d=de,e=e+1',I)
wp('c=c*(a-e+1),d = de', c =(a!) /(a-(e+1)+1)! & d= ((e+1)-1)!
wp('c=c*(a-e+1)',c= (a!) / (a-e)! & de= e!
wp (", c(a-e+1)= (a!)/ (a-e)! & de-e! // de = e! ==> d= (e-1)!
c= (a!) / (a-e+1) & d = (e-1)!
I & b => I = immer wahr !