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:loesungws09 [20.03.2018 18:11] – Evrenpruefungen:bachelor:aud:loesungws09 [20.06.2020 14:09] (aktuell) – BierBaron69
Zeile 10: Zeile 10:
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8861-Klausur-25-02-2010-Aufgabe-7b-Dijkstra]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8861-Klausur-25-02-2010-Aufgabe-7b-Dijkstra]]
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/9468-Klausur-25-02-2010]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/9468-Klausur-25-02-2010]]
 +  * [[https://fsi.cs.fau.de/forum/thread/17186-Klausur-Ws2009-Frage-zu-ADTs-A8c]]
  
 ===== Lösungsversuch ===== ===== Lösungsversuch =====
Zeile 44: Zeile 45:
  
  
-**i)** Falsch; nur bei gerader Anzahl an Elementen.+**i)** Falsch; nur bei gerader Anzahl an Elementen. Naja es hängt in v.a. auch von der Wahl des Pivot-Elementes ab.
  
 **j)** O(1) **j)** O(1)
Zeile 79: Zeile 80:
 private static long[][] b = new long[MAX][MAX]; private static long[][] b = new long[MAX][MAX];
 // Vorinitialisierung des Felds b[][] mit -1 // Vorinitialisierung des Felds b[][] mit -1
 +//Klausurfragestellung nicht ganz eindeutig, gefragt ist hier richtigerweise dynamische Programmierung mittels Memoization
  
-private static long binomFast(int n, int k) {+private static long binom(int n, int k) { 
  if(k > n)  if(k > n)
  return 0;  return 0;
Zeile 187: Zeile 189:
   * **O(n log n)**   * **O(n log n)**
 Sollte es nicht O(n) sein? In den VL-Folien steht, dass das Aufbauen einer Halde aus einem Array der Länge n nur O(n) ist. (Beweis wurde ausgelassen, aber intuitiv deswegen, weil die obere Hälfte des Arrays keine Kinder in der Halde hat => ein großer Teil fällt schon mal weg!) Sollte es nicht O(n) sein? In den VL-Folien steht, dass das Aufbauen einer Halde aus einem Array der Länge n nur O(n) ist. (Beweis wurde ausgelassen, aber intuitiv deswegen, weil die obere Hälfte des Arrays keine Kinder in der Halde hat => ein großer Teil fällt schon mal weg!)
 +
 +Ja O(n), in der Klausur wurde nach der effizientesten Möglichkeit gesucht. Diese baut den Heap in O(n) auf, wie hier unter 4.2.4 beschrieben: http://linux-related.de/index.html?/coding/sort/sort_heap.htm
  
 **c)** **c)**
Zeile 201: Zeile 205:
  }  }
 } }
 +</code>
 +
 +Das ginge meines Erachtens (bei anderer Angabe noch leichter), oder??:
 +
 +<code java>
 +
 +public static void haldenSortierung(int[] feld){
 +    haldenEigenschaftHerstellen(feld);
 +        
 +    for(int i = feld.length - 1; i > 0; i--){
 +        tausche(feld, 0, i);
 +        versickern(feld, 0, i - 1);
 +    }
 +}   
 </code> </code>
  
Zeile 318: Zeile 336:
 <code> <code>
 wp("a = a*3 - 1; b = 80 - a; b--;", b > 47) = wp("a = a*3 - 1; b = 80 - a; b--;", b > 47) =
-wp("a = a*3 - 1; b = 80 - a; b = b -1;", b > 47) =+wp("a = a*3 - 1; b = 80 - a; b = b - 1;", b > 47) =
 wp("a = a*3 - 1; b = 80 - a;", b - 1 > 47) = wp("a = a*3 - 1; b = 80 - a;", b - 1 > 47) =
 wp("a = a*3 - 1;", 80 - a - 1 > 47) = wp("a = a*3 - 1;", 80 - a - 1 > 47) =