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.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungws13 [09.08.2017 10:54] – ab21ajus | pruefungen:bachelor:aud:loesungws13 [04.04.2019 11:14] – Nico Hambauer | ||
---|---|---|---|
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 " | + | **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 " |
**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< |
**c)** | **c)** | ||
Zeile 60: | Zeile 60: | ||
} | } | ||
} | } | ||
- | </ | + | </ |
+ | \\ | ||
+ | Bessere Lösung (statt nur den übergebenen Streuwert zu überprüfen, | ||
+ | |||
+ | <code java> | ||
+ | import java.util.LinkedList; | ||
+ | |||
+ | class Streutabelle { | ||
+ | LinkedList< | ||
+ | |||
+ | Streutabelle (int size) { | ||
+ | buckets = new LinkedList[size]; | ||
+ | } | ||
+ | |||
+ | void insert (String s, int hs) { | ||
+ | assert s != null && 0 <= hs && hs < buckets.length; | ||
+ | |||
+ | for (LinkedList< | ||
+ | if (list != null && list.contains(s)) { | ||
+ | return; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | if (buckets[hs] == null) { | ||
+ | buckets[hs] = new LinkedList< | ||
+ | } | ||
+ | |||
+ | buckets[hs].addLast(s); | ||
+ | } | ||
+ | } | ||
+ | // | ||
+ | //sollte der String in einem anderen Bucket landen? Bedeutet erstere Implementierung reicht fuer diese Implementierung voellig aus! | ||
+ | //Auserdem wuerde der platz auch kaum reichen auf der Angabe fuer eine Implementierung mit dieser Fehlerbeachtung | ||
+ | </ | ||
Zeile 70: | Zeile 103: | ||
**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< |
- | | | | __5__ | 8 | infty | infty | infty | | + | | | | __5< |
- | | | | | __8__ | 10 | 18 | infty | | + | | | | | __8< |
- | | | | | | __9__ | 18 | 15 | | + | | | | | | __9< |
- | | | | | | | __12__ | + | | | | | | | __12< |
- | | | | | | | | __13__ | + | | | | | | | | __13< |
**c)** | **c)** | ||
Zeile 82: | Zeile 115: | ||
**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 149: | ||
curr.myString = s; | curr.myString = s; | ||
} | } | ||
+ | } | ||
+ | </ | ||
+ | \\ | ||
+ | oder | ||
+ | \\ | ||
+ | <code java> | ||
+ | public class Trie { | ||
+ | // bis zu 26 Kinder; null, wenn kein Kind mit zugehoerigem Buchstaben: | ||
+ | Trie[] children = new Trie[' | ||
+ | String myString; // null, wenn keine Zeichenkette zu speichern ist | ||
+ | |||
+ | void insert(String s) { | ||
+ | assert s != null; | ||
+ | |||
+ | for (char c : s.toCharArray()) { | ||
+ | assert c >= ' | ||
+ | } | ||
+ | |||
+ | Trie curr = this; | ||
+ | |||
+ | for (int i = 0; i < s.length(); i++) { | ||
+ | int charIndex = s.charAt(i) - ' | ||
+ | |||
+ | if (curr.children[charIndex] == null) { | ||
+ | curr.children[charIndex] = new Trie(); | ||
+ | } | ||
+ | curr = curr.children[charIndex]; | ||
+ | } | ||
+ | curr.myString = s; | ||
+ | } | ||
} | } | ||
</ | </ | ||
Zeile 116: | Zeile 187: | ||
<code java> | <code java> | ||
- | void printSorted(){ | + | void printSorted() { |
- | | + | Trie curr = this; |
- | System.out.println(myString); | + | |
- | | + | |
- | | + | System.out.println(curr.myString); |
- | if(children[i] != null) { | + | } |
- | | + | |
- | } | + | |
- | | + | if (curr.children[i] != null) { |
+ | curr.children[i].printSorted(); | ||
+ | } | ||
+ | } | ||
} | } | ||
</ | </ |