Zurueck zur Startseite

Probeklausur - MIT LOESUNGEN

Fortgeschrittene Algorithmen und Programmierung

Vorlesungen 1-12

Wintersemester 2025/26 | HTW Berlin

Prof. Dr. Alexandra Mikityuk

Pruefungsinformationen

Hinweis: Dies ist eine Uebungsklausur MIT Loesungen. Versuchen Sie zuerst, die Aufgaben selbst zu loesen, bevor Sie die Loesungen anschauen!
Teil 1: Strukturen und Zeiger (25 Punkte)
Aufgabe 1.1: Struktur-Definition 10 Punkte

Definieren Sie eine Struktur Student mit folgenden Feldern:

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

Wichtig: Vergessen Sie nicht den Basisfall!
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]); } }

Antwort: O(____)

Erklaerung:

b) (4 Punkte)

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

Antwort: O(____)

Erklaerung:

Gesamtpunktzahl: _____ / 100 Punkte
Viel Erfolg!
Diese Probeklausur deckt den Stoff der Vorlesungen 1-12 ab: Strukturen, Zeiger, Rekursion, Sortieralgorithmen (Selection Sort, Insertion Sort, Bubble Sort), Binaere Suche und Komplexitaetsanalyse (O-Notation).