=== Forum ===
  * [[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 ====


=== Aufgabe 1 - Wissensfragen (15P) ===
**a)** falsch

**b)** [kann mich nicht erinnern ob das Teil des Stoffes war]

**c)** falsch

**d)** [nicht in Vorlesung durchgenommen]

**e)** richtig

**f)** [nicht in Vorlesung durchgenommen]

**g)** 1. und 3. Antwort richtig

**h)** falsch

**i)**

falsch

richtig

falsch - eher richtig, siehe [[https://fsi.informatik.uni-erlangen.de/forum/thread/8853-Klausur-17-9-07]]

falsch

**j)** falsch

**k)** falsch

=== Aufgabe 2 - Java (12P) ===

  - Beispiel: c: Test
  - a: Test
  - b: 42
  - c: 0
  - f: 0
  - Compiler-Fehler: Ambiguous Method
  - 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];
	
	}