Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen (Übersicht)
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:bachelor:aud:loesungws09 [19.03.2018 20:00] – Evren | pruefungen:bachelor:aud:loesungws09 [20.06.2020 14:09] (aktuell) – BierBaron69 | ||
---|---|---|---|
Zeile 10: | Zeile 10: | ||
* [[https:// | * [[https:// | ||
* [[https:// | * [[https:// | ||
+ | * [[https:// | ||
===== Lösungsversuch ===== | ===== Lösungsversuch ===== | ||
Zeile 44: | Zeile 45: | ||
- | **i)** Falsch; nur bei gerader Anzahl an Elementen. | + | **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 79: | 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 187: | Zeile 189: | ||
* **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, | 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 201: | 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 261: | 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 269: | 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 278: | 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 289: | Zeile 336: | ||
< | < | ||
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) = |