Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

--- pruefungen:bachelor:aud:loesungws14 [08.07.2015 12:55] – Phreek90
+++ pruefungen:bachelor:aud:loesungws14 [07.04.2022 17:18] – Kruskal korrigiert BobbyB
@@ Zeile 1: / Zeile 1: @@
-===== Forendiskussion =====
+===== Forendiskussionen =====
-https://fsi.informatik.uni-erlangen.de/forum/thread/12767-klausur-WS2014
+  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/12767-klausur-WS2014|Aufgabe 1]]
+  * [[https://fsi.cs.fau.de/forum/thread/12844-WS14-ADT|Aufgabe 6]]
+  * [[https://fsi.cs.fau.de/forum/thread/17211-Mit-this-keyword-auf-Variablen-zugreifen-WS14-Auf|Aufgabe 7]]
 ===== Lösungsversuch =====
@@ Zeile 31: / Zeile 33: @@
         int index = 0; //write index
         do {
-            for(int i = 0; i < in[c]; i++) {
+            for(int i = 0; i < count[c]; i++) {
-                in[index++] += 1;
+                in[index++] = c;
             }
             c++;
-        } while (c < count.length && index < in.length);
+        } while (index < in.length);
     }
 }
 </code>
 d) O(n)\\
-e) NEIN, es ist nicht widerlegt, da es sich hier nicht um ein vergleichsbasiertes Sorierverfahren handelt (Wo bitte schön soll der Vergleich sein?)
+e) NEIN, es ist nicht widerlegt, da es sich hier nicht um ein **nicht** vergleichsbasiertes Sortierverfahren handelt!
 ==== Aufgabe 3 - Prim vs. Kruskal (10) ====
 a) (A,B) -- (B,D) -- (B,C)\\
-b) (B,D) -- (A,D) -- (D,C)\\
+b) (B,D) -- (A,B) -- (B,C)\\
 c) NEIN
