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 [14.03.2018 15:27] – Evrenpruefungen:bachelor:aud:loesungws13 [05.08.2019 09:31] (aktuell) – SpeedyGonzalez
Zeile 61: Zeile 61:
 }    }   
 </code> </code>
- +\\ 
-bessere Lösung (statt nur den übergebenen Streuwert zu überprüfen, werden hier alle Streuwerte durchgegangen und geprüft ob der String s in irgendeiner LinkedList, weil in der Aufgabenstellung steht "Beachten Sie bitte, dass jeder Schlüssel höchstens einmal **in der Streutabelle** vorkommen darf"):+Bessere Lösung (statt nur den übergebenen Streuwert zu überprüfen, werden hier alle Streuwerte durchgegangen und geprüft ob sich der String s in irgendeiner LinkedList befindet, weil in der Aufgabenstellung steht "Beachten Sie bitte, dass jeder Schlüssel höchstens einmal **in der Streutabelle** vorkommen darf"):
  
 <code java> <code java>
Zeile 78: Zeile 78:
  
         for (LinkedList<String> list : buckets) {         for (LinkedList<String> list : buckets) {
-            if (list !=null && list.contains(s)) {+            if (list != null && list.contains(s)) {
                 return;                 return;
             }             }
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 100: 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<sub>s</sub>__ | 6<sub>s</sub> | ∞ | ∞ | ∞ | ∞ | 
-| | | __5__ | 8 | infty | infty | infty |  +| | | __5<sub>a</sub>__ | 8<sub>a</sub> | ∞ | ∞ | ∞ |  
-| | | | __8__ | 10 | 18 | infty | +| | | | __8<sub>a</sub>__ | 10<sub>b</sub> | 18<sub>b</sub> | ∞ | 
-| | | | | __9__ | 18 | 15 | +| | | | | __9<sub>c</sub>__ | 18<sub>b</sub> | 15<sub>c</sub> | 
-| | | | | | __12__ | 15 | +| | | | | | __12<sub>d</sub>__ | 15<sub>c</sub> | 
-| | | | | | | __13__ |+| | | | | | | __13<sub>e</sub>__ |
  
 **c)** **c)**
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 - '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 138: 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 146: 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>