Probeklausur - Fortgeschrittene Algorithmen und Programmierung (VL 1-13)

Teil 1: Strukturen und Zeiger (25 Punkte)

Aufgabe 1.1: Struktur-Definition 10 Punkte

Definieren Sie eine Struktur Student mit folgenden Feldern:

Matrikelnummer (int)
Name (char array mit 50 Zeichen)
Note (double)

Schreiben Sie dann eine Funktion void printStudent(struct Student s), die einen Studenten formatiert ausgibt.

Aufgabe 1.2: Strukturen und Zeiger 15 Punkte

Schreiben Sie eine Funktion void verbessereNote(struct Student* s, double bonus), die die Note eines Studenten um einen Bonus verbessert (aber maximal auf 1.0).

Hinweis: Achten Sie auf den Pfeil-Operator (->) fuer Zeiger auf Strukturen!

Zeigen Sie auch ein Beispiel fuer den Aufruf dieser Funktion.

Teil 2: Rekursion (25 Punkte)

Aufgabe 2.1: Fakultaet rekursiv 8 Punkte

Implementieren Sie die Funktion int fakultaet(int n) rekursiv.

Hinweis: n! = n * (n-1)! und 0! = 1

Aufgabe 2.2: Fibonacci rekursiv 8 Punkte

Implementieren Sie die Fibonacci-Folge rekursiv: fib(n) = fib(n-1) + fib(n-2)

Mit fib(0) = 0 und fib(1) = 1

Aufgabe 2.3: Array-Summe rekursiv 9 Punkte

Schreiben Sie eine rekursive Funktion int summeArray(int arr[], int n), die die Summe aller Elemente berechnet.

Beispiel: summeArray({1,2,3,4,5}, 5) = 15

Teil 3: Sortieralgorithmen (30 Punkte)

Aufgabe 3.1: Theoriefragen zu Sortieralgorithmen 10 Punkte

a) Was bedeutet "stabil" bei einem Sortieralgorithmus? Geben Sie ein Beispiel. (4 Punkte)

b) Was bedeutet "in-place"? (3 Punkte)

c) Welcher der drei Algorithmen (Selection Sort, Insertion Sort, Bubble Sort) ist stabil? (3 Punkte)

Aufgabe 3.2: Insertion Sort 10 Punkte

Implementieren Sie Insertion Sort fuer ein Integer-Array.

Prinzip: Fuege jedes Element an die richtige Position im bereits sortierten Teil ein.

Aufgabe 3.3: Bubble Sort mit Optimierung 10 Punkte

Implementieren Sie Bubble Sort mit dem "swapped"-Flag zur Optimierung.

Erklaeren Sie kurz, warum diese Optimierung wichtig ist.

Teil 4: Binaere Suche & Komplexitaet (20 Punkte)

Aufgabe 4.1: Binaere Suche implementieren 12 Punkte

Implementieren Sie die binaere Suche iterativ: int binaereSuche(int arr[], int n, int gesucht)

Voraussetzung: Das Array ist bereits sortiert!

Wichtig: Verwenden Sie mitte = links + (rechts - links) / 2 um Overflow zu vermeiden!

Aufgabe 4.2: Komplexitaetsanalyse 8 Punkte

Bestimmen Sie die Zeitkomplexitaet (Big-O) folgender Code-Ausschnitte:

a) (4 Punkte)

for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { printf("%d ", arr[i][j]); } }

b) (4 Punkte)

int k = n; while (k > 1) { printf("%d ", k); k = k / 2; }

Probeklausur - MIT LOESUNGEN

Fortgeschrittene Algorithmen und Programmierung

Vorlesungen 1-13

Pruefungsinformationen