@@ Zeile 72: / Zeile 74: @@
         int pos = hk; //current position during exploration
         do { //b)
-            for(int i = 0; i < map[pos].length; i++) {
+            for(int i = 0; i < b; i++) {
-                if(map[pos][i] == null) {
+                if(map[pos][i] == null || map[pos][i].equals(k)) { //keine NullPointerException dank lazy evaluation
-                    map[pos|[i] = k;
-                    return null;
-                } else if(map[pos][i].equals(k)) {
                     K kold = map[pos][i];
                     map[pos][i] = k;
                     return kold;
                 }
-                pos += c;
-                pos %= map.length;
             }
+            pos = (pos + c) % s;
         } while (pos != hk);
@@ Zeile 110: / Zeile 108: @@
 long bDP(int n, int m) {
     long[][] mem = new long[n + 1][m + 1];
-    for(int i = 0; i < n; i++) {
+    for(int i = 0; i <= n; i++) {
-        for(int j = 0; j < m; j++) {
+        for(int j = 0; j <= m; j++) {
-            if((n<m) || (m == 0 && n != 0)) {
+            if(j >= 1 && j <= i-1) {
+                mem[i][j] = (3*(i-1)*mem[i-1][j] + j*mem[i-1][j-1])/i;
+            } else if((i<j) || (j == 0 && i != 0)) {
                 mem[i][j] = 0;
-            } else if(n == m) {
+            } else if(i == j) {
                 mem[i][j] = 1;
-            } else {
-                mem[i][j] = (3*(n-1)*b(n-1,m) + m*b(n-1,m-1))/n;
             }
         }
@@ Zeile 140: / Zeile 138: @@
     nat2bin(n) = push(nat2bin(div(n, succ(succ(zero)))), mod(n, succ(succ(zero))))
 </code>
-c) ???
+c)
+<code>
+axs
+    bin2nat(empty) = zero
+    bin2nat(push(S,N)) = add(N,mult(bin2nat(S),succ(succ(zero)))) // (N + 2*bin2nat(S))
+</code>
 ==== Aufgabe 7 - Doppelverkettung (29) ====
+a+b) <code java>
+class DLNode<V> {
+    DLNode<V> a; //Referenz auf Vorgänger
+    V v; //Aktuelles Element
+    DLNode<V> z; //Referenz auf Nachfolger
+    boolean isDLL() { //Aufgabe (a), checks if this node is part of a Doubly Linked List
+        DLNode<V> d = this, c = this.a; //drag/current pointers
+        boolean searchedEverything = false;
+        while(!searchedEverything) {
+            if(!(d.z.a == d && d.a.z == d)) {
+                return false;
+            }
+            d = d.z;
+            if(d == this || d == null || (d.z == null && d.a.z == d)) {
+                searchedEverything = true;
+                break;
+            }
+        }
+        d = this;
+        searchedEverything = false;
+        while(!searchedEverything) {
+            if(!(d.z.a == d && d.a.z == d)) {
+                return false;
+            }
+            d = d.a;
+            if(d == this || d == null || (d.a == null && d.z.a == d)) {
+                searchedEverything = true;
+                break;
+            }
+        }
+        return true;
+    }
+    // Andere Lösung, die weniger Vergleiche hat
+    // IMHO ist jeweils ein Vergleich in den jeweils ersten IFs in den WHILEs redundant.
+    // Außerdem überprüft diese Lösung, ob die DLL auch in beide Richtungen zirkulär ist, wenn sie in eine Richtung zirkulär ist.
+    boolean isDLL() {
+      DLNode<V> d = this, c = this.a;
+      while (c != this && c != null) {
+        if (c.z != d) {
+          return false;
+        }
+        d = c;
+        c = c.z; //Anmerkung anderer Student: müsste mMn c = c.a sein
+      }
+      // Anmerkung anderer Student: Das Zuruecksetzen von d fehlt mMn, da man ja unten mit dem oben veraenderten c weitermacht . Hab es mal hier drunter eingefuegt
+      d = this;
+      DLNode<V> e = this.z;
+      while (e != this && e != null) {
+        if (e.a != d) {
+          return false;
+        }
+        d = e;
+        e = e.a; //Anmerkung anderer Student: müsste mMn e = e.z sein
+      }
+      // Either both null (non-circular) or both not null (circular in both directions!)
+      return ((c == null && e == null) || (c != null && e != null));
+    }
+    boolean isLoopedDLL() { //Aufgabe (b), checks if this node is part of a Looped DLL
+        DLNode<V> c = this.a;
+        if(!isDLL()) {
+            return false;
+        } else {
+            while(c != this) {
+                // Zuerst null-Check, c kann hier bereits null sein!
+                if(c == null) {
+                    return false;
+                }
+                c = c.a;
+            }
+            c = this.z;
+            while(c != this) {
+                if(c == null) {
+                    return false;
+                }
+                c = c.z;
+            }
+            return true;
+        }
+    }
+}
+</code>
+c+d) <code java>
+class PriorityDeque<V extends Comparable<V>> {
+    DLNode<V> h; //highest prio node (null if empty)
+    V get(boolean high) { //Aufgabe (c)
+        DLNode<V> r = h; //will finally point to requested node
+        //list is empty
+        if(h == null) {
+            throw new NoSuchElementException("[Error] List is empty!");
+        }
+        //list has only on single node - just empty the deque
+        else if(h.a == null || h.a == h) {
+            h = null;
+        }
+        //user requested head - reconfigure internal head pointer
+        else if(high) {
+            h = h.z;
+        }
+        //user requested node that preceeds head - retarget r
+        else {
+            r = h.a;
+        }
+        //unlink requested node r and return its value
+        r.a.z = r.z;
+        r.z.a = r.a;
+        return r.v;
+    }
+    void put(V v) { //Aufgabe (d)
+        DLNode<V> c = h; //current node (drag)
+        DLNode<V> n = new DLNode<V>(); n.v = v; n.a = n.z = n;
+        if(c == null || c.v.compareTo(v) < 0) {
+            //n becomes new head
+            h = n;
+        } else {
+            //search node c that immediately succeeds n
+            do {
+                c = c.z;
+            } while (c.v.compareTo(v) >= 0 && c != h);
+        }
+        //insert/link n before c, if c exists
+        if(c != null) {
+            c.a.z = n;
+            n.a = c.a;
+            n.z = c;
+            c.a = n;
+        }
+    }
+}
+</code>