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 [29.11.2015 01:42] – tomabrafixpruefungen: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 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) ====
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;
Zeile 82: Zeile 81:
                 }                 }
             }             }
-            pos += c; +            pos = (pos + c) % s;
-            pos %= map.length;+
         } while (pos != hk);         } while (pos != hk);
                  
Zeile 144: Zeile 142:
 <code> <code>
 axs axs
-    bin2nat(empty) = null +    bin2nat(empty) = zero 
-    bin2nat(push(s,n)) = add(n,mul(bin2nat(s),succ(succ(zero)))) ?+    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;
         }         }