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.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws13 [14.03.2018 15:27] – Evrenpruefungen:bachelor:aud:loesungws13 [15.03.2018 14:49] – Evren
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 100: 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<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 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 138: Zeile 146:
     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 184:
  
 <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>