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

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
Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws15 [03.04.2017 14:23] – Danplanpruefungen:bachelor:aud:loesungws15 [07.04.2019 13:22] – Nico Hambauer
Zeile 9: Zeile 9:
 ** b) ** 2 und 3 ** b) ** 2 und 3
  
-** c) ** 2    +** c) ** 2   || Ziemlich sicher, dass auch 1 richtig ist. 
-  *  "Die Länge des Feldes ist keine 2er-Potenz.": unsicher, ob das hier eine Rolle spielt+  * zu 1) (2. Meinung: "(stimmt hier nicht auch 1?)") => wenn man bei der linearen Suche ("< oder "=") überprüft, müsste man sicherstellen, dass die zu durchsuchende Zahlenreihe immer aufsteigend sortiert ist. Mit einer allgemeinen Methode zur linearen Suche würden die Suchen mit Sicherheit für alle anderen Fälle daneben gehen.  
 +  * zu 2) Lineare Suche überprüft im intervall [0:n] ob das i-te-Element == gesuchte Element ist, wenn das gesuchte Element das erste Element ist, dann ist man sofort fertig. Die binäre Suche braucht dazu mindestends noch ein schritt.  
 +  * zu 3) unsicher, ob das hier eine Rolle spielt ( 2.Meinung: "Denke ich nicht") 
 +  * zu 4) scheidet aus, weil 2 richtig ist
  
 ** d) ** 3 ** d) ** 3
Zeile 20: Zeile 23:
   * "löst das Rucksackproblem für n Elemente mit O(n^2) zusätzlichem Speicher.": Unsicher, ob man mit dem Algorithmus das Problem lösen kann oder wie die Lösung aussieht.    * "löst das Rucksackproblem für n Elemente mit O(n^2) zusätzlichem Speicher.": Unsicher, ob man mit dem Algorithmus das Problem lösen kann oder wie die Lösung aussieht. 
  
-** g) ** 2+** g) ** 2  (Meiner Meinung nach: 3 und 4 sind richtig!)
   * unsicher   * unsicher
 +  * Ich denke 4 müsste stimmen
 +  * Bei 2 bin ich mir auch unsicher, da das eigentlich die Definition des Theta-Kalküls ist (auch ein Landau-Symbol), in den Folien aber steht, dass man mit dem O-Kalkül meistens das meint.
  
 ==== Aufgabe 2 Streuspeicherung ==== ==== Aufgabe 2 Streuspeicherung ====
Zeile 39: Zeile 44:
   * C 3 (P)-> 4   * C 3 (P)-> 4
   * D 3 (P)-> 4 (S)-> 0   * D 3 (P)-> 4 (S)-> 0
-  * E 0 (P)-> 1 (S)-> 4 (S)-> 2+  * E 0 (S)-> 1 (P)-> 4 (S)-> 2
  
 ==== Aufgabe 3 Binäre Suche ==== ==== Aufgabe 3 Binäre Suche ====
Zeile 103: Zeile 108:
 <code java> <code java>
  
- void sort(String[] a) { +void sortierenDurchEinfuegen(String[] a) { 
- String temp; + String tmp; 
-  +  
- for (int n = 1; n < a.length; n++) {+ for (int n = 1; n < a.length; n++) {
   
- temp = a[n]; // entnommenes Element merken+ tmp = a[n]; // entnommenes Element merken
   
-                        int i = n - 1;+ int i = n - 1;
   
- while (i >= 0 && temp.compareTo(a[i]) < 0) { + while (i >= 0 && tmp.compareTo(a[i]) < 0) { 
- a[i + 1] = a[i]; + a[i + 1] = a[i]; 
- i--; + i--;
- } +
- +
- a[i + 1] = temp; // entnommenes Element +
- // einsetzen+
  }  }
 +
 + a[i + 1] = tmp; // entnommenes Element
 + // einsetzen
  }  }
 +}
  
  
Zeile 139: Zeile 144:
         long an = a(n-1);         long an = a(n-1);
         for(int i = 1; i < n; i++){         for(int i = 1; i < n; i++){
-                  an+= a(i)*a(i-1);+                  an+= a(i)*a(n-i); 
         }         }
         return an;         return an;
Zeile 212: Zeile 217:
  sammle(am,k,verb, bk);  sammle(am,k,verb, bk);
  ergebnis.add(verb);  ergebnis.add(verb);
 +                                //einfacher waere hier statt den letzten drei zeilen folgendes:
 +                                //sammle(am,k,ergebnis.get(k), bk); //!!
  }  }
   
Zeile 223: Zeile 230:
  for (int j=0;j<am[i].length;j++){  for (int j=0;j<am[i].length;j++){
  if (am[i][j]){  if (am[i][j]){
- if (vs.contains(i) && vs.contains(j)){ + if (!(vs.contains(i) && vs.contains(j))){ 
- // ok +                                 am[i][j] = false; 
- } +                                                am[j][i] = false;
- else { +
- am[i][j] = false;+
  }  }
  }  }
Zeile 253: Zeile 258:
 } }
 </code> </code>
 +
 +==== Aufgabe 8 ADT ====
 +<note>TODO</note>
 +
 +** a) **  
 +    * collect(Node(g, n)) = add(collect(g), n)  
 +    * collect(Edge(g, a, b)) = add(add(collect(g), a), b)
 +
 +** b) **
 +   * path(Node(g, n), x, y) = path(g, x, y)
 +   * path(Edge(g, a, b), x, y) =  true      falls (path(g, x, a) ^ path(g, b, y)) v (path(g, y, a) ^ path(g, b, x))   ;  path(g, x, y) sonst
 +
 +** c) **  
 +    * isRoot(Edge(g, a, b), x) = isRoot(g,x)    falls x!=b
 +       false sonst
 +