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
a) falsch
b) 3 - eine Schleife korrekt ist
c) richtig
d) richtig
e) Bucketsort, Mergesort
f) 1 - exakt n-1 Kanten
g) 4 - O(n² * log n)
h) O(n*(log n)²)
i) 1 - kontextsensitiven Grammatiken
Aufgabe 2 - Graphen
a)
A | B | C | D | E | F | Prioritäts-Warteschlange |
---|---|---|---|---|---|---|
[0] | ∞ | ∞ | ∞ | ∞ | ∞ | A |
0 | [4] | 5 | ∞ | ∞ | ∞ | B,C |
0 | 4 | [5] | ∞ | 5 | ∞ | C,E |
0 | 4 | 5 | 7 | [5] | ∞ | E,D |
0 | 4 | 5 | [6] | 5 | 10 | D,F |
0 | 4 | 5 | 6 | 5 | [10] | F |
0 | 4 | 5 | 6 | 5 | 10 |
b)
- nach B: 4
- nach C: 5
- nach D: 6
- nach E: 5
- nach F: 10
Aufgabe 3 - Java
a) Java Datei zum selber testen: :pruefungen:bachelor:aud:test.java.txt
Zeile | Bildschirmausgabe bzw. keine Ausgabe |
---|---|
23 | BA |
24 | AB |
27 | keine Ausgabe |
31 | BB |
38 | CC |
39 | AA |
b)
Zeile | Begrundung |
---|---|
7 | Compiler: f implementiert nicht die Methode f des Interfaces |
19 | Compiler: keine cast von double auf int im return Statement |
34 | Compiler: Instanzvariablen können nicht über den statischen Typ angesprochen werden (nicht A sondern a) |
40 | Compiler: Man kann nicht von der Ober- auf die Unterklasse konvertieren, nur andersherum |
44 | Compiler: g ist eine private-Methode. Darauf kann man nicht von i aus zugreifen |
Aufgabe 4 - ADT
a) A4: contains(x, create) = false
A5: contains(x, append(y,l))= 1+contains(x,l) //falls x=y contains(x,l) //falls x!=y
b) A → D → create
c) VORSICHT! nicht wirklich sicher!
A1: append(head(append(D, create), append(A, create))
A1: append(head(prepend(D, create), prepend(A, create))
A3: append(D, prepend(A, create)
A2: prepend(A, append(D, create)
A1: prepend(A, prepend(D, create)
Aufgabe 5 - Pseudo-Zufallszahlen
a)
public static int f(int n) { if (n < 3) return n + 1; else return 1 + (((f(n - 1) - f(n - 2)) * f(n - 3)) % 100); }
b)
Vorüberlegungen:
f(n - 1) ^= c, da f(2) = 2 + 1 = 3 ist; analog:
f(n - 2) ^= b
f(n - 3) ^= a
lin (a, b, c) ^= lin (f(n - 3), f(n - 2), f(n - 1), steps)
Wir starten also am Basisfall n < 3 ( ⇒ Bottom-Up ), weshalb nur noch der „sonst“-Teil beachtet werden muss.
Nächster „step“: n + 1
lin (f(n - 2), f(n - 1), f(n), steps - 1) (*)
f(n - 2) und f(n - 1) sind bereits berechnet und müssen nur nach links geschoben werden. f(n) berechnet sich wie in Aufgabe a) und sieht mit a, b, c dann so aus:
f(n) = 1 + (((c - b) * a) % 100)
Das in (*) eingesetzt ergibt dann
lin(b, c, 1 + (((c - b) * a) % 100), steps - 1)
public static int f(int n) { return lin(1, 2, 3, n); } private static int lin(int a, int b, int c, int steps) { if (steps == 0) { return a; } else { lin(b, c, 1 + (((c - b) * a) % 100), steps - 1); } }
Warum steht das Ergebnis gerade in a?
Wo das Ergebnis stehen muss, zeigt die Anwedung der Rekursionsvorschrift: f(0) = lin(1, 2, 3, 0). Da n = 0 < 3, greift der sonst-Fall und das Ergebnis muss n + 1 = 0 + 1 = 1 sein. Und die 1 steht in a.
c)
public static int f(int n) { int a = 1, b = 2, c = 3; while (n > 0) { int tmp = a; a = b; b = c; c = 1 + (((b-a)*tmp)%100); n--; } return a; }
Aufgabe 6 - Suchbäume
a)
27 / \ 23 42 / / \ 7 32 64 \ 81
b) Schlusselfolge für maximale Höhe: 7, 23, 27, 32, 42, 64, 81 Kosten: O (n²)
Schlusselfolge für minimale Höhe: 32, 64, 42, 81, 23, 7, 27 Kosten: O (n * log n)
c)
d)
Rotation an: 64
Einfachrotation, da 81 und 64 links gedreht werden.
Aufgabe 7 - Heap
a) Für jeden Knoten außer der Wurzel gilt A[Vater[i]] >= A[i]
b)
13 6 9 2 5 8
c)
public int leftChildIndex (int parentIndex) { return parentIndex*2+1; }
d)
public int parentIndex (int childIndex) { return (childIndex-1)/2; }
e)
//keine garantie! public void add (int priority) { array[n] = priority; while( j !=0) { int i = n; int j = parentIndex(n); if( priority > array[j] ) { array[i] = array[j]; array[j] = priority; } else { break; } } n++; }
f) O(log n)
Aufgabe 8 (wp)
a) a > b-5 && true ⇒ a > b-5