Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forum   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

Link zu dieser Vergleichsansicht

Both sides previous revision Vorhergehende Überarbeitung
Nächste Überarbeitung
Vorhergehende Überarbeitung
pruefungen:bachelor:aud:loesungss07 [21.02.2012 17:52]
LaCucaracha
pruefungen:bachelor:aud:loesungss07 [04.03.2020 14:26] (aktuell)
kat04
Zeile 1: Zeile 1:
 === Forum === === Forum ===
-  * [[https://​fsi.informatik.uni-erlangen.de/​forum/​thread/​8853-Klausur-17-9-07]] +  * [[https://​fsi.informatik.uni-erlangen.de/​forum/​thread/​8853-Klausur-17-9-07]] ​A3,A1 
 +  * [[https://​fsi.informatik.uni-erlangen.de/​forum/​thread/​8883-17-09-2007-Aufgabe-5-ADT-Warteschlange]]
 ==== Lösungsversuch ==== ==== Lösungsversuch ====
  
Zeile 28: Zeile 28:
 richtig richtig
  
-falsch+falsch ​- eher richtig, siehe [[https://​fsi.informatik.uni-erlangen.de/​forum/​thread/​8853-Klausur-17-9-07]]
  
 falsch falsch
Zeile 45: Zeile 45:
   - Compiler-Fehler:​ Ambiguous Method   - Compiler-Fehler:​ Ambiguous Method
   - e: 23   - e: 23
 +
 +=== Aufgabe 3 - Spannbäume (20P) ===
 +
 +**a)** Adjazenzmatrix
 +
 +**b)** ​
 +
 +**c)** ​
 +
 +**d)** Halde - Begründung???​ FIXME
 +
 +**e)** ​
 +
 +  * genau n
 +  * genau n - 1
 +  * genau 1
 +  * O (|V| * log |V| + |E|)
 +
 +
 +=== Aufgabe 4 - Suchbaum und Streutabelle (15P) ===
 +
 +**a)** ​
 +
 +**b)** ​
 +
 +  * Bester Fall: 1
 +  * Schlechtester Fall: n - 1
 +
 +**c)** 6, 4, 8, 2, 5, 7, 1
 +
 +**d)** ​
 +  * Preorder
 +  * Inorder (produziert im binären Suchbaum sortierte Liste)
 +  * Postorder
 +
 +**e)** ​
 +
 +  3|7(3)|-|1|4|-|2|5|6(4)|-|
 +  ​
 + === Aufgabe 6 - QuickSort === 
 +
 +  public class QuickSort {
 +
 + public static void main(String[] args) {
 +
 + int[] array = { 20, 35, -15, 7, 55, 1, -22,​56,​-8,​100,​-202 };
 + System.out.println(quickSelect(array,​ 6));
 + quickSort(array);​
 +
 +
 +
 +
 + }
 +
 + // v e r t a u s c h t zwei Positionen e i n e r Reihung
 + static void swap(int a[], int i, int j) {
 + int t = a[i];
 + a[i] = a[j];
 + a[j] = t;
 + }
 +
 + // s o r t i e r t di e komplette Reihung
 + static void quickSort(int a[]) {
 + quickSortAuf(a,​ 0, a.length - 1);
 +
 + }
 +
 + // s o r t i e r t den Bereich von s t a r t b i s end ( i n k l u s i v e )
 + static void quickSortAuf(int a[], int start, int end) {
 +
 + if (start >= end) {
 + return;
 + }
 + int pivot = a[start];
 + int i = start;
 + int k = end;
 + while (i < k) {
 + while (i < k && a[i] < pivot)
 + i++;
 + while (i < k && a[k] > pivot)
 + k--;
 + if (i < k) {
 + swap(a, i, k);
 + }
 + }
 +
 + quickSortAuf(a,​ start, i);
 + quickSortAuf(a,​ i + 1, end);
 + }
 +
 + static int quickSelect(int a[], int r) {
 + int[] tmp = new int[a.length];​
 + System.arraycopy(a,​ 0, tmp, 0, a.length);
 + return quickSelect(tmp,​ 0, tmp.length - 1, r);
 +
 + }
 +
 + // sucht im Bereich von s t a r t b i s end ( i n k l u s i v e )
 + // nach dem rg r o e s s t e n Element
 + static int quickSelect(int a[], int start, int end, int r) {
 + System.out.println(Arrays.toString(a));​
 + if(r>​=start && r <= end && start <end) {
 + int pivot = a[start];
 + int i = start;
 + int k = end;
 + while (i < k) {
 + while (i < k && a[i] < pivot)
 + i++;
 + while (i < k && a[k] > pivot)
 + k--;
 + if (i < k) {
 + swap(a, i, k);
 + }
 + }
 + quickSelect(a,​ start, i,r);
 + quickSelect(a,​ i+1, end,r);
 + }
 + return a[r];
 +
 + }