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 [19.02.2013 14:09] – Dawodopruefungen:bachelor:aud:loesungss09 [15.05.2019 06:34] – 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 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 232: Zeile 245:
 **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 263:
 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 |