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, es muss sortiert sein
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) 2 - 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) Pfade von Knoten A nach …
… | Kosten | Pfad |
---|---|---|
B | 4 | A → B |
C | 5 | A → C |
D | 6 | A → B → E → D |
E | 5 | A → B → E |
F | 10 | A → B → E → F |
Aufgabe 3 - Java
a)
Zeile | Bildschirmausgabe bzw. keine Ausgabe |
---|---|
23 | BA |
24 | AB |
27 | keine Ausgabe |
31 | BB |
38 | CC |
39 | AA |
Java-Datei zum selbst testen:
:pruefungen:bachelor:aud:test.java.txt
b)
Zeile | Begrundung |
---|---|
7 | Compiler: A implementiert die Methode f() des Interfaces I nicht (korrekt) |
19 | Compiler: fehlender Cast von double zu int im return-Statement |
21 | Compiler: die Sichtbarkeit von A geerbte public Methode g() kann in der Unterklasse nicht eingeschränkt werden |
34 | Compiler: Statischer Zugriff auf Instanzvariablen (Beachte Unterschied: A ↔ a) |
40 | Compiler: Cast von Ober- auf Unterklasse nicht möglich (andersherum jedoch schon) |
44 | Compiler: Interface I definiert keine Methode g() |
Java-Datei zum selbst testen:
:pruefungen:bachelor:aud:test-07-08_2.java.txt
Aufgabe 4 - ADT
a)
contains(x, create) = false contains(x, append(x, L)) = 1 + contains(x, L) contains(x, append(y, L)) = contains(x, L)
b) A → D → create
c)
append(head(append(D, create), append(A, create)) = A1 = append(head(prepend(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; 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)
Für die maximale Höhe müssen die Werte in auf- oder absteigend sortiert in den Baum eingefügt werden.
Schlüsselfolge für maximale Höhe: 7, 23, 27, 32, 42, 64, 81
Kosten: O(n)
Für einen perfekt balancierten Baum fügt man immer das mittlere Element der sortierten Reihe ein, teil die Reihe in zwei Restreihen auf und fährt mit diesen genauso fort.
Schlüsselfolge für minimale Höhe: 32, 23, 7, 27, 64, 42, 81
Kosten: O(log n)
c)
d)
- Rotation an: 64
- Einfachrotation, da die Vorzeichen der Balancewerte von 81 und 64 gleich sind
e) …
Aufgabe 7 - Heap
a) Der Wert jedes Knotens muss größer, als der seiner Kinder sein.
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; int p = parentIndex(n); while(p >= 0 && array[p] < array[n]) { // swap ohne temporäre Variable, da immer nur priority nach oben geswappt wird array[n] = array[p]; array[p] = priority; n = p; p = parentIndex(n); } n++; }
f) O(log n)
Aufgabe 8 (wp)
a)
wp("if (a > b - 5) {a = b++ - 4;}", a = b - 5) = [(a > b - 5) ∧ wp("a = b++ - 4;", a = b - 5)] ∨ [(a ≤ b - 5) ∧ (a = b - 5)] = [(a > b - 5) ∧ wp("a = b - 4; b = b + 1;", a = b - 5)] ∨ [(a ≤ b - 5) ∧ (a = b - 5)] = [(a > b - 5) ∧ wp("a = b - 4; b = b + 1;", a = b - 5)] ∨ (a = b - 5) = [(a > b - 5) ∧ wp("a = b - 4;", a = b + 1 - 5)] ∨ (a = b - 5) = [(a > b - 5) ∧ (b - 4 = b + 1 - 5)] ∨ (a = b - 5) = [(a > b - 5) ∧ (b - 4 = b - 4)] ∨ (a = b - 5) = [(a > b - 5) ∧ true] ∨ (a = b - 5) = (a > b - 5) ∨ (a = b - 5) = (a ≥ b - 5)
b)
i)
Nummer 3: (x mod 2) = (i mod 2) ∧ y ≥ 0
ii)
Zu zeigen: P => wp(A,I) Nachweis: wp(A,I) = wp("x = i; y = 0; r = false;", (x mod 2) = (i mod 2) ∧ y ≥ 0) = wp("x = i; y = 0;", (x mod 2) = (i mod 2) ∧ y ≥ 0) = wp("x = i;", (x mod 2) = (i mod 2) ∧ 0 ≥ 0) = (i mod 2) = (i mod 2) ∧ 0 ≥ 0 = true ∧ true = true P => wp(A,I) = ((i ≥ 0) => true) = (¬(i ≥ 0) ∨ true) = true
iii)
Zu zeigen: {I ∧ b} => wp(A,I) Nachweis: wp(A,I) = wp("x = x - 2; y = y + 1;", (x mod 2) = (i mod 2) ∧ y ≥ 0) = wp("x = x - 2;", (x mod 2) = (i mod 2) ∧ y + 1 ≥ 0) = (x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0 {I ∧ b} => wp(A,I) = {(x mod 2) = (i mod 2) ∧ y ≥ 0 ∧ x > 1} => ((x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0) = ¬{(x mod 2) = (i mod 2) ∧ y ≥ 0 ∧ x > 1} ∨ ((x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0) = (x mod 2) != (i mod 2) ∨ (y < 0) ∨ (x ≤ 1) ∨ ((x - 2 mod 2) = (i mod 2) ∧ y + 1 ≥ 0) = (y + 1 ≥ 0) gilt immer, da y vor der Schleife immer 0 ist, und in der Schleife immer wieder inkrementiert wird. (y < 0) ist aus selbigem Grund immer falsch. (x mod 2) != (i mod 2) ∨ (x ≤ 1) ∨ (x - 2 mod 2) = (i mod 2) Da das Axiom "a mod 2 = (a - 2) mod 2" für a ≥ 2 gilt: aus ¬(x ≤ 1) folgt (x > 1) und daraus über das Axiom, dass (x - 2 mod 2) = (i mod 2) = true Das heißt: (x mod 2) != (i mod 2) ∨ (x ≤ 1) ∨ (x - 2 mod 2) = (i mod 2) = true