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 ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungss11 [20.02.2013 12:17] – Dawodo | pruefungen:bachelor:aud:loesungss11 [21.03.2018 12:00] – Evren | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
===== Forendiskussionen ===== | ===== Forendiskussionen ===== | ||
+ | * [[https:// | ||
+ | * [[https:// | ||
+ | * [[https:// | ||
+ | * [[https:// | ||
* [[https:// | * [[https:// | ||
* [[https:// | * [[https:// | ||
- | * [[https:// | ||
- | * [[https:// | ||
- | * [[https:// | ||
===== Lösungsversuch ===== | ===== Lösungsversuch ===== | ||
Zeile 13: | Zeile 14: | ||
**a)** E + Unterklassen von E | **a)** E + Unterklassen von E | ||
- | **b)** O(|n|) | + | **b)** O(|n|) |
+ | Begründung: | ||
+ | Nach einmaliger Abarbeitung der inneren Schleife gilt "n == 0". Dadurch ergibt die Auswertung des Schleifenkopfs der äußeren Schleife " | ||
**c)** O(n) | **c)** O(n) | ||
+ | Begründung: | ||
+ | Im ersten Durchgang der Schleife werden alle drei Unterfunktionen einmal aufgerufen, das heißt: O(log n) + O(n) + O(1) = O(n) für die erste Iteration. \\ | ||
+ | In allen weiteren Durchläufen wird nur mehr " | ||
+ | Da es insgesamt n-1 weitere Iterationen gibt, lautet der Gesamtaufwand der weiteren Iterationen O(n) \\ | ||
+ | Insgesamt ergibt sich damit: O(n) + O(n) = O(n) | ||
- | **d)** 2. Antwort ist richtig: "kommt mit O(1) zusätzlichem Speicher aus." | + | **d)** 2. Antwort ist richtig |
**e)** 1. Antwort ist richtig: " | **e)** 1. Antwort ist richtig: " | ||
Zeile 23: | Zeile 31: | ||
**f)** 2. und 3. Antwort sind richtig | **f)** 2. und 3. Antwort sind richtig | ||
- | **g)** false, denn der " | + | **g)** false, denn der " |
- | **h)** O(log n) | + | **h)** O(log n) \\ |
+ | Begründung: | ||
+ | Ein erster Eintrag von Element x lässt sich in einer sortierten Reihung mittels binärer Suche in O(log n) finden. \\ | ||
+ | Um zu prüfen, ob (wie viele ist irrelevant!) es noch weitere Einträge von Element x gibt, muss man nur das Element rechts und links vom aktuellen betrachtet, was in O(1) geht. | ||
**i)** 2. Antwort ist richtig | **i)** 2. Antwort ist richtig | ||
Zeile 42: | Zeile 53: | ||
<code java> | <code java> | ||
- | boolean isSearchTree(){ | + | boolean isSearchTree() { |
- | return isSearchTreeAux(null, | + | if(left != null) { |
- | } | + | if(getMax(left.data) >= data || !left.isSearchTree()) |
- | + | return false; | |
- | boolean isSearchTreeAux(Integer min, Integer max){ | + | } |
- | if(min != null && data < min) | + | |
- | return false; | + | if(right != null) { |
- | + | if(getMin(right) <= data || !right.isSearchTree()) | |
- | if(max != null && | + | return false; |
- | return false; | + | } |
- | + | ||
- | if(left != null && !left.isSearchTreeAux(min, | + | |
- | return false; | + | |
- | + | ||
- | if(right | + | |
- | return false; | + | |
return true; | return true; | ||
} | } | ||
</ | </ | ||
+ | |||
+ | ?? oder vielleicht so: ?? | ||
+ | \\ | ||
+ | <code java> | ||
+ | boolean isSearchTree() { | ||
+ | if (this.left == null && this.right == null) { | ||
+ | return true; | ||
+ | } else if (this.left == null) { | ||
+ | if (this.right.getMin() > this.data) { | ||
+ | return this.right.isSearchTree(); | ||
+ | } | ||
+ | return false; | ||
+ | } else if (this.right == null) { | ||
+ | if (this.left.getMax() < this.data) { | ||
+ | return this.left.isSearchTree(); | ||
+ | } | ||
+ | return false; | ||
+ | } else { | ||
+ | if (this.left.getMax() < this.data && this.right.getMin() > this.data) { | ||
+ | return this.left.isSearchTree() && this.right.isSearchTree(); | ||
+ | } | ||
+ | return false; | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Zum Testen: https:// | ||
+ | |||
**c)** | **c)** | ||
- | * Für jeden Knoten gilt: Der Wert seiner Kinder muss größer, als sein eigener Wert sein. | + | * Für jeden Knoten gilt: Der Wert seiner Kinder muss größer als sein eigener Wert sein. |
- | * Mathematisch: | + | * Mathematisch: |
- | * In der Wurzel steht immer das Minimum des Teilbaums, also ∀ y ∈ T': value(x) ≤ value (y) | + | * In der Wurzel steht immer das Minimum des Teilbaums, also ∀y ∈ T': value(x) ≤ value(y) |
**d)** | **d)** | ||
Zeile 73: | Zeile 106: | ||
int smallest = getSmallest(); | int smallest = getSmallest(); | ||
- | // aktueller Knoten | + | // aktueller Knoten der kleinste -> fertig |
- | if(data | + | if(data |
- | if(right.data == smallest) { | + | return; |
- | swap(this, | + | |
- | right.sanitize(); | + | if(left != null && left.data == smallest) { |
- | } else { | + | swap(this, |
- | swap(this, | + | left.sanitize(); |
- | left.sanitize(); | + | } else { |
- | } | + | swap(this, |
+ | right.sanitize(); | ||
} | } | ||
} | } | ||
Zeile 88: | Zeile 122: | ||
**e)** | **e)** | ||
- | Ein AVL-Baum ist ein binärer Suchbaum, bei dem für jeden Knoten gilt: Die Höhe der beiden Teilbäume unterscheidet sich maximal um eins. | + | Ein AVL-Baum ist ein binärer Suchbaum, bei dem für jeden Knoten gilt: Die Höhe seiner |
**f)** | **f)** | ||
Zeile 110: | Zeile 144: | ||
<code java> | <code java> | ||
void getInOrderHelper(ArrayList< | void getInOrderHelper(ArrayList< | ||
- | if (left != null) | + | if(left != null) |
left.getInOrderHelper(a); | left.getInOrderHelper(a); | ||
a.add(data); | a.add(data); | ||
- | if (right != null) | + | if(right != null) |
right.getInOrderHelper(a); | right.getInOrderHelper(a); | ||
} | } | ||
Zeile 122: | Zeile 156: | ||
**h)** | **h)** | ||
- | 2. und 3. Antwort sind richtig. | + | 2. und 3. Antwort sind richtig |
==== Aufgabe 3 - Streutabellen ==== | ==== Aufgabe 3 - Streutabellen ==== | ||
Zeile 150: | Zeile 184: | ||
} | } | ||
</ | </ | ||
+ | |||
+ | Alternativ: | ||
+ | |||
+ | <code java> | ||
+ | int getIndex(String url, ArrayList< | ||
+ | return urlList.indexOf(url); | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | Bemerkung: \\ | ||
+ | Der Parameter urlList ist eigentlich überflüssig, | ||
**c)** | **c)** | ||
Zeile 161: | Zeile 206: | ||
ArrayList< | ArrayList< | ||
- | |||
int index = getIndex(url, | int index = getIndex(url, | ||
+ | |||
if(index == -1) | if(index == -1) | ||
throw new UnknownHostException(); | throw new UnknownHostException(); | ||
Zeile 174: | Zeile 219: | ||
<code java> | <code java> | ||
void resize(int h) { | void resize(int h) { | ||
- | int newBuckets = h + 1 - urls.size(); | + | while(urls.size() |
- | + | ||
- | for (int i = 0; i < newBuckets; i++) { | + | |
urls.add(new ArrayList< | urls.add(new ArrayList< | ||
ips.add(new ArrayList< | ips.add(new ArrayList< | ||
} | } | ||
} | } | ||
+ | </ | ||
+ | alternativ: | ||
+ | \\ | ||
+ | <code java> | ||
+ | void resize(int h) { | ||
+ | urls.ensureCapacity(h); | ||
+ | ips.ensureCapacity(h); | ||
+ | } | ||
</ | </ | ||
Zeile 189: | Zeile 240: | ||
int h = hash(url); | int h = hash(url); | ||
- | // Hashtabelle vergrößern, | + | // Hashtabelle vergrößern |
- | if(urls.size() <= h) | + | resize(h); |
- | resize(h); | + | |
int index = getIndex(url, | int index = getIndex(url, | ||
- | // die URL ist bereits vorhanden, es muss nur die IP aktualisiert werden | + | // URL wurde nicht gefunden -> URL und IP neu hinzufügen |
- | if(index | + | if(index |
- | ips.get(h).set(index, | + | |
- | + | ||
- | // die URL wurde nicht gefunden, URL und IP müssen neu eingefügt werden | + | |
- | } else { | + | |
urls.get(h).add(url); | urls.get(h).add(url); | ||
ips.get(h).add(ip); | ips.get(h).add(ip); | ||
+ | |||
+ | // URL ist bereits vorhanden -> aktualisiere IP | ||
+ | } else { | ||
+ | ips.get(h).set(index, | ||
} | } | ||
} | } | ||
Zeile 208: | Zeile 258: | ||
Bemerkung: \\ | Bemerkung: \\ | ||
- | Die Aufgabe baut auf der Annahme auf, dass es sich praktisch um zwei eigenständige, | + | Die Aufgabe baut auf der Annahme auf, dass es sich praktisch um zwei eigenständige, |
Nur aufgrund diese Annahme funktionieren die obigen Funktionen korrekt. | Nur aufgrund diese Annahme funktionieren die obigen Funktionen korrekt. | ||
Zeile 232: | Zeile 282: | ||
<code java> | <code java> | ||
- | public static long getPrimeDPHelper(int n, long primes[]) { | + | public static long getPrimeDPHelper(int n, long primes[]) |
- | if(n <= 0) | + | // ArrayIndexOutOfBoundsException detection (falls getPrimeDPHelper(..) falsch aufgerufen wird) |
+ | if (n >= primes.length) { | ||
+ | throw new ArrayIndexOutOfBoundsException(" | ||
+ | } | ||
+ | |||
+ | | ||
return 2; | return 2; | ||
- | + | ||
- | if(primes[n] == 0) { | + | // Geforderte Primzahl wurde noch nicht berechnet |
+ | if (primes[n] == 0) { | ||
+ | // Berechne den vorherige Primzahl | ||
long p = getPrimeDPHelper(n - 1, primes); | long p = getPrimeDPHelper(n - 1, primes); | ||
+ | // Berechne ausgehend von der vorherigen, die aktuelle Primzahl | ||
do { | do { | ||
p++; | p++; | ||
Zeile 265: | Zeile 323: | ||
| 0 | 11 | 16 | 3 | 7 | 7 | [17] | | | 0 | 11 | 16 | 3 | 7 | 7 | [17] | | ||
| 0 | 11 | 16 | 3 | 7 | 7 | 17 | | | 0 | 11 | 16 | 3 | 7 | 7 | 17 | | ||
+ | |||
+ | alternativ: | ||
+ | |||
+ | ^ Kara ^ A ^ B ^ C ^D ^E ^ Klee ^ | ||
+ | | [0] | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | | ||
+ | | | ∞ | 18< | ||
+ | | | 13< | ||
+ | | | 11< | ||
+ | | | [11< | ||
+ | | | | [16< | ||
+ | | | | | | | | [17< | ||
+ | | | | | | | | | | ||
+ | |||
+ | Indizes rückwärts (von unten nach oben) durchgehen : [17< | ||
+ | |||
+ | => umdrehen: Klara -> C -> E -> A -> Klee | ||
**b)** | **b)** | ||
- | Kürzester Pfad: Kara -> C -> E -> A -> Klee | + | Kürzester Pfad: \\ |
+ | Kara -> C -> E -> A -> Klee | ||
**c)** | **c)** | ||
Zeile 282: | Zeile 357: | ||
< | < | ||
IA_0 (n = 0): | IA_0 (n = 0): | ||
- | C0 = (0 + 2) * 2^(0 - 1) = 2 * 2^(-1) = 2 / 2 = 1 | + | C_0 = (0 + 2) * 2^(0 - 1) = 2 * 2^(-1) = 2 / 2 = 1 |
- | cpRec(0) = 1 | + | cpRec(0) = 1 (Basisfall) |
IA_1 (n = 1): | IA_1 (n = 1): | ||
- | C1 = (1 + 2) * 2^(1 - 1) = 3*2^0 = 3 * 1 = 3 | + | C_1 = (1 + 2) * 2^(1 - 1) = 3*2^0 = 3 * 1 = 3 |
- | cpRec(1) = 3 | + | cpRec(1) = 3 (Basisfall) |
</ | </ | ||
Zeile 294: | Zeile 369: | ||
< | < | ||
IV_(n-2) (n-2): | IV_(n-2) (n-2): | ||
- | cpRec(n-2) = C_(n-2) | + | cpRec(n-2) = C_(n-2) |
IV_(n-1) (n-1): | IV_(n-1) (n-1): | ||
- | cpRec(n-1) = C_(n-1) | + | cpRec(n-1) = C_(n-1) |
</ | </ | ||
Aus dem Programmfragment ist zu entnehmen: | Aus dem Programmfragment ist zu entnehmen: | ||
< | < | ||
- | cpRec(n) = 4 * cpRec(n-1) - 4 * cpRec(n-2) = | + | cpRec(n) = 4 * cpRec(n-1) - 4 * cpRec(n-2) = ... |
</ | </ | ||
- | über die obigen Induktionsvoraussetzungen kommt man auf: | + | Über die obigen Induktionsvoraussetzungen kommt man auf: |
< | < | ||
- | = 4 * C_(n-1) - 4 * C_(n-2) = | + | ... = 4 * C_(n-1) - 4 * C_(n-2) = |
= 4 * [((n - 1) + 2) * 2^((n - 1) - 1)] - 4 * [((n - 2) + 2) * 2^((n - 2) - 1)] = | = 4 * [((n - 1) + 2) * 2^((n - 1) - 1)] - 4 * [((n - 2) + 2) * 2^((n - 2) - 1)] = | ||
= 4 * [(n + 1) * 2^(n - 2)] - 4 * [n * 2^(n - 3)] = | = 4 * [(n + 1) * 2^(n - 2)] - 4 * [n * 2^(n - 3)] = | ||
Zeile 327: | Zeile 402: | ||
< | < | ||
LO: Falsch | LO: Falsch | ||
- | n ≥ 0; a = 1; k = n - 1; p = 1; | + | n ≥ 0; a = 1; k = n - 1; p = 1; n > 0 (IF-Bedingung) |
- | a = (n + 2) * 2^(n - 1) | + | (a = (n + 2) * 2^(n - 1)) = (1 = (n + 2) * 2^(n - 1)) |
-> kann nicht für jedes n ≥ 0 gelten | -> kann nicht für jedes n ≥ 0 gelten | ||
RO: Falsch | RO: Falsch | ||
- | n ≥ 0; a = 1; k = n - 1; p = 1; | + | n ≥ 0; a = 1; k = n - 1; p = 1; n > 0 (IF-Bedingung) |
- | p = 2^(n - k) = 2^(n - (n - 1)) = 2^1 = 2 | + | (p = 2^(n - k)) = (1 = 2^(n - (n - 1))) = |
+ | (1 = 2^1) = (1 = 2) | ||
-> stimmt nicht | -> stimmt nicht | ||
LU: Richtig | LU: Richtig | ||
- | n ≥ 0; a = 1; k = n - 1; p = 1; | + | n ≥ 0; a = 1; k = n - 1; p = 1; n > 0 (IF-Bedingung) |
- | (p = 2^(n - k - 1) ∧ k ≥ 0) = (p = 2^(n - (n - 1) - 1) ∧ n - 1 ≥ 0) = | + | (p = 2^(n - k - 1) ∧ k ≥ 0) = (1 = 2^(n - (n - 1) - 1) ∧ n - 1 ≥ 0) = |
- | (p = 2^0 ∧ n - 1 ≥ 0) = (p = 1 ∧ n - 1 ≥ 0) | + | (1 = 2^0 ∧ n - 1 ≥ 0) = (1 = 1 ∧ n - 1 ≥ 0) |
+ | Falls n eine Ganzzahl ist, folgt: (n > 0) ∧ (n - 1 ≥ 0) = true | ||
-> stimmt | -> stimmt | ||
RU: Falsch | RU: Falsch | ||
- | n ≥ 0; a = 1; k = n - 1; p = 1; | + | n ≥ 0; a = 1; k = n - 1; p = 1; n > 0 (IF-Bedingung) |
- | C_k = (k + 2) * p -> p = 2^(k - 1) | + | (C_k = (k + 2) * p) = (C_(n-1) = (n + 1) * 1) = |
+ | (C_(n-1) = n + 1) | ||
-> kann nicht für jedes n ≥ 0 gelten | -> kann nicht für jedes n ≥ 0 gelten | ||
</ | </ | ||
Zeile 379: | Zeile 457: | ||
(p * 2 = 2^(n - k) ∧ k > 0) | (p * 2 = 2^(n - k) ∧ k > 0) | ||
- | |||
{I ∧ b} => wp(A, I) = | {I ∧ b} => wp(A, I) = | ||
Zeile 402: | Zeile 479: | ||
</ | </ | ||
- | **e)** | + | einfacher: |
+ | < | ||
+ | Zu zeigen: (I ∧ b) => wp(B, I) | ||
- | (unsicher) | + | I: p = 2^(n - k - 1) ∧ k ≥ 0 |
+ | b: (k > 0) | ||
+ | B: "p *= 2; k--" <=> "p = p * 2; k = k - 1;" | ||
+ | |||
+ | (I ∧ b): | ||
+ | p = 2^(n - k - 1) ∧ k ≥ 0 ∧ k > 0 | ||
+ | <=> p = 2^(n - k - 1) ∧ k > 0 (weil: (k ≥ 0 ∧ k > 0) <=> (k > 0)) | ||
+ | |||
+ | wp(B, I): | ||
+ | wp("p = p * 2; k = k - 1;", p = 2^(n - k - 1) ∧ k ≥ 0) | ||
+ | <=> wp("p = p * 2;", p = 2^(n - (k - 1) - 1) ∧ k - 1 ≥ 0) | ||
+ | <=> wp("p = p * 2;", p = 2^(n - k) ∧ k ≥ 1) | ||
+ | <=> wp(" ", p * 2 = 2^(n - k) ∧ k ≥ 1) | ||
+ | <=> p * 2 = 2^(n - k) ∧ k ≥ 1 | ||
+ | <=> p = (1/2) * 2^(n - k) ∧ k ≥ 1 | ||
+ | <=> p = 2^(n - k) * (1/2) ∧ k ≥ 1 | ||
+ | <=> p = 2^(n - k) * 2^(-1) ∧ k ≥ 1 (weil: (1/2) = 2^(-1)) | ||
+ | <=> p = 2^(n - k - 1) ∧ k ≥ 1 (weil: 2^(n - k) * 2^(-1) = 2^(n - k - 1)) | ||
+ | |||
+ | (I ∧ b) => wp(B, I): | ||
+ | p = (2^(n - k - 1) ∧ k > 0) | ||
+ | -> wahr, weil k > 0 <=> k ≥ 1, da k vom Datentyp " | ||
+ | |||
+ | fertig | ||
+ | </ | ||
+ | |||
+ | **e)** | ||
V := k | V := k |