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
pruefungen:bachelor:aud:loesungws14 [08.07.2015 18:27] – Fehlende Aufgabe Nummer 7 hinzugefügt, 6c fehlt immer noch teilweise Phreek90pruefungen:bachelor:aud:loesungws14 [08.04.2022 06:49] (aktuell) – Ich bin dumm, Änderung rückgängig 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) ====
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>