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) Richtig
b) [nicht mehr Stoff aktueller Semester]
c)
- O(n³)
- O(√n)
- O(√n*log2n)
d) 3. Antwort ist richtig
e) Falsch
f) Falsch
g) Bucketsort, Mergesort
h) Richtig, weil:
Zusammenhänge für die Höhe h eines AVL-Baums mit n Knoten:
log2(n + 1) ≤ h < 1,441 * log2(n + 2)
⇔ O(log2(n + 1)) ≤ h < O(1,441 * log2(n + 2))
⇔ O(log2(n)) ≤ h < O(log2(n + 2))
⇔ O(log2(n)) ≤ h < O(log2(n))
⇒ h ∈ O(log2(n))
i) Falsch; nur bei gerader Anzahl an Elementen. Naja es hängt in v.a. auch von der Wahl des Pivot-Elementes ab.
j) O(1)
k) O(n)
Aufgabe 2 - Streutabellen
a)
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
3 | 6 | 1 | 12 | 2 | 5 | ||
9 | 4 |
b)
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
17 | 30 | 60 | 90 | 40 | 123 | 20 | 50 |
c)
Die Anzahl der Buckets und die Schrittweite sollten teilerfremd sein, da sonst nicht alle Buckets abgedeckt werden können.
Ein Schlüssel kann so unter Umständen nicht der Hashtabelle hinzugefügt werden, obwohl noch Buckets frei wären.
Aufgabe 3 -Rekursion
a) kaskadenartige Rekursion
b) Die Implementierung ist ineffizient, weil viele Werte mehrfach berechnet werden.
c)
private static long[][] b = new long[MAX][MAX]; // Vorinitialisierung des Felds b[][] mit -1 //Klausurfragestellung nicht ganz eindeutig, gefragt ist hier richtigerweise dynamische Programmierung mittels Memoization private static long binom(int n, int k) { if(k > n) return 0; if(k == 0 || k == n) return 1; if(b[n][k] == -1) b[n][k] = binom(n - 1, k - 1) + binom(n - 1, k); return b[n][k]; }
Aufgabe 4 - Suchbäume
a)
Ein binärer Suchbaum ist ein total geordneter Baum, bei dem für jeden Knoten gilt:
Jeder Knoten des linken Teilbaums ist echt kleiner, jeder des rechten Teilbaums echt größer als der aktuelle Knoten.
b)
- Minimale Höhe ist O(log n)
- Maximale Höhe ist O(n)
c)
Gesucht ist vom aktuellen Knoten ausgehend das linkeste Kind des rechten Teilbaums Nicht der rechte Knoten von der Wurzel, sondern das linkeste Kind vom rechten Kind der Wurzel !
static int getNext(BinTree r) { // Annahme der Aufgabenstellung, dass es einen nächsten Wert gibt r = r.right; while(r.left != null) { r = r.left; } return r.value; }
d)
static boolean insert(BinTree b, int value) { BinTree prev = null; // Schleppzeiger (kann nie null bleiben, solange der Baum nicht leer ist) while(b != null) { if(b.value == value) return false; if(b.value < value) { prev = b; b = b.right; } else { prev = b; b = b.left; } } if(prev.value < value) { prev.right = new BinTree(value); } else { prev.left = new BinTree(value); } return true; }
oder rekursive Version:
static boolean insertRec(BinTree b, int value) { if (value > b.value) { if (b.right == null) { b.right = new BinTree(value); return true; } return insertRec(b.right, value); } else if (value < b.value) { if (b.left == null) { b.left = new BinTree(value); return true; } return insertRec(b.left, value); } return false; }
Aufgabe 5 - Halde
a)
public static void haldenEigenschaftHerstellen(int[] feld) { for(int i = feld.length/2 - 1; i>= 0; i--) { versickern(feld, i, feld.length-1); } }
b)
- O(n log n)
Sollte es nicht O(n) sein? In den VL-Folien steht, dass das Aufbauen einer Halde aus einem Array der Länge n nur O(n) ist. (Beweis wurde ausgelassen, aber intuitiv deswegen, weil die obere Hälfte des Arrays keine Kinder in der Halde hat ⇒ ein großer Teil fällt schon mal weg!)
Ja O(n), in der Klausur wurde nach der effizientesten Möglichkeit gesucht. Diese baut den Heap in O(n) auf, wie hier unter 4.2.4 beschrieben: http://linux-related.de/index.html?/coding/sort/sort_heap.htm
c)
public static void haldenSortierung(int[] feld) { haldenEigenschaftHerstellen(feld); for(int i = 0; i < feld.length; i++) { tausche(feld, 0, feld.length - 1 - i); // Annahme, dass versickern nur mit validen "von" und "bis" Werte aufgerufen werden darf if(i < feld.length - 1) versickern(feld, 0, feld.length - 2 - i); } }
Das ginge meines Erachtens (bei anderer Angabe noch leichter), oder??:
public static void haldenSortierung(int[] feld){ haldenEigenschaftHerstellen(feld); for(int i = feld.length - 1; i > 0; i--){ tausche(feld, 0, i); versickern(feld, 0, i - 1); } }
Programm zum selbst Testen:
:pruefungen:bachelor:aud:heapsort.java.txt
d)
- versickern: O(log n)
- haldenSortierung: O(n log n)
Aufgabe 6 - UML
Aufgabe 7 - Graphen
a) Adjazenzmatrix
A | B | C | D | |
---|---|---|---|---|
A | - | 4 | 2 | - |
B | 4 | - | 1 | - |
C | 2 | 1 | - | 5 |
D | - | - | 5 | - |
b) Dijkstra
A | B | C | D | E | F | G | H |
---|---|---|---|---|---|---|---|
[0] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
4A | [2A] | ∞ | ∞ | ∞ | ∞ | ∞ | |
[3C] | 7C | ∞ | ∞ | ∞ | ∞ | ||
7C | ∞ | [4B] | ∞ | ∞ | |||
7C | [5F] | ∞ | 8F | ||||
[7C] | 10E | 8F | |||||
10E | [8F] | ||||||
[9H] |
[9H] → [8F] → [4B] → [3C] → [2A] → [0]
⇒ A → C → B → F → H → G
c) Euler
Eine von mehreren Möglichkeiten:
d)
- Welche Kanten werden vom Algorithmus als nächstes in Betracht gezogen?
EG, HF, BA, CA, DC
- Welche dieser Kanten fugt der Algorithmus im nächsten Schritt der Lösungsmenge hinzu? \\CA
Die Kante DC wird nicht genommen, da nur Kanten hinzugefügt werden, die zu einem noch nicht besuchten Knoten führen.
Aufgabe 8 – Abstrakte Datentypen
a)
contains(x, create) = false contains(x, put(x, M)) = true contains(x, put(y, M)) = contains(x, M);
oder
axs contains(s, create()) = FALSE contains(s, put(a, m)) = { TRUE falls s = a { contains(s, m) sonst
b)
count: String x MultiSet -> Integer count(x, create) = 0 count(x, put(x, M)) = 1 + count(x, M) count(x, put(y, M)) = count(x, M)
oder
ops count: String x MultiSet -> Integer axs count(s, create()) = 0 count(s, put(a, m)) = { 1 + count(s, m) falls s = a { count(s, m) sonst
c)
purge: String x MultiSet -> MultiSet purge(x, create) = create purge(x, put(x, M)) = purge(x, M) purge(x, put(y, M)) = put(y, purge(x, M))
oder
ops purge: String x MultiSet -> MultiSet axs purge(s, create()) = create() purge(s, put(a, m)) = { purge(s, m) falls s = a { put(a, purge(s, m)) sonst
d)
Primärkonstruktoren:
create, put
Aufgabe 9 - wp-Kalkül
a)
wp("a = a*3 - 1; b = 80 - a; b--;", b > 47) = wp("a = a*3 - 1; b = 80 - a; b = b - 1;", b > 47) = wp("a = a*3 - 1; b = 80 - a;", b - 1 > 47) = wp("a = a*3 - 1;", 80 - a - 1 > 47) = (80 - (a*3 - 1) - 1 > 47) = (80 - a*3 + 1 - 1 > 47) = (33 > a*3) = (11 > a)
wp("if (x < 0 || x > 7) {x = 7 - x;} else {x = 8 + x;}", x != 7) = [(x < 0 ∨ x > 7) ∧ wp("x = 7 - x;", x != 7)] ∨ [¬(x < 0 ∨ x > 7) ∧ wp("x = 8 + x;", x != 7)] = [(x < 0 ∨ x > 7) ∧ (7 - x != 7)] ∨ [(x ≥ 0) ∧ (x ≤ 7) ∧ (8 + x != 7)] = [(x < 0 ∨ x > 7) ∧ (x != 0)] ∨ [(x ≥ 0) ∧ (x ≤ 7) ∧ (x != -1)] = (x != 0) ist durch (x < 0 ∨ x > 7) schon abgedeckt (x != -1) ist durch (x ≥ 0) ∧ (x ≤ 7) schon abgedeckt (x < 0) ∨ (x > 7) ∨ ((x ≥ 0) ∧ (x ≤ 7)) = (x < 0) ∨ (x > 7) ∨ (0 ≤ x ≤ 7) = (true)
b)
i)
LO: falsch a = 1, i = n mf(n, i) = mf(n, n) = 0 RO: falsch a = 1, i = n mf(n, k) - mf(i, k) = mf(n, k) - mf(n, k) = 0 LU: korrekt a = 1, i = n (mf(n, k) / (mf(i, k) = (mf(n, k) / (mf(n, k) = 1 RU: falsch a = 1, i = n mf(n, i) - mf(k, i) = mf(n, n) - mf(k, n) = 0 - mf(k, n) = -mf(k, n) < 0
ii)
Zu zeigen: {I ∧ b} = wp(A, I) wp(A, I) = wp("a = a*i; i = i - k;", a = (mf(n, k)) / (mf(i, k)) ) = wp("a = a*i;", a = (mf(n, k)) / (mf(i - k, k)) ) = (a*i = (mf(n, k)) / (mf(i - k, k)) ) = (a = (mf(n, k)) / (mf(i - k, k) * i) ) = = (*) = (a = (mf(n, k)) / (mf(i, k)) ) (*) Nebenrechnung: mf(i - k, k) = (i - k) * (i - 2k) * (i - 3k) * ... * 1 mf(i - k, k) * i = (i - k) * (i - 2k) * (i - 3k) * ... * 1 * i und das entspricht mf(i, k) * i = i* (i - k) * (i - 2k) * (i - 3k) * ... * 1 {I ∧ b} => wp(A, I) {a = (mf(n, k)) / (mf(i, k)) ∧ i > 0)} => (a = (mf(n, k)) / (mf(i, k)) ) trivial, da die schwächste Vorbedingung nur restriktiver gemacht wurde
iii)
V = i i = n, n > 0 -> V > 0 zu Beginn i = i - k, k > 0 -> i ist monoton fallend