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 [15.07.2015 13:37] – tomabrafixpruefungen: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 40: Zeile 42:
 </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 219: Zeile 250:
         }         }
         //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;
         }         }