Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Lösungsversuch
Inhaltsverzeichnis
Lösungsversuch
Aufgabe 1 Wissensfragen
a) 1 und 2
b) 2 und 3
c) 4
d) 2 und 4
e) 1
f) 1 und 3
g) 3 und 4
h) 1 und 4
i) 1 und 2
j) 1 und 3
- zu 4)
- ⇒ Eine endrekursive Methode kann unmittelbar entrekursiviert werden.
- zu c)
- ⇒ Laufzeit ist O(log(n))
Aufgabe 2 Suchen und O-Kalkül
a)
static int[] searchNaive(int[] a, int z) { int[] r = null; for(int i = 0; i < a.length; i++) { for(int j = i+1; j < a.length; j++) { if(a[i] + a[j] == z) { r = new int[] {i, j}; } } } return r; }
b)
static int[] searchLinear(int[] a, int z) { int i = 1, j = a.length - 1; while(i < j) { if(a[i] + a[j] == z) { return new int[] {i, j}; } else if(a[i] + a[j] < z) { i++; } else { j--; } } }
c)
static LinkedList<Integer> searchDuplicates(int[] a, int[] b) { LinkedList<Integer> ds = new LinkedList<>(); AVLTree at = new AVLTree(); for(int x : a) { at.insert(x); } for(int x : b) { AVLNode r = at.root; while(r != null) { if(x < r.data) { r = r.left; } else if(x > r.data) { r = r.right; } else { ds.add(x); break; } } } return ds; }
Aufgabe 3 Bäume
a)
B1 | B2 | B3 | |
---|---|---|---|
Preorder: | ∧∨ab∨cd | ∨∧ab¬∨cd | ∨¬a∧¬b∨¬cd |
Inorder: | (a∨b)∧(c∨d)) | a∧b∨¬(c∨d) | ¬a∨¬b∧(¬c∨d) |
Postorder: | ab∨cd∨∧ | ab∧cd∨¬∨ | a¬b¬c¬d∨∧∨ |
b)
LinkedList<KOp> toPrefix() { LinkedList<KOp> r = new LinkedList<>(); r.add(o); for(KTree c : cs) { r.addAll(c.toPrefix()); } return r; }
static KTree fromPostfix(LinkedList<KOp> postfix) { Stack<KTree> s = new Stack<>(); for(KOp o : postfix) { switch(o) { case AND: case OR: KTree r = s.pop(); KTree l = s.pop(); s.push(new KTree(o, l, r)); break; case NOT: s.push(new KTree(o, s.pop())); break; default: s.push(new KTree(o)); } } return s.pop(); }
Aufgabe 4 Listen
a)
public boolean contains(E e) { Node cur = head; for(int l = LEVELS - 1; l >= 0; l--) { while(cur.next[l] != null && cur.next[l].e.compareTo(e) <= 0) { if(cur.next[l].e.compareTo(e) == 0) { return true; } cur = cur.next[l]; } } return false; }
b)
private Node[] getPred(E e) { Node[] last = (Node []) Array.newInstance(Node.class, LEVELS); Node cur = head; for(int l = LEVELS - 1; l >= 0; l--) { while(cur.next[l] != null && cur.next[l].e.compareTo(e) < 0) { cur = cur.next[l]; } last[l] = cur; } return last; }
c)
public boolean insert(E e) { Node newN = new Node(e); int newL = getRandomLevel(); if(contains(e)) { return false; } Node[] pred = getPred(e); for(int l = newL; l >= 0; l--) { newN.next[l] = pred[l].next[l]; pred[l].next[l] = newN; } return true; } public boolean delete(E e) { if(!contains(e)) { return false; } Node[] pred = getPred(e); for(int l = LEVELS - 1; l >= 0; l--) { if(pred[l].next[l] != null) { pred[l].next[l] = pred[l].next[l].next[l]; } } return true; }
Aufgabe 5 ADT
a)
as2gh(Create, Create, k) = Node(New, k)
as2gh(Add(n, ns), as, k) = Edge(as2gh(ns, as, k), k, n)
as2gh(Create, Add(ns, as), k) = Node(as2gh(ns, as, k+1), k)
b)
flatten(Add(Create, as)) = flatten(as)
flatten(Add(Add(n, ns), as)) = Add(n, flatten(Add(ns, as)))
c)
as2af(as) = as2afh(length(as)+1, as, flatten(as))
as2afh(si, Create, af)) = Add(si, af)
as2afh(si, Add(ns, as), af) = Add(si, as2afh(si+length(ns), as, af))
Aufgabe 6 Graphen
a)
boolean isSafe(boolean g[][], int cs[], int v, int c) { for (int n = 0; n < g.length; n++) { if (g[v][n] == true && c == cs[n]) { // Kante vorhanden und Farbe bereits vergeben return false; } } return true; }
b)
boolean helper(boolean g[][], int cs[], int m, int v) { // base case if (v >= g.length) { return true; } // try different colors for vertex v for (int c = 1; c <= m; c++) { if (isSafe(g, cs, v, c)) { int color = cs[v]; // aktuelle Farbe sichern cs[v] = c; // neue Farbe setzen if (helper(g, cs, c, v + 1)) { // Rekursion (Fehler?: sollte m statt c sein) return true; } // backtrack cs[v] = color; } } // keine Loesung gefunden -> Schritt zurueck return false; }
c)
int[] color(boolean g[][], int m) { int[] cs = new int[g.length]; if (!helper(g, cs, m, 0)) { return null; } return cs; }