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.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:bachelor:aud:loesungws13 [15.03.2018 12:33] – Evrenpruefungen:bachelor:aud:loesungws13 [05.08.2019 09:31] (aktuell) – SpeedyGonzalez
Zeile 90: Zeile 90:
     }     }
 } }
 +//Anmerkung: hier wird allerdings immer der gleiche hashcode fuer einen String s verwendet, den ich mehrfach einfuege.
 +//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
 </code>   </code>  
  
Zeile 113: Zeile 117:
 **d)** **d)**
 ^ s | 0 | | | | | | | ^ s | 0 | | | | | | |
-^ a | ∞ | [s,a] 1 | | | | | |+^ a | ∞ | __[s,a] 1__ | | | | | |
 ^ b | ∞ | [s,b] 6 | | | | | | ^ b | ∞ | [s,b] 6 | | | | | |
-^ c | ∞ | ∞ | [a,b] 4 | [b,c] 6 | [d,c] 1 | | | +^ c | ∞ | ∞ | __[a,b] 4__ | [b,c] 6 | __[d,c] 1__ | | | 
-^ d | ∞ | ∞ | [a,c] 7 | [b,d] 5 | | | | +^ d | ∞ | ∞ | [a,c] 7 | __[b,d] 5__ | | | | 
-^ e | ∞ | ∞ | ∞ | [b,e] 13 | [d,e] 3 | [d,e] 3 | | +^ e | ∞ | ∞ | ∞ | [b,e] 13 | [d,e] 3 | __[d,e] 3__ | | 
-^ f | ∞ | ∞ | ∞ | ∞ | ∞ | [c,f] 7 | [e,f] 1 |+^ f | ∞ | ∞ | ∞ | ∞ | ∞ | [c,f] 7 | __[e,f] 1__ |
  
 => [s,a], [a,b], [b,d], [d,c], [d,e], [e,f] => [s,a], [a,b], [b,d], [d,c], [d,e], [e,f]
Zeile 140: Zeile 144:
          
     for(char c : s.toCharArray(){     for(char c : s.toCharArray(){
-      if(curr.children[c - 'A'] == null) curr.children[c-'A'] = new Trie();+      if(curr.children[c - 'A'] == null){ 
 +            curr.children[c-'A'] = new Trie(); 
 +      }
       curr = curr.children[c - 'A'];       curr = curr.children[c - 'A'];
     }     }
Zeile 146: Zeile 152:
     curr.myString = s;     curr.myString = s;
   }   }
 +}
 +</code>
 +\\
 +oder
 +\\
 +<code java>
 +public class Trie {
 +    // bis zu 26 Kinder; null, wenn kein Kind mit zugehoerigem Buchstaben:
 +    Trie[] children = new Trie['Z' - 'A' + 1];
 +    String myString; // null, wenn keine Zeichenkette zu speichern ist
 +
 +    void insert(String s) {
 +        assert s != null;
 +
 +        for (char c : s.toCharArray()) {
 +            assert c >= 'A' && c <= 'Z';
 +        }
 +
 +        Trie curr = this;
 +
 +        for (int i = 0; i < s.length(); i++) {
 +            int charIndex = s.charAt(i) - 'A';
 +
 +            if (curr.children[charIndex] == null) {
 +                curr.children[charIndex] = new Trie();
 +            }
 +            curr = curr.children[charIndex];
 +        }
 +        curr.myString = s;
 +    }
 } }
 </code> </code>
Zeile 154: Zeile 190:
  
 <code java> <code java>
-void printSorted(){ +void printSorted() { 
-   if(myString != null) { +    Trie curr = this; 
-      System.out.println(myString); +     
-   } +    if (curr.myString != null) { 
-   for(int i=0; i < 26; i++){ +        System.out.println(curr.myString); 
-      if(children[i] != null) { +    } 
-         children[i].printSorted(); + 
-      } +    for (int i = 0; i < curr.children.length; i++) { 
-   }+        if (curr.children[i] != null) { 
 +            curr.children[i].printSorted(); 
 +        } 
 +    }
 } }
 </code> </code>