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 ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungws13 [14.03.2018 14:31] – Evren | pruefungen:bachelor:aud:loesungws13 [15.03.2018 14:49] – Evren | ||
---|---|---|---|
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 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); | ||
+ | } | ||
+ | } | ||
+ | </ | ||
Zeile 70: | Zeile 100: | ||
**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 112: | ||
**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 146: | ||
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 184: | ||
<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(); | ||
+ | } | ||
+ | } | ||
} | } | ||
</ | </ |