• 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

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

1. Beispiel: c: Test
2. a: Test
3. b: 42
4. c: 0
5. f: 0
6. Compiler-Fehler: Ambiguous Method
7. e: 23

a) Adjazenzmatrix

b)

c)

d) Halde - Begründung???

e)

• genau n
• genau n - 1
• genau 1
• O (|V| * log |V| + |E|)

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)|-|

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];

}