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 [19.02.2013 14:09] – Dawodopruefungen:bachelor:aud:loesungss09 [15.05.2019 06:35] (aktuell) – SpeedyGonzalez
Zeile 27: Zeile 27:
 **h)** O(n²) **h)** O(n²)
  
-**i)** [Nicht mehr Stoff aktueller Semester?]+**i)** richtig, O(|v| + |E|)
  
  
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 170: Zeile 182:
  
 Anmerkung:\\ Anmerkung:\\
-Ich hab keine Ahnung, was bei sortPos mit "from" und "to" gemeint ist. Eventuell ist das auch einfach zur Verwirrung da.+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 = 0; i < array.length; 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 232: Zeile 246:
 **Kruskal:** O(e * log(e)) bei Implementierung mit Pfadkompression **Kruskal:** O(e * log(e)) bei Implementierung mit Pfadkompression
  
-==== Aufgabe 6 -Streutabellen ====+==== Aufgabe 6 - Streutabellen ====
 **a)** **a)**
  
Zeile 250: Zeile 264:
 Begründung: \\ Begründung: \\
 Die Multiplikation mit 2 macht aus jedem Schlüssel garantiert eine gerade Zahl, die anschließende Addition mit 3 garantiert eine ungerade Zahl. \\ Die Multiplikation mit 2 macht aus jedem Schlüssel garantiert eine gerade Zahl, die anschließende Addition mit 3 garantiert eine ungerade Zahl. \\
-Eine ungerade Zahl modulo eine ungerade Zahl ergibt wiederum eine ungerade Zahl.+Eine ungerade Zahl modulo eine gerade Zahl ergibt wiederum eine ungerade Zahl.
  
 **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 |