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
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungss09 [29.07.2015 09:09] – vaiqueropruefungen:bachelor:aud:loesungss09 [15.05.2019 06:34] – 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 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 210:
  
 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 266:
  
 **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 |