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 15:13] – Evren | pruefungen:bachelor:aud:loesungws13 [15.03.2018 14:49] – Evren | ||
---|---|---|---|
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(); | ||
+ | } | ||
+ | } | ||
} | } | ||
</ | </ |