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 14:33] – Evrenpruefungen:bachelor:aud:loesungws13 [05.08.2019 09:31] (aktuell) – SpeedyGonzalez
Zeile 36: Zeile 36:
  
 ^ Buckets ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^  ^ Buckets ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 
-^ Schlüssel | B | A | D | C | E |  +^ Schlüssel | B<sub>0</sub> | A<sub>0</sub> | D<sub>1</sub> | C<sub>1</sub> | E<sub>4</sub> |  
  
 **c)** **c)**
Zeile 60: Zeile 60:
      }      }
 }    }   
-</code> +</code> 
 +\\ 
 +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> 
 +import java.util.LinkedList; 
 + 
 +class Streutabelle { 
 +    LinkedList<String>[] buckets; 
 + 
 +    Streutabelle (int size) { 
 +        buckets = new LinkedList[size]; 
 +    } 
 + 
 +    void insert (String s, int hs) { 
 +        assert s != null && 0 <= hs && hs < buckets.length; 
 + 
 +        for (LinkedList<String> list : buckets) { 
 +            if (list != null && list.contains(s)) { 
 +                return; 
 +            } 
 +        } 
 + 
 +        if (buckets[hs] == null) { 
 +            buckets[hs] = new LinkedList<String>(); 
 +        } 
 + 
 +        buckets[hs].addLast(s); 
 +    } 
 +} 
 +//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>  
  
  
Zeile 70: 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 82: 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 102: 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 108: 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 116: 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>