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
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws13 [14.03.2018 14:33] – Evrenpruefungen:bachelor:aud:loesungws13 [04.04.2019 11:18] – Nico Hambauer
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 108: Zeile 150:
     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 188:
  
 <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>