# Wintersemester 2024/25 (2) Quelle: https://inf.zone/extras/altklausuren/ws-2425-2/ **Wintersemester 2024/25, zweiter Termin.** 9 ECTS: alle Aufgaben, 120 Punkte. 6 ECTS: nur A1 bis A6, 80 Punkte. **Altklausur** Die Aufgaben einer früheren E-Prüfung, ohne Lösungen. Geprüft wurde am Laptop: Wo hier ein leerer Kasten steht, war in der Prüfung ein Eingabefeld. Zu jeder Teilaufgabe gab es außerdem das Kästchen [„Weiß ich nicht“](https://inf.zone/extras/exam-hints/#weiß-ich-nicht-kästchen). Den Code, der in der Prüfung im Ordner `exam-files` lag, gibt es als [ws-2425-2.zip](https://inf.zone/download/extras/altklausuren/ws-2425-2.zip). Im Codespace laden und entpacken Sie ihn so: ```bash wget https://inf.zone/download/extras/altklausuren/ws-2425-2.zip unzip ws-2425-2.zip ``` Die Tests, die in der Prüfung mit `check50 checks/...` liefen, liegen nicht bei. ## A1: Grundlagen (22 Punkte) ### A1a (4 Punkte) Die C-Funktion `fopen` benötigt als Parameter neben dem Dateinamen einen **Mode String**, der angibt, welche Operationen auf einer Datei ausgeführt werden sollen. Geben Sie für die folgenden Szenarien an, welcher Mode String im Quelltext der Programme beim Aufruf von `fopen` verwendet werden muss, um die angegebene Aufgabe durchzuführen. Entscheiden Sie sich jeweils für genau einen der in der Vorlesung behandelten Mode Strings, also **r**, **w** oder **a**. *Hinweis:* Falls Ihnen die Parameter von `fopen` bzw. das Konzept des *Mode Strings* nicht mehr bekannt sind, können Sie die Details dazu im CS50-Manual nachlesen, das oben auf der Seite verlinkt ist. Alice möchte ihre Daten sichern. Ihr Backup-Programm öffnet eine neue Sicherungsdatei zum Schreiben. *[Antwortfeld]* Ein E-Mail-Programm öffnet eine Archivdatei, um weitere Nachrichten anzuhängen. *[Antwortfeld]* Ein Bildbetrachtungsprogramm öffnet eine Bilddatei, um diese auf dem Bildschirm anzuzeigen. *[Antwortfeld]* Ein Kommandozeileninterpreter (z.B. die CS50-Shell) öffnet eine Skriptdatei, um die darin enthaltenen Shellbefehle auszuführen. *[Antwortfeld]* ### A1b (3 Punkte) Analysieren Sie folgenden Pseudocode. Die Syntax und das Verhalten der Sprachkonstrukte sind an C angelehnt. Auf geschweifte Klammern wird verzichtet. Die Einrückungen drücken aus, welche Teile des Codes innerhalb von Schleifen und Bedingungen stehen. FOR und IF und alle Operatoren funktionieren wie in C. AND ist der boolesche UND-Operator (&& in C). Die Pseudocode-Funktion AUSGABE gibt die Werte der dahinterstehenden Variablen ohne Trennzeichen dazwischen, also direkt hintereinander innerhalb von einer Zeile aus, gefolgt von einen Zeilenumbruch. *Hinweis:* Es ist zur Beantwortung *nicht* nötig, das Programm in C-Code zu übersetzen und zu kompilieren. ```text x = 0 count = 0 FOR (a = '0'; (a <= '9') AND (x == 0); a++): FOR (b = '0'; (b <= '9') AND (x == 0); b++): FOR (c = '0'; (c <= '9') AND (x == 0); c++): IF a == c: AUSGABE a, b, c count++ IF count == 3: x = 1 ``` Geben Sie die Ausgabe in dieses Feld ein. *[Antwortfeld, mehrzeilig]* ### A1c (4 Punkte) Wir haben in der Vorlesung drei Kriterien betrachtet, nach denen Codequalität bewertet werden kann. Nennen Sie diese mit je einem Stichwort. Es ist nicht nötig, die Kriterien zu erklären. Geben Sie je ein Stichwort auf einer Zeile ein. *[Antwortfeld, mehrzeilig]* Nehmen Sie an, in Ihrer *main*-Funktion wird die Funktion `process()` aufgerufen. Sie haben an der Stelle in *main*, an der `process()` aufgerufen wird, in VS Code einen Breakpoint gesetzt und das Programm gestartet. Der Debugger hat das Programm an Ihrem Breakpoint angehalten. Wie heißt die Debugger-Funktion, mit der Sie den Debugger instruieren, die Ausführung fortzusetzen und bei der ersten Instruktion in `process()` wieder anzuhalten? Nennen Sie den Namen der gefragten Debugger-Funktion. *[Antwortfeld]* ### A1d (7 Punkte) Beantworten Sie folgende Fragen zur Kommandozeile. Die Befehle werden in der angegebenen Reihenfolge ausgeführt. Zu Beginn befinden Sie sich im Verzeichnis `/home/user`. Sie möchten in den Ordner `projects` wechseln, der sich im aktuellen Verzeichnis befindet. *[Antwortfeld]* Sie haben sich geirrt und möchten wieder in das vorherige Verzeichnis zurückwechseln. *[Antwortfeld]* Sie möchten dort einen Ordner `foo` anlegen. *[Antwortfeld]* Nehmen Sie an, dass Sie sich nun im Ordner `foo` befinden. Dort möchten Sie eine Datei namens "bar.c" über die Kommandozeile erstellen und direkt in VS Code öffnen (das Terminal läuft in der Ihnen bekannten CS50-Umgebung). *[Antwortfeld]* Sie haben Ihr Programm fertig gestellt und möchten es nun auf der Kommandozeile kompilieren. *[Antwortfeld]* Sie haben im Debugger einige Breakpoints gesetzt und wollen von der Kommandozeile aus den Debugger starten (das Terminal läuft in der Ihnen bekannten CS50-Umgebung). *[Antwortfeld]* Abschließend möchten Sie Ihr Programm `bar` auf Speicherlecks überprüfen. *[Antwortfeld]* ### A1e (4 Punkte) In der Vorlesung haben Sie verschiedene Stellenwertsysteme kennengelernt, wie das Binärsystem, das Hexadezimalsystem und das Dezimalsystem. Viele mesoamerikanische Kulturen, darunter auch die Maya, verwendeten das sogenannte *Vigesimalsystem*, ein Stellenwertsystem zur Basis 20. Um eine Stelle darzustellen, werden zwei verschiedene Zeichen verwendet: Runde Punkte (Wert: 1) und rechteckige Blöcke (Wert: 5). Der Wert an der jeweiligen Stelle entspricht der Summe der Werte seiner Zeichen. Bei der Notation einer Stelle werden immer so wenig Zeichen wie möglich verwendet. Es werden also nie mehr als vier Punkte pro Stelle notiert. Die einzelnen Stellen werden von unten nach oben geschrieben, d.h. die niedrigstwertige Stelle steht immer ganz unten. Die Zahlen **24** und **13** werden in diesem Stellenwertsystem beispielsweise folgendermaßen dargestellt, wobei die dünne horizontale Linie die zwei Stellen voneinander trennt. ![Die Zahl 24 im Vigesimalsystem: oben ein Punkt, unter der Trennlinie vier Punkte](https://inf.zone/extras/altklausuren/ws-2425-2/bild-1.png) ![Die Zahl 13 im Vigesimalsystem: über der Trennlinie nichts, darunter drei Punkte über zwei Blöcken](https://inf.zone/extras/altklausuren/ws-2425-2/bild-2.png) Schreiben Sie Zahlen im Vigesimalsystem auf. Verwenden sie dabei folgenden Notation: - Das Zeichen `-` (Bindestrich, links neben der rechten Shift-Taste) für einen **Block**. - Das Zeichen `.` (Punkt, ebenfalls neben der rechten Shift-Taste) für einen **Punkt**. - Die Ziffer `0`, wenn Sie an der entsprechenden Stelle weder einen Block noch einen Punkt notieren möchten. - Schreiben Sie jeden Block in eine eigene Zeile. Fassen Sie alle Punkte direkt hintereinander in einer eigenen Zeile zusammen. - Trennen Sie die einzelnen Stellen durch Leerzeilen. Die Zahl **24** würden Sie also folgendermaßen notieren: ```text . .... ``` Notieren Sie die Zahl 202 im Vigesimalsystem. *[Antwortfeld, mehrzeilig]* Notieren Sie die Zahl 42 im Vigesimalsystem. *[Antwortfeld, mehrzeilig]* ## A2: Grundlagen der C-Programmierung (17 Punkte) ### A2a (2 Punkte) Beantworten Sie folgende Fragen. Mit welcher Funktion können Sie in C die Länge eines Strings ermitteln? Es reicht, den Namen der Funktion anzugeben (ohne Klammern und ohne Parameter) *[Antwortfeld]* Mit welcher Funktion können Sie in C zwei Strings miteinander vergleichen? Es reicht, den Namen der Funktion anzugeben (ohne Klammern und ohne Parameter) *[Antwortfeld]* ### A2b (4 Punkte) Ein wichtiger Datentyp in C ist `int`. Beschreiben Sie, was bei einem sogenannten Integer-Overflow passiert und wodurch dieser ausgelöst wird. *[Antwortfeld, mehrzeilig]* Betrachten Sie folgenden Programmcode. ```c #include typedef struct foo { int value; char bar[5]; } foo; int main() { printf("Ein int benötigt %lu Bytes.\n", sizeof(int)); printf("Fünf chars benötigen %lu Bytes.\n", sizeof(char) * 5); printf("%lu + %lu sollte %lu sein.\n", sizeof(int), sizeof(char) * 5, sizeof(foo)); } ``` Nach dem Kompilieren und Ausführen wird die folgende Ausgabe erzeugt: ```text Ein int benötigt 4 Bytes. Fünf chars benötigen 5 Bytes. 4 + 5 sollte 12 sein. ``` Erklären Sie, wie es zu diesem Widerspruch kommt. *[Antwortfeld, mehrzeilig]* ### A2c (5 Punkte) Betrachten Sie das folgende C-Programm (Sie haben es bereits in der Vorlesung gesehen) und ermitteln Sie drei Fehler im Quellcode. Geben Sie jeweils die Zeile an, in der der Fehler auftritt (**Inhalt der Zeile**), und wie Sie den Fehler beheben würden (am besten mit der **erforderlichen Anpassung der Codezeile**, ersatzweise mit einer Erklärung). Achten Sie dabei darauf, dass der Code auch nach Ihren Änderungen noch das bewirkt, was intendiert war. *Empfehlung:* Nutzen Sie die Fehlermeldungen, die *make* ausgibt, wenn Sie versuchen, das Programm zu kompilieren. ```c #include #include int main() { int n = 5; int *z = NULL; int *array = malloc(5); for (int i = 0; i <= n; i++) { array[i] = i * 2; *z = array[i]; } free(array); printf("%d\n", *z); return 0; } ``` Geben Sie für jeden gefundenen Fehler den Inhalt der Zeile an, die geändert werden müsste und beschreiben Sie, wie Sie den Fehler beheben würden. *[Antwortfeld, mehrzeilig]* ### A2d (6 Punkte) Schreiben Sie ein Programm, das einen Integer auf der Konsole entgegennimmt und den doppelten Wert ausgibt. Sie können dazu die CS50-Bibliothek benutzen. Die Ausgabe des Programms soll zum Beispiel wie folgt aussehen: ```text Geben Sie einen Integer ein: 3 Der doppelte Wert von 3 ist 6. ``` Geben Sie hier den Inhalt Ihres C-Programms ein. *[Antwortfeld, mehrzeilig]* ## A3: Chiffre (12 Punkte) In dieser Aufgabe implementieren Sie ein Kommandozeilenprogramm in C, das einen Text verschlüsselt. Dieses Verfahren funktioniert so ähnlich wie die Ihnen bekannte Caesar-Chiffre. Der wichtigste Unterschied: Die Klartext-Zeichen werden *nicht* um einen *konstanten* Wert verschoben, sondern unterschiedlich weit. Wie weit ein Zeichen verschoben wird, ergibt sich aus einem Schlüsselwort, das genauso lang ist wie der Klartext. Das Verfahren lässt sich wie folgt veranschaulichen: ```text H A L L O 7 0 11 11 14 B I B E R 1 8 1 4 17 ------------------ I I M P F 8 8 12 15 5 ``` Das Programm arbeitet wie folgt: - Es ordnet dem Klartext und dem Schlüsselwort wie folgt buchstabenweise Zahlen zu: A = 0, B = 1, C = 2, ..., Z = 25. - Es addiert die Zahlen, die an der gleichen Position stehen. Im Beispiel etwa `7 + 1 = 8` und ermittelt den zugehörigen Chiffretext-Buchstaben (hier: `I`). - Um sicherzustellen, dass der Chiffretext aus Buchstaben besteht, wird der Modulo-Operator verwendet (`% 26`). Im Beispiel sieht man den Effekt beim letzten Zeichen: `(14 + 17) % 26 = 31 % 26 = 5`. *Tipp:* Für die Ausgabe ist folgende Konstruktion hilfreich: `'A' + 8 = 'I'` etc. Die Aufgabenstellung finden Sie im Verzeichnis **exam-files/chiffre**. Für diese Aufgabe steht Ihnen *check50* zur Verfügung. Um *check50* zu verwenden, führen Sie folgenden Befehl in dem Verzeichnis aus, in dem sich die Datei *chiffre.c* befindet: **check50 checks/chiffre** Zuvor sollten Sie Ihr Programm kompilieren. ### A3a (7 Punkte) Prüfen Sie zunächst die Anzahl der Argumente sowie deren Inhalt. Wenn weniger oder mehr als 2 Argumente übergeben werden, dann soll das Programm mit dem Rückgabewert 2 terminieren und `Usage: ./chiffre <key>\n` ausgeben. Prüfen Sie anschließend, ob beide Argumente ausschließlich aus Großbuchstaben bestehen. Sollte dies nicht der Fall sein, geben Sie den String `Both arguments need to be uppercase strings!\n` aus und terminieren das Programm wieder mit dem Rückgabewert 2. Verwenden Sie für Ihre Implementierung die Funktion `is_uppercase_string(string arg)`. Prüfen Sie zuletzt, ob beide übergebene Strings gleich lang sind. Implementieren Sie dazu die Funktion `same_length(string arg_1, string arg_2)`. Wenn dies nicht der Fall ist, geben Sie den String `Both arguments need to be uppercase strings and of the same length!\n` aus und beenden das Programm mit dem Rückgabewert 2. Kopieren Sie den gesamten Inhalt von **chiffre.c** in dieses Feld. *[Antwortfeld, mehrzeilig]* ### A3b (5 Punkte) Implementieren Sie nun die Verschlüsselung für die Chiffre. Dazu implementieren Sie die Funktion `encrypt(char a, char b)`. Wenden Sie dann die Funktion `encrypt()` Zeichen für Zeichen auf den Klartext und das Schlüsselwort an. Das Ergebnis speichern Sie im String `result` und geben es auf der Konsole aus. Kopieren Sie den gesamten Inhalt von **chiffre.c** in dieses Feld. *[Antwortfeld, mehrzeilig]* ## A4: Datenrettung (10 Punkte) Dominik hat versehentlich wichtige Daten gelöscht. Glücklicherweise hat er den Inhalt des Datenträgers gesichert, indem er eine vollständige Kopie des Dateisystems ("Image") erstellt hat. Ihre Aufgabe ist es, aus diesem Image zwei Dateien wiederherzustellen. **Bearbeitungshinweis:** Das Folgende beschreibt das verwendete FAT16-Dateisystem. **Konzentrieren Sie sich auf die für die Dateiwiederherstellung relevanten Teile.** Schauen Sie sich zuerst die konkreten Aufgaben und den Code in `fat1.c` und `fat2.c` an. Das Image nutzt FAT16, aufgebaut aus: Boot Sector, File Allocation Tables (FATs), Root Directory, Data Area. ![FAT16 Struktur](https://inf.zone/extras/altklausuren/ws-2425-2/bild-3.png) - **Boot Sector:** Enthält Basisparameter des Dateisystems, wie Sektorgröße, Clustergröße (in Sektoren) und Startpositionen der anderen Bereiche. Diese Informationen sind oft zum Berechnen von Offsets nötig. - **Data Area:** Hier liegen die eigentlichen Datei-Inhalte, aufgeteilt in nummerierte Blöcke fester Größe, genannt **Cluster**. Ein Cluster ist die kleinste Einheit für die Dateispeicherung und besteht aus einem oder mehreren Sektoren (der kleinsten Einheit, die die Hardware lesen/schreiben kann). - **Root Directory:** Enthält Einträge für Dateien und Verzeichnisse im Stammverzeichnis. Für die Wiederherstellung sind entscheidend: - Der **Dateiname** und Erweiterung. - Die **Nummer des ersten Clusters**, in dem der Dateiinhalt beginnt. - Die **exakte Dateigröße in Bytes** (wichtig, um das Ende der Datei im letzten Cluster zu bestimmen). - **File Allocation Table (FAT):** Das Kernstück, das die Cluster einer Datei miteinander verkettet. - Für jeden Cluster in der Data Area gibt es einen Eintrag in der FAT (bei FAT16: 16 Bit pro Eintrag). - **Funktionsweise:** Der Index des FAT-Eintrags entspricht der Cluster-Nummer, auf den sich der FAT-Eintrag bezieht. Der *Wert* in einem FAT-Eintrag enthält je nach Fall folgende Daten: - **Nächster Cluster:** Eine Cluster-Nummer (z.B. Wert 12 im Eintrag für Cluster 5) verweist auf den nächsten Datenblock (Cluster 12). - **Letzter Cluster (EOC - End of Chain):** Ein spezieller Wert (typisch: `0xFFF8` - `0xFFFF`) markiert das Ende der Dateikette. - **Freier Cluster:** Der Wert `0x0000` bedeutet, der Cluster ist ungenutzt. **Anders als bei klassischen verketteten Listen in der Programmierung** (wo ein Element Daten und einen expliziten Pointer auf das nächste Element enthält), funktioniert die FAT durch *implizite* Referenzierung: - Der Index im FAT-Array ist gleichzeitig die Nummer des Clusters - Der Wert an dieser Stelle in der FAT ist die Nummer des nächsten Clusters in der Liste - Die Daten selbst sind nicht Teil der Liste, sondern liegen getrennt in den Clustern der Data Area **Beispiel zum Nachverfolgen einer Datei ("Urlaub.jpg", 9500 Bytes):** 1. **Root Directory:** Liefert Startcluster = **3**, Größe = **9500 Bytes**. 2. **FAT\[3\]:** Enthält den Wert **7**. Nächster Cluster ist 7. 3. **FAT\[7\]:** Enthält den Wert **11**. Nächster Cluster ist 11. 4. **FAT\[11\]:** Enthält **0xFFFF** (end of chain). Cluster 11 ist der letzte. 5. **Ergebnis:** Die Datei besteht aus den Clustern 3, 7, 11 (in dieser Reihenfolge). 6. **Lesen der Daten:** Angenommen, Clustergröße = 4096 Bytes (4 KB): **Normalerweise** gibt es zwei identische Kopien der FAT (FAT1 und FAT2). Die zweite FAT dient als Backup, falls die erste beschädigt wird. **Zusammenfassend für die Wiederherstellung:** Das **Root Directory** liefert den Startcluster und die Gesamtgröße einer Datei. Die **FAT** zeigt, wie die nachfolgenden Cluster der Datei verkettet sind, bis zum End-of-Chain-Marker. Die eigentlichen Daten befinden sich in den entsprechenden **Clustern** der **Data Area**. **Aufgaben** Um diese Aufgabe zu bearbeiten, müssen Sie die Dateien im Verzeichnis **exam-files/fat** bearbeiten. Das folgende Bild zeigt beispielhaft wie die Situation im Image aussehen könnte. ![Beispiel: In der FAT verweist Cluster 2 auf 3, 3 auf 4, 4 ist das Ende (EOC), das ist BOOK.PDF. Ebenso 5 auf 6, 6 auf 7, 7 ist das Ende, das ist DUCK.JPG. Darunter die Cluster der Data Area, unten das Root Directory mit BOOK.PDF ab Cluster 2 und DUCK.JPG ab Cluster 5](https://inf.zone/extras/altklausuren/ws-2425-2/bild-4.png) ### A4a (4 Punkte) Ihre erste Aufgabe ist es, einige Metadaten aus dem Boot Sector zu extrahieren: - OEM Identifier: Das Betriebssystem, unter dem der Datenträger formatiert wurde. - Reserved Sectors: Die Anzahl der für das Dateisystem reservierten Sektoren, die nicht frei verwendet werden können. - Number of FATs: Die Anzahl der FATs. - Bytes per Sector: Die Anzahl der Bytes pro Sektor. - Sectors per Cluster: Die Anzahl der Sektoren pro Cluster. Vervollständigen Sie dazu das Programm `fat1.c`. Kopieren Sie den gesamten Inhalt von **fat1.c** in dieses Feld. *[Antwortfeld, mehrzeilig]* ### A4b (6 Punkte) Die Datei `fat2.c` enthält bereits Code, der die Einträge aus dem Root Directory liest und über die einzelnen Cluster einer Datei iteriert. Vervollständigen Sie dazu die Funktion **extract\_file**, sodass diese den Inhalt einer Datei aus dem Image liest und unter dem originalen Dateinamen im aktuellen Verzeichnis speichert. Achten Sie darauf, dass alle allokierten Ressourcen (Dateien, Speicher) ordnungsgemäß freigegeben werden. Kopieren Sie den gesamten Inhalt von **fat2.c** in dieses Feld. *[Antwortfeld, mehrzeilig]* ## A5: Sortieren und verkettete Listen (9 Punkte) ### A5a (3 Punkte) Gegeben sei ein Array mit 8 Elementen. Dieses Array soll sortiert werden. Dazu wird eine MergeSort-Funktion verwendet, die Merge Sort rekursiv implementiert. Die verwendete MergeSort-Funktion ist wie folgt implementiert: - Prüfe, ob Basisfall vorliegt (einzelnes Element) - Sonst: - Teile Array in zwei Hälften - Sortiere Hälften jeweils durch Aufruf von MergeSort - Führe sortierte Hälften zusammen Wie oft wird die MergeSort-Funktion insgesamt aufgerufen, um das Array zu sortieren? *Keine Begründung erforderlich.* *Tipp:* Skizzieren Sie, welche Schritte nacheinander durchlaufen werden. *[Antwortfeld]* Welches bekannte Prinzip oder Entwurfsmuster für Algorithmen bildet die Grundlage von Merge Sort und ermöglicht seine effiziente Laufzeitkomplexität? *[Antwortfeld]* ### A5b (6 Punkte) Neben der Ihnen bekannten einfach verketteten Liste gibt es auch *doppelt verkettete Listen*. Diese lassen sich mit folgender Datenstruktur implementieren: ```c typedef struct list_node { int value; struct list_node *next; struct list_node *prev; }; ``` Mit dieser Datenstruktur wurde eine sortierte doppelt verkettete Liste erstellt, die bereits folgende Elemente in aufsteigender Reihenfolge enthält: 10, 25, 40, 55. Im Speicher wird dies wie folgt abgebildet (Speicheradressen sind vierstellig): ```c // Pointer auf den Listenanfang struct list_node* head = 0x1000; // Pointer auf das Listenende struct list_node* tail = 0x4000; 0x1000: [10, 0x2000, NULL] // Erstes Element (prev ist NULL) 0x2000: [25, 0x3000, 0x1000] // Zweites Element 0x3000: [40, 0x4000, 0x2000] // Drittes Element 0x4000: [55, NULL, 0x3000] // Letztes Element (next ist NULL) ``` Fügen Sie die Werte 30 und 60 in die sortierte doppelt verkettete Liste ein. Legen Sie dazu neue Knoten mit von Ihnen gewählten vierstelligen Speicheradressen an. In Ihrer Antwort geben Sie die neuen Knoten in der gleichen Schreibweise an wie in der Aufgabenstellung, also Speicheradresse gefolgt vom Inhalt des Knotens. Ihre Antwort muss auch alle notwendigen Änderungen an bestehenden Knoten dokumentieren (auch hier Angabe der Speicheradresse und des veränderten Inhalts). Geben Sie außerdem an, wie sich der head- und tail-Pointer nach den Einfügeoperationen verändert haben. Achten Sie darauf, dass alle Verbindungen in beide Richtungen korrekt gesetzt werden und die Liste nach dem Einfügen weiterhin aufsteigend sortiert ist. Geben Sie hier den Zustand Ihrer Liste und den Inhalt der Pointer *head* und *tail* nach dem Einfügen aller Knoten an (nur den Endzustand) *[Antwortfeld, mehrzeilig]* ## A6: Structs und Pointer (10 Punkte) ### A6a (3 Punkte) Gegeben sei ein Integer **int i** sowie die Pointer **int \*p** und **int \*q**, die beide auf **i** zeigen. Geben Sie alle Zuweisungen an, die gültig sind. **Gültig** bedeutet, dass der Code kompiliert und dass Inhalt und Zweck der Variablen gleich bleiben. Antworten Sie, indem Sie die Buchstaben der einzelnen Zuweisunge durch Komma getrennt eintragen. Also z. B. **a, d, g**, wenn sie der Meinung sind, dass dies gültige Zuweisungen sind. ```text (a) p = i; (d) p = &q; (g) p = *q; (b) *p = &i; (e) p = *&q; (h) *p = q; (c) &p = q; (f) p = q; (i) *p = *q; ``` Geben Sie die Zuweisungen an, die gültig sind. *[Antwortfeld]* ### A6b (7 Punkte) Gegeben sind folgende Strukturen für die Implementierung eines Stacks: ```c typedef struct Node { int value; struct Node *next; } Node; typedef struct Stack { Node *top; } Stack; ``` Implementieren Sie eine Funktion `void push(Stack *s, int value)`, um ein Element auf den Stack zu legen. Dabei müssen Sie prüfen, ob der übergebene Pointer gültig ist, also nicht NULL ist. Falls der Stack leer ist, hat der Pointer `Node *top` den Wert NULL. Beim letzten Element des Stacks hat `struct Node *next` den Wert NULL. Im Verzeichnis `stack` befindet sich die Datei `stack.c` mit einem bereits generierten Stack, die sie verwenden können, um Ihre Implementierung zu testen. Kopieren Sie **nur Ihre push-Funktion** in dieses Feld. *[Antwortfeld, mehrzeilig]* ## B1: Python und OOP (25 Punkte) ### B1a (6 Punkte) Schreiben Sie ein Python-Programm, das einen Wert in Meilen entgegennimmt und diesen in Kilometer umrechnet. Runden Sie Ihre Ausgabe auf 2 Dezimalstellen (also z.B. `5.12`). Nutzen Sie folgendes Umrechnungsverhältnis: 1 Meile = 1,609344 Kilometer. Verwenden Sie in dieser Aufgabe **nicht** die cs50-Bibliothek. Wandeln Sie stattdessen die eingelesene Zeichenkette `str` mit der Funktion `float(str)` in eine Fließkommazahl um. Die Ausgabe des Programms sollte für die Eingabe `23.0` wie folgt aussehen (es können auch Ganzzahlen eingegeben werden): ```text Distanz in Meilen: 23.0 23.0 Meilen sind ungefähr 37.01 Kilometer. ``` Fügen Sie das vollständige Programm in dieses Feld ein. *[Antwortfeld, mehrzeilig]* ### B1b (6 Punkte) In dieser Aufgabe dürfen Sie die cs50-Bibliothek verwenden. Schreiben Sie ein Programm, das einen String über die Eingabeaufforderung entgegennimmt. Das Programm soll ermitteln, wie oft jedes Zeichen im eingegebenen String vorkommt. Berücksichtigen Sie dabei alle eingegebenen Zeichen, einschließlich Leerzeichen, und unterscheiden Sie zwischen Groß- und Kleinbuchstaben. Das Programm soll die Häufigkeiten in einem **Dictionary letters** speichern und am Ende des Programm das Dictionary mit `print(letters)` ausgeben. Die Ausgabe soll wie folgt aussehen: ```text Eingabe: Hallo {'H': 1, 'a': 1, 'l': 2, 'o': 1} ``` Fügen Sie das vollständige Programm in dieses Feld ein. *[Antwortfeld, mehrzeilig]* ### B1c (6 Punkte) Gegeben ist folgender C-Code: ```c #include <stdio.h> int main(int argc, char *argv[]) { typedef struct { char* name; int age; } person; person people[2]; people[0].name = "Alice"; people[0].age = 25; people[1].name = "Bob"; people[1].age = 30; for (int i = 0; i < 2; i++) { printf("Person %i: Name: %s, Age: %i\n", (i + 1), people[i].name, people[i].age); } } ``` Wandeln Sie dieses C-Programm in ein entsprechendes Python-Programm um. Programmieren Sie objektorientiert, d.h. verwenden Sie eine Klasse `Person` mit den Attributen `name` und `age`. Sie müssen keine Methoden oder Properties verwenden. Speichern Sie die zwei Person-Objekte in einer Liste. Iterieren Sie über die Liste, um die gleichen Daten auszugeben wie im C-Programm. Fügen Sie das vollständige Programm in dieses Feld ein. *[Antwortfeld, mehrzeilig]* ### B1d (7 Punkte) Schreiben Sie ein Python-Programm, das eine ASCII-Leiter basierend auf zwei Parametern **n** und **m** ausgibt: - Der Parameter **n** bestimmt zwei Eigenschaften: - Die **Breite der Sprossen** (die horizontalen Verbindungsstücke, bestehend aus "-"-Zeichen) - Die **Länge der Holmstücke** (die vertikalen Teile zwischen den Sprossen, bestehend aus "#"-Zeichen) - Der Parameter **m** gibt an, wie viele Zwischenräume (Sprossen mit den dazugehörigen Holmstücken) die Leiter haben soll. - Die Bereiche innerhalb der Leiter sind mit Leerzeichen ausgefüllt. - Die Holme (die senkrechten Teile) bestehen aus `#`-Symbolen - Die Verbindung zwischen Sprossen und Holmen wird durch `+` dargestellt. Lesen Sie die Parameter **n** und **m** nacheinander über die input()-Funktion oder eine geeignete Funktion aus der cs50-Bibliothek von der Konsole ein. Hier einige Beispiele zur Veranschaulichung: ```text n=3, m=3 n=1, m=5 n=5, m=2 +---+ +-+ +-----+ # # # # # # # # +-+ # # # # # # # # +---+ +-+ # # # # # # # # # # +-+ +-----+ # # # # # # +---+ +-+ # # # # # # # # # # +-+ # # # # # # +---+ +-----+ ``` Fügen Sie das vollständige Programm in dieses Feld ein. *[Antwortfeld, mehrzeilig]* ## B2: Budget Tracker und Debugging (15 Punkte) In dieser Aufgabe entwickeln Sie Teile einer Flask-Anwendung zur Verwaltung von Ausgaben. Ihre Aufgabe wird es sein, den Login und eine Ausgabenübersicht mit Test-Daten zu implementieren. Für diese Aufgabe stellen wir Ihnen Quellcode zur Verfügung, den Sie vervollständigen müssen. Wechseln Sie dazu im Terminal in das Verzeichnis **exam-files/budget**, das sich in Ihrem Homeverzeichnis */home/student* befindet. Damit Code-Änderungen vom Flask-Server automatisch berücksichtigt werden, müssen Sie den Server wie folgt starten: **`flask --debug run`** Um die Anwendung im Browser zu öffnen, klicken Sie bei gedrückter <kbd>Strg</kbd>-Taste auf die URL (*Running on ...*), die Flask nach dem Start anzeigt. Um Flask zu beenden, verwenden Sie die Tastenkombination <kbd>Strg-C</kbd>. ### B2a (5 Punkte) Zunächst implementieren Sie die Login-Funktion. Hierfür müssen Sie die Funktion für die "/"-Route implementieren (*index*). Implementieren Sie folgende Fälle: **Fall 1: GET-Requests:** Die Funktion soll das Template `login.html` rendern. **Fall 2: POST-Requests:** Die Funktion soll zunächst prüfen, ob die in das Formular eingegebenen Daten korrekt sind. Dazu müssen Sie die Formularfelder `username` und `password` auslesen und mit den Angaben im `users`-Dictionary abgleichen. Dort stehen die korrekten Daten. Die *Keys* sind die Benutzernamen. Als *Value* wird jeweils ein Dictionary gespeichert, in dem unter anderem das Passwort abgelegt ist. **Fall 2a:** Es ist kein Eintrag für den eingegebenen Benutzernamen vorhanden oder das eingegebene Passwort stimmt nicht mit dem hinterlegtem Passwort überein. In diesem Fall leiten Sie den Browser auf `/` um. Dies bewirkt, dass der Browser die Seite erneut mit einem GET-Request abruft und das Login-Formular anzeigt. **Fall 2b:** Der Benutzer existiert und das Passwort ist korrekt. In diesem Fall weisen Sie der Session-Variablen *username* den im Formular eingegebenen Benutzernamen zu. Beispiel: `session["username"] = <...>`. Danach leiten Sie den Browser nach `/home` um. Kopieren Sie **nur Ihre index-Funktion inklusive @app.route-Decorator** in dieses Feld. *[Antwortfeld, mehrzeilig]* ### B2b (5 Punkte) In dieser Teilaufgabe sollen Sie die Testdaten, die im Dictionary `users` hinterlegt sind, auslesen und im Template `home.html` rendern. *Hinweis: Wenn Sie die Teilaufgabe B2a nicht lösen konnten, entfernen Sie den Decorator @login\_required über `show_expenses()` und setzen Sie den User mit folgender Codezeile statisch auf den Testuser: `user = users['test']`.* Lesen Sie dazu den User-Eintrag für den aktuell angemeldeten Benutzer aus dem `users`-Dictionary aus. Der aktuell angemeldete Benutzer steht in der Session-Variablen, die Sie in Teilaufgabe B2a verwendet haben. Übergeben Sie anschließend `items` und das `budget` des Users an das Template und rendern Sie dieses. Das Template müssen Sie folgendermaßen vervollständigen: - Iterieren Sie mit einer Schleife über die einzelnen `items` und geben Sie sowohl `description` als auch `price` in der Tabelle aus. - Geben Sie anschließend noch `budget` im div-Element hinter dem Text "Total Budget:" aus. - Fügen Sie schließlich ein weiteres div-Element hinzu, das einen Link mit dem Text "Logout" enthält, über den sich der Benutzer abmelden kann. Verwenden Sie die dafür vorgesehene Route. Kopieren Sie nur die Funktion **show\_expenses** in dieses Feld. *[Antwortfeld, mehrzeilig]* Kopieren Sie den gesamten Inhalt der Datei **home.html** in dieses Feld. *[Antwortfeld, mehrzeilig]* ### B2c (5 Punkte) In der Anwendung gibt es noch die Route `/signup`, allerdings ohne Programmlogik im Flask-Backend. Wird das Account-anlegen-Formular unvollständig oder inkorrekt ausgefüllt, erscheint vor dem Absenden eine Fehlermeldung. Dazu werden die Formularfelder in der Datei `validation.js` clientseitig validiert. Ist eine zusätzliche serverseitige Prüfung der Eingabedaten erforderlich? Begründen Sie kurz warum oder warum nicht. *[Antwortfeld, mehrzeilig]* Das Skript `validation.js` enthält **zwei Fehler**. *Hinweis:* Zur Fehlersuche können Sie die Konsole und den Debugger in den *Developer Tools* des Browsers verwenden. Diese können Sie mit `F12` öffnen. Geben Sie jeweils den Programmcode der Zeilen an, in der die Fehler auftreten und erläutern Sie jeweils stichpunktartig das Problem. *[Antwortfeld, mehrzeilig]*