Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen
Inhaltsverzeichnis
Forendiskussionen
Lösungsversuch
Aufgabe 1 - Wissensfragen
a) Falsch, es muss sortiert sein
b) Nummer 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)) = true contains(x, append(y, L)) = contains(x, L)
b) A → D
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:
public static int f(int n) { return lin(1, 2, 3, n); } private static int lin(int a, int b, int c, int steps) { ...
Die Basisfälle der Funktion sind für n < 3 gegeben:
f(0) = 1
f(1) = 2
f(2) = 3
Aus dem gegebenen Aufruf (mit 1,2,3) und dieser Basisfälle lässt sich schließen:
a = 1 = f(0) –> entspricht f(n - 3)
b = 2 = f(1) –> entspricht f(n - 2)
c = 3 = f(2) –> entspricht f(n - 1)
Das Wichtige an dieser Aufgabe ist sich bewusst zu machen, wie die Werte im angegebenem Aufruf, mit den Basisfällen bzw. f(n-3), f(n-2), f(n-1) in der angegebenen Formel korrespondieren. Das Ziel ist ja diese Werte der Formel in Java-Code auszudrücken.
Somit wissen wir:
lin(a, b, c, steps) → 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), dieses mal jedoch mit den durchgereichten Zwischenergebnissen a, b, c:
f(n) = 1 + (((c - b) * a) % 100) (* *)
(* *) in (*) eingesetzt ergibt:
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; return 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) = 1
f(0) = lin(1, 2, 3, 0)
Das Ergebnis steht in Variable a.
c)
public static int f(int n) { int a = 1; int b = 2; int c = 3; while(n > 0) { int fn = 1 + (((c - b) * a) % 100); a = b; b = c; c = fn; 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)
Verwendete Definitionen:
- Höhe eines Blatts: 0
- Daraus folgt die Höhe des leeren Baums: -1
- Balancefaktor: (Höhe des linken Teilbaums) - (Höhe des rechten Teilbaums)
d)
- Rotation an Knoten: 64
- Einfachrotation gegen der Uhrzeigersinn, da die Vorzeichen der Balancefaktoren von 81 und 64 gleich sind
e)
Aufgabe 7 - Heap
a) Der Wert jedes Knotens muss größer (Max-Heap) oder kleiner (Min-Heap) als die Werte 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 % 2 == 1) ? (childIndex - 1) / 2 : (childIndex - 2) / 2; //Oder auch einfach nur // return childIndex/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-Kalkül
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