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.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungss17 [19.10.2017 18:06] – Lösung für Aufgabe 2 hinzugefügt jonpostpruefungen:bachelor:aud:loesungss17 [12.07.2018 06:19] – LasagneAlForno
Zeile 7: Zeile 7:
 **b)** 2 und 3 **b)** 2 und 3
  
-**c)** 2 und 4+**c)** 4
  
 **d)** 2 und 4 **d)** 2 und 4
Zeile 25: Zeile 25:
   * zu 4)   * zu 4)
     *=>  Eine endrekursive Methode kann unmittelbar entrekursiviert werden.     *=>  Eine endrekursive Methode kann unmittelbar entrekursiviert werden.
 +   * zu c) 
 +    *=>  Laufzeit ist O(log(n))
  
 ==== Aufgabe 2 Suchen und O-Kalkül ==== ==== Aufgabe 2 Suchen und O-Kalkül ====
Zeile 86: Zeile 87:
     }     }
     return ds;     return ds;
 +}
 +</code>
 +
 +====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<KOp> toPrefix() {
 +    LinkedList<KOp> r = new LinkedList<>();
 +    
 +    r.add(o);
 +    for(KTree c : cs) {
 +        r.addAll(c.toPrefix());
 +    }
 +    
 +    return r;
 +}
 +</code>
 +
 +<code java>
 +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();
 +}
 +</code>
 +
 +====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;
 +}
 +</code>
 +
 +**b)**
 +<code java>
 +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;
 +}
 +</code>
 +
 +**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;
 +}
 +</code>
 +
 +====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)**
 +<code java>
 +boolean isSafe(boolean g[][], int cs[], int v, int c) {
 +    for(int n = 0; n < g.length; n++) {
 +        if(g[v][n] && c == cs[n]) {
 +            return false;
 +        }
 +    }
 +    return true;
 +}
 +</code>
 +**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)) {
 +            //try and recurse
 +            cs[v] = c;
 +            if(helper(g, cs, m, v+1)) {
 +                return true;
 +            }
 +            //backtrack
 +            cs[v] = 0;
 +        }
 +    }
 +    //finally give up
 +    return false;
 +}
 +</code>
 +
 +**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;
 } }
 </code> </code>