Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Lösungsversuch (Übersicht)
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Nächste Überarbeitung | Vorherige ÜberarbeitungLetzte ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungss17 [19.10.2017 17:42] – angelegt jonpost | pruefungen:bachelor:aud:loesungss17 [24.07.2019 14:44] – Kleine Verbesserung in Aufgabe 6b) + Formatierung angepasst. dom | ||
---|---|---|---|
Zeile 7: | Zeile 7: | ||
**b)** 2 und 3 | **b)** 2 und 3 | ||
- | **c)** | + | **c)** 4 |
**d)** 2 und 4 | **d)** 2 und 4 | ||
Zeile 23: | Zeile 23: | ||
**j)** 1 und 3 | **j)** 1 und 3 | ||
+ | * zu 4) | ||
+ | *=> | ||
+ | * zu c) | ||
+ | *=> | ||
+ | |||
+ | ==== Aufgabe 2 Suchen und O-Kalkül ==== | ||
+ | |||
+ | **a)** | ||
+ | <code java> | ||
+ | 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)** | ||
+ | <code java> | ||
+ | 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)** | ||
+ | <code java> | ||
+ | static LinkedList< | ||
+ | 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)** | ||
+ | <code java> | ||
+ | LinkedList< | ||
+ | LinkedList< | ||
+ | | ||
+ | r.add(o); | ||
+ | for(KTree c : cs) { | ||
+ | r.addAll(c.toPrefix()); | ||
+ | } | ||
+ | | ||
+ | return r; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | <code java> | ||
+ | static KTree fromPostfix(LinkedList< | ||
+ | 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)** | ||
+ | <code java> | ||
+ | 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)** | ||
+ | <code java> | ||
+ | private Node[] getPred(E e) { | ||
+ | Node[] last = (Node []) Array.newInstance(Node.class, | ||
+ | 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)** | ||
+ | <code java> | ||
+ | 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, | ||
+ | |||
+ | as2gh(Add(n, | ||
+ | |||
+ | as2gh(Create, | ||
+ | |||
+ | **b)** | ||
+ | |||
+ | flatten(Add(Create, | ||
+ | |||
+ | flatten(Add(Add(n, | ||
+ | |||
+ | **c)** | ||
+ | |||
+ | as2af(as) = as2afh(length(as)+1, | ||
+ | |||
+ | as2afh(si, Create, af)) = Add(si, af) | ||
+ | |||
+ | as2afh(si, Add(ns, as), af) = Add(si, as2afh(si+length(ns), | ||
+ | |||
+ | ====Aufgabe 6 Graphen==== | ||
+ | **a)** | ||
+ | <code java> | ||
+ | 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)** | ||
+ | <code java> | ||
+ | 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]; | ||
+ | cs[v] = c; // neue Farbe setzen | ||
+ | | ||
+ | if (helper(g, cs, c, v + 1)) { // Rekursion | ||
+ | return true; | ||
+ | } | ||
+ | // backtrack | ||
+ | cs[v] = color; | ||
+ | } | ||
+ | } | ||
+ | // keine Loesung gefunden -> Schritt zurueck | ||
+ | return false; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | **c)** | ||
+ | <code java> | ||
+ | int[] color(boolean g[][], int m) { | ||
+ | int[] cs = new int[g.length]; | ||
+ | | ||
+ | if (!helper(g, cs, m, 0)) { | ||
+ | return null; | ||
+ | } | ||
+ | return cs; | ||
+ | } | ||
+ | </ |