Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Aufgabe 1 - Wissensfragen
Inhaltsverzeichnis
Keine Garantie für Korrektheit. Falls etwas nicht passen sollte, einfach ausbessern.
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) 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²))
c) Falsch (O(k * n))
d) Falsch (Direkt erreichbaren)
e) Wahr
f) Falsch (O(n), irrelevant ob einfach oder doppelt verkettet)
g) Falsch
h) Falsch
i) Falsch (Rechter Ast, B über D)
j) Wahr
k) Wahr (aber nur Konstanten)
Aufgabe 2 - Streuspeicherung
a)
Buckets | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
Schlüssel | B | A | |||
D | C | ||||
E |
b)
Buckets | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
Schlüssel | B0 | A0 | D1 | C1 | E4 |
c)
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; if(buckets[hs] == null){ buckets[hs] = new LinkedList<String>(); } if(!buckets[hs].contains(s)){ buckets[hs].addLast(s); } } }
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“):
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
Aufgabe 3 - Graphalgorithmen
a) s → (a,1) → (b,6)
a → (b,4) → (c,7)
b → (c,6) → (d,5) → (e,13)
c → (d,1) → (f,7)
d → (e,3)
e → (f,1)
f → (,)
b)
s | a | b | c | d | e | f |
---|---|---|---|---|---|---|
0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
1s | 6s | ∞ | ∞ | ∞ | ∞ | |
5a | 8a | ∞ | ∞ | ∞ | ||
8a | 10b | 18b | ∞ | |||
9c | 18b | 15c | ||||
12d | 15c | |||||
13e |
c) s → a → c → d → e → f
d)
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) true
Aufgabe 4 - Bäume
a)
public class Trie{ Trie[] children = new Trie['Z'-'A'+1]; String myString; void insert(String s){ assert s != null; for(char c : s.toCharArray()) assert c >= ’A’ && c <= ’Z’; Trie curr = this; for(char c : s.toCharArray(){ if(curr.children[c - 'A'] == null){ curr.children[c-'A'] = new Trie(); } curr = curr.children[c - 'A']; } curr.myString = s; } }
oder
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; } }
b) O(n)
c)
void printSorted() { Trie curr = this; if (curr.myString != null) { System.out.println(curr.myString); } for (int i = 0; i < curr.children.length; i++) { if (curr.children[i] != null) { curr.children[i].printSorted(); } } }
Aufgabe 5 - Dynamische Programmierung
a)
void initDP() { dp = new int[g.length][k+1]; //erste Spalte initialisieren for(int i = 0; i < dp.length; i++) { dp[i][0] = 0; } }
b)
void fillSingle(int i, int restk) { if(i == 0) { /* ... */ } else { int without = dp[i-1][restk]; int with = 0; if (g[i] <= restk){ with = dp[i-1][restk-g[i]] + w[i]; } dp[i][restk] = Math.max(with, without); } }
c)
void solve() { initDP(); for(int i = 0; i < g.length; i++) { // <=, da dp[i] jeweils von 0 bis k (inklusive) reicht for(int restk = 0; restk <= k; restk++) { fillSingle(i, restk); } } return dp[g.length - 1][k]; }
Aufgabe 6 - Abstrakte Datentypen
a)
ops: head: FunList -> T tail: FunList -> FunList axs: head(nil) = null; head(cons(t, l)) = t; tail(cons(t, l)) = l; tail(nil) = nil;
b)
Vorschlag:
ops: concat: FunList x FunList -> FunList axs: // ggf. die folgenden beide nochmal trennen in // anyFunList = cons(e, l) und anyFunList = nil // Sollte so aber eigtl. passen, auch wenn (nil, nil) auf beide // matcht, da in beiden Fällen dasselbe (nil) rauskommt concat(nil, anyFunList) = anyFunList concat(anyFunList, nil) = anyFunList concat(cons(elem1, list1), cons(elem2, list2)) = cons(elem1, concat(list1, cons(elem2, list2)))
c)
Entnommen aus dem Tafelfoliensatz zur Übung 9, Folie 7 / 44: https://www2.cs.fau.de/teaching/WS2015/AuD/uebungen/secure/uebung09_handout.pdf
ops filter: Pred x FunList -> FunList axs filter(p, nil) = nil filter(p, cons(t, l)) = { cons(t, filter(p, l)) falls apply(p, t) filter(p, l) sonst
Aufgabe 7 (Backtracking)
a)
boolean isSolved(int[][] sq){ int n = sq.length; int checkSum = ((n * n * n) + n) / 2; int rowSum = 0, colSum = 0, diag1Sum = 0, diag2Sum = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ rowSum += sq[i][j]; colSum += sq[j][i]; } if(rowSum != checkSum || colSum != checkSum){ return false; } else { rowSum = colSum = 0; } } for(int i = 0; i < n; i++){ diag1Sum += sq[i][i]; diag2Sum += sq[n - 1 - i][i]; } if(diag1Sum != checkSum || diag2Sum != checkSum){ return false; } return true; }
b)
boolean solve(int [][] sq, int pos, boolean [] used) { int n = sq.length; int col = pos % n; int row = (pos - col) / n; if(pos >= used.length){ return isSolved(sq); } else { for(int i = 1; i <= used.length; i++){ if(used[i-1] == false){ sq[col][row] = i; used[i-1] = true; if(solve(sq, pos+1, used)){ return true; } sq[col][row] = 0; used[i-1] = false; } } } return false; }
Aufgabe 8 - Schreibtischlauf
Zeilennummer | Fehlerbeschreibung |
---|---|
4 | Mehrfachvererbung existiert in Java nicht |
12 | Kein explizites Casting von double nach int |
14 | final-Werte sind konstant, hier wird versucht ein final-Wert zu überschreiben |
16 | Zuweisung ist kein Boolean-Wert, kann somit nicht in der if-Abfrage stehen |
20 | nicht-statische Variable kann nicht aus statischem Kontext aufgerufen werden |
24 | Es existiert keine Variable k (mehr) |
25 | : fehlt im tenären Operator |
28 | switch fehlt (Herrenloses case) |
34 | double zurückgegeben, int erwartet (→ selber Fehler wie in Zeile 12) |
38 | Exception muss via throws MyException deklariert werden, kann nicht so wie hier einfach so geworfen werden |
41 | abstrakte Methode in nicht abstrakter Klasse |