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

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws14 [08.07.2015 18:27] – Fehlende Aufgabe Nummer 7 hinzugefügt, 6c fehlt immer noch teilweise Phreek90pruefungen: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 ===== ===== Lösungsversuch =====
Zeile 31: Zeile 33:
         int index = 0; //write index         int index = 0; //write index
         do {         do {
-            for(int i = 0; i < in[c]; i++) { +            for(int i = 0; i < count[c]; i++) { 
-                in[index++] += 1;+                in[index++] = c;
             }             }
             c++;             c++;
-        } while (c < count.length && index < in.length);+        } while (index < in.length);
     }     }
 } }
 </code> </code>
 d) O(n)\\  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) ==== ==== Aufgabe 3 - Prim vs. Kruskal (10) ====
 a) (A,B) -- (B,D) -- (B,C)\\  a) (A,B) -- (B,D) -- (B,C)\\ 
-b) (B,D) -- (A,D) -- (D,C)\\ +b) (B,D) -- (A,B) -- (B,C)\\ 
 c) NEIN c) NEIN
  
Zeile 72: Zeile 74:
         int pos = hk; //current position during exploration         int pos = hk; //current position during exploration
         do { //b)         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];                     K kold = map[pos][i];
                     map[pos][i] = k;                     map[pos][i] = k;
                     return kold;                     return kold;
                 }                 }
-                pos += c; 
-                pos %= map.length; 
             }             }
 +            pos = (pos + c) % s;
         } while (pos != hk);         } while (pos != hk);
                  
Zeile 110: Zeile 108:
 long bDP(int n, int m) { long bDP(int n, int m) {
     long[][] mem = new long[n + 1][m + 1];     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;                 mem[i][j] = 0;
-            } else if(n == m) {+            } else if(i == j) {
                 mem[i][j] = 1;                 mem[i][j] = 1;
-            } else { 
-                mem[i][j] = (3*(n-1)*b(n-1,m) + m*b(n-1,m-1))/n; 
             }             }
         }         }
Zeile 144: Zeile 142:
 <code> <code>
 axs axs
-    bin2nat(empty) = null +    bin2nat(empty) = zero 
-    bin2nat(push(s,n)) = ????+    bin2nat(push(S,N)) = add(N,mult(bin2nat(S),succ(succ(zero)))) // (N + 2*bin2nat(S)) 
 </code> </code>
 ==== Aufgabe 7 - Doppelverkettung (29) ==== ==== Aufgabe 7 - Doppelverkettung (29) ====
Zeile 182: Zeile 181:
                  
         return true;         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));
     }     }
          
Zeile 190: Zeile 220:
         } else {         } else {
             while(c != this) {             while(c != this) {
-                c = c.a;+                // Zuerst null-Check, c kann hier bereits null sein!
                 if(c == null) {                 if(c == null) {
                     return false;                     return false;
                 }                 }
 +                c = c.a;
             }             }
             c = this.z;             c = this.z;
             while(c != this) {             while(c != this) {
-                c = c.z; 
                 if(c == null) {                 if(c == null) {
                     return false;                     return false;
                 }                 }
 +                c = c.z;
             }             }
             return true;             return true;
Zeile 216: Zeile 247:
         //list is empty         //list is empty
         if(h == null) {         if(h == null) {
-            throw NoSuchElementException("[Error] List is empty!");+            throw new NoSuchElementException("[Error] List is empty!");
         }         }
         //list has only on single node - just empty the deque         //list has only on single node - just empty the deque
-        else if(h.a == null && h.z == null) {+        else if(h.a == null || h.a == h) {
             h = null;             h = null;
         }         }
         //user requested head - reconfigure internal head pointer         //user requested head - reconfigure internal head pointer
         else if(high) {         else if(high) {
-            h = h.a;+            h = h.z;
         }         }
         //user requested node that preceeds head - retarget r         //user requested node that preceeds head - retarget r
Zeile 250: Zeile 281:
         //insert/link n before c, if c exists         //insert/link n before c, if c exists
         if(c != null) {         if(c != null) {
-            n.z = c.z; +            c.a.z = n; 
-            n.a = c; +            n.a = c.a; 
-            c.z.a = n; +            n.z = c; 
-            c.z = n;+            c.a = n;
         }         }
     }     }
 } }
 </code> </code>