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:loesungws07 [15.02.2013 10:17] – Dawodopruefungen:bachelor:aud:loesungws07 [29.03.2016 15:02] (aktuell) – ADT korrigiert Marcel[Inf]
Zeile 1: Zeile 1:
-==forum==+===== Forendiskussionen =====
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7567-Frage-Klausur-21-Februar-2008]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7567-Frage-Klausur-21-Februar-2008]]
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7104-WP-kalkuel-21-02-2008]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7104-WP-kalkuel-21-02-2008]]
Zeile 10: Zeile 10:
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8877-Klausur-21-2-2008-A10-d-e]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8877-Klausur-21-2-2008-A10-d-e]]
  
-====Lösungsversuch====+===== Lösungsversuch =====
  
-===Aufgabe 1 - Binärsuche===+==== Aufgabe 1 - Binärsuche ====
 **a)** O(n) **a)** O(n)
  
Zeile 57: Zeile 57:
 **c)** O(log n) **c)** O(log n)
  
-===Aufgabe 2 - Graphen===+==== Aufgabe 2 - Graphen ====
 **a)** **a)**
   * **Ja**   * **Ja**
Zeile 97: Zeile 97:
 BD, BC, DG, BA, FI, GE, GI, FH BD, BC, DG, BA, FI, GE, GI, FH
  
-===Aufgabe 3 - Java===+==== Aufgabe 3 - Java ====
 **a)** **a)**
 Java Datei zum Ausprobieren: {{:pruefungen:bachelor:aud:test.java-ws07.txt|:pruefungen:bachelor:aud:test.java-ws07.txt}} Java Datei zum Ausprobieren: {{:pruefungen:bachelor:aud:test.java-ws07.txt|:pruefungen:bachelor:aud:test.java-ws07.txt}}
Zeile 126: Zeile 126:
  
  
-=== Aufgabe 4 - Arithmetische Ausdrücke - Grammatik ===+==== Aufgabe 4 - Arithmetische Ausdrücke - Grammatik ====
 (nicht mehr Stoff aktueller Semester) (nicht mehr Stoff aktueller Semester)
  
-===Aufgabe 5 - ADT===+==== Aufgabe 5 - ADT ====
 **a)** **a)**
 +Primärkonstruktoren:
   * number   * number
   * binop   * binop
 +
 +Sekundärkonstruktoren (war nicht gefragt):
   * left   * left
   * right   * right
   * commutate   * commutate
  
-//Hinweis:// Konstruktoren sind alle Operationen, die Datenobjekte des Typs erzeugen.+Projektionen: 
 +  * numops
  
 **b)** **b)**
Zeile 173: Zeile 177:
 </code> </code>
  
-=== Aufgabe 6 - Rucksackproblem ===+==== Aufgabe 6 - Rucksackproblem ====
 **a)** **a)**
 ^    ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^ 12 ^ ^    ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^ 12 ^
Zeile 191: Zeile 195:
   P(2, 1) -> k_2 = 3 gehört nicht rein -> P(1, 1)   P(2, 1) -> k_2 = 3 gehört nicht rein -> P(1, 1)
   P(1, 1) -> k_1 = 1 gehört rein -> Rucksack vollständig gefüllt   P(1, 1) -> k_1 = 1 gehört rein -> Rucksack vollständig gefüllt
- 
  
 **c)** **c)**
 <code java> <code java>
-for(int i = 1; i < n; i++) {            // Zeilen +for(int i = 1; i < n; i++) { // Zeilen 
-    for(int j = 0; j < m + 1; j++) {    // Spalten + for(int j = 0; j <= m; j++) { // Spalten 
-        if((tab[i][j] == OHNE || tab[i][j] == MIT) && i < n-1) { // Wenn in einer Zeile MIT oder OHNE steht +  
-            tab[i+1][j] = OHNE;         // so muss die Zelle daraunter den Wert OHNE haben. + // Fall P(n - 1, K): Gibt es in der Zelle direkt darüber eine Lösung, 
-            if(j + k[i+1] <= m) + // dann ist P(n, K) = P(n - 1, K) 
-                tab[i+1][j+k[i+1]] = MIT; + // Das aktuelle Elemente gehört somit nicht zur Lösung -> OHNE 
-        } + if(tab[i - 1][j] != UNMOEGLICH) { 
-    }+ tab[i][j] = OHNE; 
 + 
 + // Fall P(n - 1, K - k_n): Gibt es in der Zeile darüber, nach links versetzt 
 + // eine Lösung (Achtung: ArrayIndexOutOfBoundsException), dann ist 
 + // P(n, K) = P(n - 1, K) + k_n 
 + // Das aktuelle element gehört somit zur Lösung -> MIT 
 + } else if(elements[i] <= j && tab[i - 1][j - elements[i]] != UNMOEGLICH) { 
 + tab[i][j] = MIT; 
 + } 
 + }
 } }
 </code> </code>
 +
 +Vollständiges Programm: \\
 +{{:pruefungen:bachelor:aud:rucksack.java.txt|:pruefungen:bachelor:aud:rucksack.java.txt}}
  
 **d)** **d)**
-// unsicher! +  * **Ja** 
-  * nein +  * **Ja** 
-  * ja +  * **Ja**, durch sukzessives Ausprobieren für Kapazitäten < m 
-  * nein +  * **Nein**, das Verfahren verwendet eine Integer-DP-Tabelle bzw. greift auf Indizes basierend auf der Elementgröße zu
-  * ja+
  
-=== Aufgabe 7 - Binäre Bäume ===+==== Aufgabe 7 - Binäre Bäume ====
 **a)**  **a)** 
 Der Binärbaum muss eine totale Ordnung aufweisen:\\ Der Binärbaum muss eine totale Ordnung aufweisen:\\
Zeile 285: Zeile 299:
   * **Nein**, man muss eines Tiefensuche vewenden   * **Nein**, man muss eines Tiefensuche vewenden
  
-=== Aufgabe 8 - Sortieren ===+==== Aufgabe 8 - Sortieren ====
  
 **a)** **a)**
Zeile 425: Zeile 439:
  
  
-=== Aufgabe 9 - Aufwände, O-Kalkül ===+==== Aufgabe 9 - Aufwände, O-Kalkül ====
 **a)** **a)**
   * **O(log n)**   * **O(log n)**
-  * **O(k)**+  * **O(n)**, da k * n/2
   * **O(n²)**   * **O(n²)**
   * **O(n)**   * **O(n)**
Zeile 490: Zeile 504:
   (m = m) =    (m = m) = 
   (true)   (true)
-