Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forum

Forum

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)

  1. Beispiel: c: Test
  2. a: Test
  3. b: 42
  4. c: 0
  5. f: 0
  6. Compiler-Fehler: Ambiguous Method
  7. 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];

}