Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Aufgabe 1 - Wissensfragen (Übersicht)
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:bachelor:aud:loesungws13 [15.03.2018 10:29] – Evren | pruefungen:bachelor:aud:loesungws13 [05.08.2019 09:31] (aktuell) – SpeedyGonzalez | ||
---|---|---|---|
Zeile 90: | Zeile 90: | ||
} | } | ||
} | } | ||
+ | // | ||
+ | //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 112: | 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 132: | Zeile 144: | ||
| | ||
for(char c : s.toCharArray(){ | for(char c : s.toCharArray(){ | ||
- | if(curr.children[c - ' | + | if(curr.children[c - ' |
+ | | ||
+ | } | ||
curr = curr.children[c - ' | curr = curr.children[c - ' | ||
} | } | ||
Zeile 138: | Zeile 152: | ||
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 146: | Zeile 190: | ||
<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(); | ||
+ | } | ||
+ | } | ||
} | } | ||
</ | </ |