Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Aufgabe 1 - Wissensfragen
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungLetzte ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungws13 [09.08.2017 10:54] – ab21ajus | pruefungen:bachelor:aud:loesungws13 [04.04.2019 11:18] – Nico Hambauer | ||
---|---|---|---|
Zeile 2: | Zeile 2: | ||
==== Aufgabe 1 - Wissensfragen ==== | ==== Aufgabe 1 - Wissensfragen ==== | ||
- | **a)** Falsch (MergeSort geht auch in-situ)\\ EDIT: Ich denke die Antwort hier wäre eher richtig. Nach einiger Recherche bin ich auf keine Beispielimplementierung gestoßen, die in situ arbeitet. Viele lehnen komplett ab, dass MergeSort in irgendeiner Weise in situ implementiert werden kann, andere verweisen auf sehr, sehr aufwändige und kaum mehr durchschaubare Varianten, die pseudo-in-situ arbeiten, beispielsweise mit einer " | + | **a)** Falsch (MergeSort geht auch in-situ)\\ EDIT: Ich denke die Antwort hier wäre eher richtig. Nach einiger Recherche bin ich auf keine Beispielimplementierung gestoßen, die in situ arbeitet. Viele lehnen komplett ab, dass MergeSort in irgendeiner Weise in situ implementiert werden kann, andere verweisen auf sehr, sehr aufwändige und kaum mehr durchschaubare Varianten, die pseudo-in-situ arbeiten, beispielsweise mit einer " |
**b)** Falsch (O(n²))\\ | **b)** Falsch (O(n²))\\ | ||
Zeile 22: | Zeile 22: | ||
**j)** Wahr \\ | **j)** Wahr \\ | ||
- | **k)** Wahr \\ | + | **k)** Wahr (aber nur Konstanten) |
==== Aufgabe 2 - Streuspeicherung ==== | ==== Aufgabe 2 - Streuspeicherung ==== | ||
Zeile 36: | Zeile 36: | ||
^ Buckets ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ | ^ Buckets ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ | ||
- | ^ Schlüssel | B | A | D | C | E | | + | ^ Schlüssel | B< |
**c)** | **c)** | ||
Zeile 60: | Zeile 60: | ||
} | } | ||
} | } | ||
- | </ | + | </ |
+ | \\ | ||
+ | Bessere Lösung (statt nur den übergebenen Streuwert zu überprüfen, | ||
+ | |||
+ | <code java> | ||
+ | import java.util.LinkedList; | ||
+ | |||
+ | class Streutabelle { | ||
+ | LinkedList< | ||
+ | |||
+ | Streutabelle (int size) { | ||
+ | buckets = new LinkedList[size]; | ||
+ | } | ||
+ | |||
+ | void insert (String s, int hs) { | ||
+ | assert s != null && 0 <= hs && hs < buckets.length; | ||
+ | |||
+ | for (LinkedList< | ||
+ | if (list != null && list.contains(s)) { | ||
+ | return; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | if (buckets[hs] == null) { | ||
+ | buckets[hs] = new LinkedList< | ||
+ | } | ||
+ | |||
+ | buckets[hs].addLast(s); | ||
+ | } | ||
+ | } | ||
+ | // | ||
+ | //Heisst wenn ich String x (...equals(s)) einfuege, bleibt hs gleich, also landen gleiche Strings immer im gleichen Bucket!!! Wodurch | ||
+ | //sollte der String in einem anderen Bucket landen? Bedeutet erstere Implementierung reicht fuer diese Anwendung voellig aus! | ||
+ | //Ausserdem wuerde der platz auch kaum reichen auf der Angabe fuer eine Implementierung mit dieser Fehlerbeachtung | ||
+ | </ | ||
Zeile 70: | Zeile 104: | ||
**b)** | **b)** | ||
^ s ^ a ^ b ^ c ^ d ^ e ^ f ^ | ^ s ^ a ^ b ^ c ^ d ^ e ^ f ^ | ||
- | |__0__ | infty |infty |infty |infty |infty |infty | | + | |__0__ | ∞ |∞ |∞ |∞ |∞ |∞ | |
- | | | __1__ | 6 | infty | infty | infty | infty | | + | | | __1< |
- | | | | __5__ | 8 | infty | infty | infty | | + | | | | __5< |
- | | | | | __8__ | 10 | 18 | infty | | + | | | | | __8< |
- | | | | | | __9__ | 18 | 15 | | + | | | | | | __9< |
- | | | | | | | __12__ | + | | | | | | | __12< |
- | | | | | | | | __13__ | + | | | | | | | | __13< |
**c)** | **c)** | ||
Zeile 82: | Zeile 116: | ||
**d)** | **d)** | ||
- | [s,a], [a,b], [b,d], [d,c], [d,e], [e,f] | + | ^ s | 0 | | | | | | | |
+ | ^ a | ∞ | __[s,a] 1__ | | | | | | | ||
+ | ^ b | ∞ | [s,b] 6 | | | | | | | ||
+ | ^ c | ∞ | ∞ | __[a,b] 4__ | [b,c] 6 | __[d,c] 1__ | | | | ||
+ | ^ d | ∞ | ∞ | [a,c] 7 | __[b,d] 5__ | | | | | ||
+ | ^ e | ∞ | ∞ | ∞ | [b,e] 13 | [d,e] 3 | __[d,e] 3__ | | | ||
+ | ^ f | ∞ | ∞ | ∞ | ∞ | ∞ | [c,f] 7 | __[e,f] 1__ | | ||
+ | |||
+ | => [s,a], [a,b], [b,d], [d,c], [d,e], [e,f] | ||
**e)** | **e)** | ||
Zeile 108: | Zeile 150: | ||
curr.myString = s; | curr.myString = s; | ||
} | } | ||
+ | } | ||
+ | </ | ||
+ | \\ | ||
+ | oder | ||
+ | \\ | ||
+ | <code java> | ||
+ | public class Trie { | ||
+ | // bis zu 26 Kinder; null, wenn kein Kind mit zugehoerigem Buchstaben: | ||
+ | Trie[] children = new Trie[' | ||
+ | String myString; // null, wenn keine Zeichenkette zu speichern ist | ||
+ | |||
+ | void insert(String s) { | ||
+ | assert s != null; | ||
+ | |||
+ | for (char c : s.toCharArray()) { | ||
+ | assert c >= ' | ||
+ | } | ||
+ | |||
+ | Trie curr = this; | ||
+ | |||
+ | for (int i = 0; i < s.length(); i++) { | ||
+ | int charIndex = s.charAt(i) - ' | ||
+ | |||
+ | if (curr.children[charIndex] == null) { | ||
+ | curr.children[charIndex] = new Trie(); | ||
+ | } | ||
+ | curr = curr.children[charIndex]; | ||
+ | } | ||
+ | curr.myString = s; | ||
+ | } | ||
} | } | ||
</ | </ | ||
Zeile 116: | Zeile 188: | ||
<code java> | <code java> | ||
- | void printSorted(){ | + | void printSorted() { |
- | | + | Trie curr = this; |
- | System.out.println(myString); | + | |
- | | + | |
- | | + | System.out.println(curr.myString); |
- | if(children[i] != null) { | + | } |
- | | + | |
- | } | + | |
- | | + | if (curr.children[i] != null) { |
+ | curr.children[i].printSorted(); | ||
+ | } | ||
+ | } | ||
} | } | ||
</ | </ |