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:loesungss09 [25.03.2015 15:08] – bor1pruefungen:bachelor:aud:loesungss09 [15.05.2019 06:35] (aktuell) – SpeedyGonzalez
Zeile 117: Zeile 117:
 **c)** **c)**
  
-FIXME - Aufrufgraph+<code> 
 +bar(3)  
 +    ---> foo(3) 
 +              --->foo(2) 
 +                       --->foo(1) 
 +                       --->bar(0)  
 +              --->bar(1) 
 +    ---> bar(2) 
 +              --->foo(2) 
 +                       --->foo(1) 
 +                       --->bar(0)  
 +              --->bar(1) 
 +</code>
  
 **d)** **d)**
Zeile 153: Zeile 165:
  
   * Laufzeit: O(n), da man, um von bar(n) auf bar(n + 1) zu kommen, lediglich die Aufrufe foo(n) und bar(n) zu berechnen sind und alle anderen Ergebnisse bereits in der Tabelle stehen   * Laufzeit: O(n), da man, um von bar(n) auf bar(n + 1) zu kommen, lediglich die Aufrufe foo(n) und bar(n) zu berechnen sind und alle anderen Ergebnisse bereits in der Tabelle stehen
-  * Speicherbedarf: O(n), da man zwei Arrays der Größe (n + 1) benötigt (je eins für DP von foo und von bar)+  * Speicherbedarf: O(n), da man zwei Arrays der Größe (n + 1) beneq05oqabötigt (je eins für DP von foo und von bar)
  
 ==== Aufgabe 4 - Sortieren ==== ==== Aufgabe 4 - Sortieren ====
Zeile 171: Zeile 183:
 Anmerkung:\\ Anmerkung:\\
 Mit Angabe von "from" und "to" wird eine Teilsortierung moeglich. Mit Angabe von "from" und "to" wird eine Teilsortierung moeglich.
 +
 +Beispiel-Code zur Aufgabe: https://fsi.cs.fau.de/forum/post/160481;nocount
  
 <code java> <code java>
 public static void sortPos(int array[], int from, int to, int pos) { public static void sortPos(int array[], int from, int to, int pos) {
- LinkedList<Integer>[] buckets = new LinkedList[10];+ LinkedList<Integer>[] buckets = new LinkedList[10]; //Für jede Ziifer 0-9 einen Bucket erstellen
   
- for (int i = 0; i < buckets.length; i++) {+ for (int i = 0; i < buckets.length; i++) { //In jedem Bucket eine LinkedList erstellen
  buckets[i] = new LinkedList();  buckets[i] = new LinkedList();
  }  }
   
- for (int i = from; i < to; i++) {+ for (int i = from; i < to; i++) { //Buckets mit PLZs befüllen und sortieren
  int b = getDigit(array[i], pos);  int b = getDigit(array[i], pos);
  buckets[b].addLast(array[i]);  buckets[b].addLast(array[i]);
  }  }
   
- LinkedList<Integer> master = new LinkedList<>();+ LinkedList<Integer> master = new LinkedList<>(); //Master Liste erstellen in die Werte sortiert kopiert werden können
   
- for (int i = 0; i < buckets.length; i++) {+ for (int i = 0; i < buckets.length; i++) { //In Master Liste einen Bucket nach dem anderen kopieren
  master.addAll(buckets[i]);  master.addAll(buckets[i]);
  }  }
   
- for(int i = from; i < to; i++) {+ for(int i = from; i < to; i++) { //In ursprünglichen Array die Elemente aus Master Liste kopieren.
  array[i] = master.removeFirst();  array[i] = master.removeFirst();
  }  }
Zeile 197: Zeile 211:
  
 public static void radixSort(int[] array) { public static void radixSort(int[] array) {
- for (int i = 0; i < 5; i++) {+ for (int i = 5; i >=1; i--) {
  sortPos(array, 0, array.length, i);  sortPos(array, 0, array.length, i);
  }  }
Zeile 253: Zeile 267:
  
 **c)** **c)**
 +
 +Primärkollision, wenn Bucket, wo es eigentlich eingefügt werden sollte, ein D hat.
 +Sekundärkollision, wenn Bucket, wo es eigentlich eingefügt werden sollte, ein P oder S hat.
 +
 ^Bucket ^ Key ^ P, S oder D ^ ^Bucket ^ Key ^ P, S oder D ^
 ^ 0 | 12 | S | ^ 0 | 12 | S |
 ^ 1 | 33 | D | ^ 1 | 33 | D |
 ^ 2 | 66 | S | ^ 2 | 66 | S |
-^ 3 | 28 | S |+^ 3 | 28 | P |
 ^ 4 | 14 | D | ^ 4 | 14 | D |
 ^ 5 | 6   | S | ^ 5 | 6   | S |