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
pruefungen:bachelor:aud:loesungss17 [19.10.2017 18:06] – Lösung für Aufgabe 2 hinzugefügt jonpostpruefungen:bachelor:aud:loesungss17 [05.03.2020 12:05] (aktuell) – amelie.ka
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] == true && c == cs[n]) {
 +             // Kante vorhanden und Farbe bereits vergeben
 +            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)) {
 +            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;
 +}
 +</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>