Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:bachelor:aud:loesungss09 [25.03.2015 15:08] – bor1 | pruefungen:bachelor:aud:loesungss09 [15.05.2019 06:35] (aktuell) – SpeedyGonzalez | ||
---|---|---|---|
Zeile 117: | Zeile 117: | ||
**c)** | **c)** | ||
- | FIXME - Aufrufgraph | + | < |
+ | bar(3) | ||
+ | | ||
+ | ---> | ||
+ | | ||
+ | | ||
+ | ---> | ||
+ | ---> bar(2) | ||
+ | ---> | ||
+ | | ||
+ | | ||
+ | ---> | ||
+ | </ | ||
**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: | + | * Speicherbedarf: |
==== Aufgabe 4 - Sortieren ==== | ==== Aufgabe 4 - Sortieren ==== | ||
Zeile 171: | Zeile 183: | ||
Anmerkung: | Anmerkung: | ||
Mit Angabe von " | Mit Angabe von " | ||
+ | |||
+ | Beispiel-Code zur Aufgabe: https:// | ||
<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< | + | LinkedList< |
- | for (int i = 0; i < buckets.length; | + | for (int i = 0; i < buckets.length; |
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], | int b = getDigit(array[i], | ||
buckets[b].addLast(array[i]); | buckets[b].addLast(array[i]); | ||
} | } | ||
- | LinkedList< | + | LinkedList< |
- | for (int i = 0; i < buckets.length; | + | for (int i = 0; i < buckets.length; |
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, | sortPos(array, | ||
} | } | ||
Zeile 253: | Zeile 267: | ||
**c)** | **c)** | ||
+ | |||
+ | Primärkollision, | ||
+ | Sekundärkollision, | ||
+ | |||
^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 | |