Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:bachelor:aud:loesungws09 [16.02.2013 14:13] – Dawodo | pruefungen:bachelor:aud:loesungws09 [20.06.2020 14:09] (aktuell) – BierBaron69 | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ==forum== | + | ===== Forendiskussionen ===== |
* [[https:// | * [[https:// | ||
* [[https:// | * [[https:// | ||
Zeile 10: | Zeile 10: | ||
* [[https:// | * [[https:// | ||
* [[https:// | * [[https:// | ||
+ | * [[https:// | ||
- | ==== Lösungsversuch ==== | + | ===== Lösungsversuch |
+ | ==== Aufgabe 1 - Wissensfragen ==== | ||
- | === Aufgabe 1 - Wissensfragen (14P) === | ||
**a)** Richtig | **a)** Richtig | ||
Zeile 32: | Zeile 33: | ||
**g)** Bucketsort, Mergesort | **g)** Bucketsort, Mergesort | ||
- | **h)** Richtig | + | **h)** Richtig, weil: \\ |
+ | \\ | ||
+ | Zusammenhänge für die Höhe h eines AVL-Baums mit n Knoten: \\ | ||
+ | log< | ||
+ | \\ | ||
+ | <=> O(log< | ||
+ | <=> O(log< | ||
+ | <=> O(log< | ||
+ | \\ | ||
+ | => h ∈ O(log< | ||
- | **i)** Falsch | + | |
+ | **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) | **j)** O(1) | ||
Zeile 40: | Zeile 51: | ||
**k)** O(n) | **k)** O(n) | ||
- | ----- | ||
- | === Aufgabe 2 - Streutabellen | + | ==== Aufgabe 2 - Streutabellen |
**a)** | **a)** | ||
^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ | ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ | ||
Zeile 50: | Zeile 60: | ||
**b)** | **b)** | ||
^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ | ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ | ||
- | | 1 | 3 | 6 | 9 | 4 | 12 | 2 | 5 | | + | | 1< |
**c)** | **c)** | ||
Zeile 57: | Zeile 67: | ||
Ein Schlüssel kann so unter Umständen nicht der Hashtabelle hinzugefügt werden, obwohl noch Buckets frei wären. | Ein Schlüssel kann so unter Umständen nicht der Hashtabelle hinzugefügt werden, obwohl noch Buckets frei wären. | ||
- | ----- | ||
- | == Aufgabe 3 == | + | ==== Aufgabe 3 -Rekursion ==== |
**a)** | **a)** | ||
Zeile 71: | Zeile 80: | ||
private static long[][] b = new long[MAX][MAX]; | private static long[][] b = new long[MAX][MAX]; | ||
// Vorinitialisierung des Felds b[][] mit -1 | // Vorinitialisierung des Felds b[][] mit -1 | ||
+ | // | ||
- | private static long binomFast(int n, int k) { | + | private static long binom(int n, int k) { |
if(k > n) | if(k > n) | ||
return 0; | return 0; | ||
Zeile 86: | Zeile 96: | ||
</ | </ | ||
- | ----- | ||
- | == Aufgabe 4 == | + | ==== Aufgabe 4 - Suchbäume ==== |
**a)** | **a)** | ||
Zeile 144: | Zeile 153: | ||
</ | </ | ||
- | ----- | + | oder rekursive Version: |
- | == Aufgabe 5 == | + | <code java> |
+ | 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, | ||
+ | } else if (value < b.value) { | ||
+ | if (b.left == null) { | ||
+ | b.left = new BinTree(value); | ||
+ | return true; | ||
+ | } | ||
+ | return insertRec(b.left, | ||
+ | } | ||
+ | return false; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | |||
+ | ==== Aufgabe 5 - Halde ==== | ||
**a)** | **a)** | ||
Zeile 159: | Zeile 188: | ||
**b)** | **b)** | ||
* **O(n log n)** | * **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, | ||
+ | |||
+ | 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: | ||
**c)** | **c)** | ||
Zeile 173: | Zeile 205: | ||
} | } | ||
} | } | ||
+ | </ | ||
+ | |||
+ | Das ginge meines Erachtens (bei anderer Angabe noch leichter), oder??: | ||
+ | |||
+ | <code java> | ||
+ | |||
+ | public static void haldenSortierung(int[] feld){ | ||
+ | haldenEigenschaftHerstellen(feld); | ||
+ | | ||
+ | for(int i = feld.length - 1; i > 0; i--){ | ||
+ | tausche(feld, | ||
+ | versickern(feld, | ||
+ | } | ||
+ | } | ||
</ | </ | ||
Zeile 183: | Zeile 229: | ||
* haldenSortierung: | * haldenSortierung: | ||
- | ----- | + | ==== Aufgabe 6 - UML ==== |
- | + | ||
- | == Aufgabe 6 UML == | + | |
{{: | {{: | ||
- | ----- | + | ==== Aufgabe 7 - Graphen ==== |
- | == Aufgabe 7 - Graphen (15P)== | ||
**a) Adjazenzmatrix** | **a) Adjazenzmatrix** | ||
^ ^ A ^ B ^ C ^ D ^ | ^ ^ A ^ B ^ C ^ D ^ | ||
Zeile 202: | Zeile 245: | ||
^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ | ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ | ||
| [0] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | | | [0] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | | ||
- | | 0 | 4 | [2] | ∞ | ∞ | ∞ | ∞ | ∞ | | + | | | 4< |
- | | 0 | [3] | 2 | 7 | ∞ | ∞ | ∞ | ∞ | | + | | | [3< |
- | | 0 | 3 | 2 | 7 | ∞ | [4] | ∞ | ∞ | | + | | | | | 7< |
- | | 0 | 3 | 2 | 7 | [5] | 4 | ∞ | 8 | | + | | | | | 7< |
- | | 0 | 3 | 2 | [7] | 5 | 4 | 10 | 8 | | + | | | | | [7< |
- | | 0 | 3 | 2 | 7 | 5 | 4 | 10 | [8] | | + | | | | | | | | 10< |
- | | 0 | 3 | 2 | 7 | 5 | 4 | [9] | 8 | | + | | | | | | | | [9< |
- | | 0 | 3 | 2 | 7 | 5 | 4 | 9 | 8 | | + | |
+ | [9< | ||
+ | |||
+ | => A -> C -> B -> F -> H -> G | ||
**c) Euler** | **c) Euler** | ||
Zeile 225: | Zeile 271: | ||
Die Kante DC wird nicht genommen, da nur Kanten hinzugefügt werden, die zu einem noch nicht besuchten Knoten führen. | 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 | + | ==== Aufgabe 8 – Abstrakte Datentypen |
**a)** | **a)** | ||
< | < | ||
Zeile 234: | Zeile 279: | ||
contains(x, put(y, M)) = contains(x, M); | 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) | ||
+ | </ | ||
**b)** | **b)** | ||
< | < | ||
Zeile 242: | Zeile 294: | ||
count(x, put(x, M)) = 1 + count(x, M) | count(x, put(x, M)) = 1 + count(x, M) | ||
count(x, put(y, M)) = count(x, M) | count(x, put(y, M)) = count(x, M) | ||
+ | </ | ||
+ | oder | ||
+ | \\ | ||
+ | < | ||
+ | ops | ||
+ | count: | ||
+ | |||
+ | axs | ||
+ | count(s, create()) = 0 | ||
+ | count(s, put(a, m)) = { 1 + count(s, m) falls s = a | ||
+ | { count(s, m) sonst | ||
</ | </ | ||
Zeile 251: | Zeile 314: | ||
purge(x, put(x, M)) = purge(x, M) | purge(x, put(x, M)) = purge(x, M) | ||
purge(x, put(y, M)) = put(y, purge(x, M)) | purge(x, put(y, M)) = put(y, purge(x, M)) | ||
+ | </ | ||
+ | oder | ||
+ | \\ | ||
+ | < | ||
+ | ops | ||
+ | purge: | ||
+ | |||
+ | axs | ||
+ | purge(s, create()) = create() | ||
+ | purge(s, put(a, m)) = { purge(s, m) falls s = a | ||
+ | { put(a, purge(s, m)) sonst | ||
</ | </ | ||
Zeile 258: | Zeile 332: | ||
create, put | create, put | ||
- | ----- | + | ==== Aufgabe 9 - wp-Kalkül ==== |
- | + | ||
- | == Aufgabe 9 == | + | |
**a)** | **a)** | ||
< | < | ||
wp("a = a*3 - 1; b = 80 - a; b--;", b > 47) = | 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; b = 80 - a;", b - 1 > 47) = | ||
wp("a = a*3 - 1;", 80 - a - 1 > 47) = | wp("a = a*3 - 1;", 80 - a - 1 > 47) = | ||
Zeile 274: | Zeile 347: | ||
< | < | ||
wp("if (x < 0 || x > 7) {x = 7 - x;} else {x = 8 + x;}", x != 7) = | 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) ∧ 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) ∧ (7 - x != 7)] ∨ [(x ≥ 0) ∧ (x ≤ 7) ∧ (8 + x != 7)] = | ||
[(x < 0 ∨ x > 7) ∧ (x != 0)] ∨ [(x ≥ 0) ∧ (x ≤ 7) ∧ (x != -1)] = | [(x < 0 ∨ x > 7) ∧ (x != 0)] ∨ [(x ≥ 0) ∧ (x ≤ 7) ∧ (x != -1)] = | ||
Zeile 331: | Zeile 404: | ||
iii) | iii) | ||
- | | + | < |
- | i = n, n > 0 -> V > 0 zu Beginn | + | V = i |
- | i = i - k, k > 0 -> i ist monoton fallend | + | i = n, n > 0 -> V > 0 zu Beginn |
+ | i = i - k, k > 0 -> i ist monoton fallend | ||
+ | </ |