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 [09.08.2017 10:55] – ab21ajuspruefungen:bachelor:aud:loesungws13 [05.08.2019 09:31] (aktuell) – SpeedyGonzalez
Zeile 2: Zeile 2:
 ==== Aufgabe 1 - Wissensfragen ==== ==== Aufgabe 1 - Wissensfragen ====
  
-**a)** Falsch (MergeSort geht auch in-situ)\\ EDIT: Ich denke die Antwort hier wäre eher richtig. Nach einiger Recherche bin ich auf keine Beispielimplementierung gestoßen, die in situ arbeitet. Viele lehnen komplett ab, dass MergeSort in irgendeiner Weise in situ implementiert werden kann, andere verweisen auf sehr, sehr aufwändige und kaum mehr durchschaubare Varianten, die pseudo-in-situ arbeiten, beispielsweise mit einer "Work-Area" innerhalb eines Arrays, die man wohl in 99% der Fälle erstmal selbst anlegen muss (Was den Aufwand noch höher treibt auf n²*log(n)).+**a)** Falsch (MergeSort geht auch in-situ)\\ EDIT: Ich denke die Antwort hier wäre eher richtig. Nach einiger Recherche bin ich auf keine Beispielimplementierung gestoßen, die in situ arbeitet. Viele lehnen komplett ab, dass MergeSort in irgendeiner Weise in situ implementiert werden kann, andere verweisen auf sehr, sehr aufwändige und kaum mehr durchschaubare Varianten, die pseudo-in-situ arbeiten, beispielsweise mit einer "Work-Area" innerhalb eines Arrays, die man wohl in 99% der Fälle erstmal selbst anlegen muss (Was den Aufwand noch höher treibt auf n²*log(n) und somit die komplette Implementierung, sofern das Array nicht bereits mit Work-Area inklusive an die Methode übergeben wird, völlig schwachsinnig macht.).\\ EDIT 2: MergeSort wird in der Regel nicht in-situ durchgeführt (Quelle: Vorlesungsfolien WS17/18)  
  
 **b)** Falsch (O(n²))\\ **b)** Falsch (O(n²))\\
Zeile 22: Zeile 22:
 **j)** Wahr \\ **j)** Wahr \\
  
-**k)** Wahr \\+**k)** Wahr (aber nur Konstanten) \\
  
 ==== Aufgabe 2 - Streuspeicherung ==== ==== Aufgabe 2 - Streuspeicherung ====
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>