"readme.md" did not exist on "4b6535c752e754bef1d385e548972ed853021287"
Select Git revision
klausur.tex 11.51 KiB
\thispagestyle{empty}
\strut\hfill
\includegraphics[height=1.5cm]{logo-hochschule-bochum.pdf}
\section*{Hardwarenahe Programmierung / Angewandte Informatik\\
Klausur -- 6.\ Februar 2017}
Prof.~Dr.~Peter Gerwinski, Wintersemester 2016/17
\bigskip
\bigskip
\begin{center}
\renewcommand{\arraystretch}{2.0}
\begin{tabular}{|l|p{10cm}|} \hline
Name: & \\\hline
Matrikel-Nr.: & \\\hline
Benutzername: & \username \\\hline
Passwort: & \password \\\hline
\rule{0pt}{0.8cm}\raisebox{-1pt}{\shortstack[l]{Prüfsumme der hoch-\\[1pt]geladenen Datei:}} & \\\hline
\end{tabular}
\end{center}
\bigskip
Zeit: 150 Minuten
Zulässige Hilfsmittel:
\begin{itemize}
\item Schreibgerät
\item Beliebige Unterlagen in Papierform und/oder auf Datenträgern
\item Elektronische Rechner (Notebook, Taschenrechner o.\,ä.)
\item Zugang zum Klausur-WLAN
\end{itemize}
Nur die o.\,a.\ zulässigen Hilfsmittel
dürfen sich während der Klausur im Arbeitsbereich befinden.
Der einzige zulässige Zugang zu Datennetzen jeglicher Art
(LAN, WLAN, Bluetooth, \dots) ist der Zugang zum Klausur-WLAN,
das während der Klausur unter der ESSID \lstinline{klausur}
mit Passwort \lstinline{klausurklausur} zugänglich ist.
Sonstige Funkeinheiten (z.\,B.\ Bluetooth) von Notebooks o.\,ä.\
sind auszuschalten; ggf.\ dafür vorhandene physische Schalter sind zu benutzen.
Mobiltelefone, Geräte mit mobilem Internet-Zugang u.\,ä.\
sind auszuschalten und in der Tasche zu verstauen.
Die reguläre Maximalpunktzahl beträgt \totalpoints\ Punkte.\\
Bei besonderen Leistungen sind Zusatzpunkte möglich.\\
Mit 20 erreichten Punkten gilt die Klausur als bestanden.
Die Beispielprogramme werden Ihnen über das \textbf{Klausur-WLAN}
unter der URL \url{http://klausur} zum Herunterladen angeboten.
Unter derselben URL finden Sie auch ein Web-Interface
zum Hochladen \emph{einer einzigen Datei\/}
(normalerweise eine Archiv-Datei) mit Ihren Klausurergebnissen.
Bei mehrfachem Hochladen wird die vorherige Version überschrieben.
Zulässige Archiv-Dateiformate sind \file{tar.gz}, \file{tar.bz2},
\file{tar.xz}, \file{zip} und \file{7z}.
\textbf{Wichtig: Bitte tragen Sie nach dem Hochladen die Prüfsumme
oben auf diesem Blatt in das dafür vorgesehene Feld ein},
damit wir die Datei eindeutig Ihnen zuordnen können.
Wenn Sie nicht über einen Zugang zum Klausur-WLAN verfügen,
stellen wir Ihnen alternativ die Beispiel-Programme auf Datenträger (USB-Stick)
zur Verfügung. Die Abgabe von digital gelösten Aufgaben
hat dann auf demselben Datenträger zu erfolgen.
\clearpage
\exercise{Strings umsortieren}
Wir betrachten das folgende Programm (\file{aufgabe-1.c}):
\begin{lstlisting}[style=numbered]
#include <stdio.h>
#include <string.h>
void fun (char *s)
{
int len = strlen (s);
for (int i = 0; i < len; i++)
{
for (int j = i - 1; j >= 0; j--)
{
if (s[i] < s[j])
{
char sx = s[i];
s[i] = s[j];
s[j] = sx;
}
}
}
}
int main (void)
{
char s[] = "BAECD";
fun (s);
printf ("%s\n", s);
return 0;
}
\end{lstlisting}
Auf einem Rechner, der den ASCII-Zeichensatz verwendet, lautet die Ausgabe:
\lstinline[style=terminal]{ABCDE}
\begin{enumerate}[\quad(a)]
% \item
% Was bewirkt die Funktion \lstinline{fun}?
% \points{4}
% \workspace{12}
\item
Beweisen Sie (z.\,B.\ anhand eines Gegenbeispiels),
daß die Funktion allgemein \lstinline{fun} \emph{nicht\/} dazu geeignet ist,
die Buchstaben eines Strings gemäß ihrer ASCII-Reihenfolge zu sortieren.
\points{2}
\workspace{9}
\item
Was kann passieren, wenn die Zeile \lstinline{char s[] = "BAECD";}
durch \lstinline|char s[] = { 'B', 'A', 'E', 'C', 'D'|~\lstinline|};| ersetzt wird, und warum?
\points{2}
\workspace{10}
\item
Von welcher Ordnung (Landau-Symbol) ist die Funktion \lstinline{fun} und warum?
Wir beziehen uns hierbei auf die Anzahl der Vergleiche \lstinline{s[i] < s[j]}
in Abhängigkeit von der Länge des Eingabe-Strings \lstinline{"BAECD"}.
\points{1}
\workspace{10}
\item
Beschreiben Sie -- in Worten und/oder als C-Quelltext --, wie
sich die Funktion \lstinline{fun} so abwandeln läßt,
daß sie die Buchstaben des Strings \lstinline{s} gemäß ihrer ASCII-Reihenfolge sortiert.
Von welcher Ordnung (Landau-Symbol) ist Ihre Version der Funktion und warum?
\points{3}
\workspace{22}
\end{enumerate}
\exercise{Speicherformate von Zahlen}
Wir betrachten das folgende Programm (\file{aufgabe-2.c}):
\begin{lstlisting}[style=numbered]
#include <stdio.h> #include <stdint.h>
int main (void)
{
uint16_t numbers[] = { 25928, 27756, 11375, 30496, 29295, 25708, 2593, 0 };
printf ("%s", numbers);
return 0;
}
\end{lstlisting}
Das Programm wird compiliert und ausgeführt:
\begin{lstlisting}[style=terminal]
$ ¡gcc -Wall aufgabe-2.c -o aufgabe-2¿
aufgabe-2.c: In function ‘main’:
aufgabe-2.c:7:3: warning: format ‘%s’ expects argument of type ‘char *’,
but argument 2 has type ‘uint16_t *’ [-Wformat]
$ ¡./aufgabe-2¿
Hello, world!
\end{lstlisting}
\begin{enumerate}[\quad(a)]
\item
Erklären Sie die beim Compilieren auftretende Warnung.
\points{2}
\workspace{8}
\item
Erklären Sie die Ausgabe des Programms.\\
Welche Endianness hat der verwendete Rechner?
\points{4}
\workspace{16}
% \item
% Wie sähe die Ausgabe auf einem Rechner mit entgegengesetzter Endianness aus?
% \points{2}
% \workspace{11}
\item
Erklären Sie die Ausgabe des Programms,
wenn Sie den Datentyp \lstinline{uint16_t} durch \lstinline{uint32_t} ersetzen.
\points{3}
\workspace{12}
\item
Erklären Sie die Ausgabe des Programms
und die beim Compilieren auftretenden Warnungen,
wenn Sie den Datentyp \lstinline{uint16_t} durch \lstinline{uint8_t} ersetzen.
Warum tritt die Warnung aus den vorherigen Aufgabenteilen nicht mehr auf?
\points{3}
\workspace{14}
\end{enumerate}
\exercise{Allgemeine Sortierfunktion}
Ein Zeiger auf \lstinline{void} ist ein \emph{generischer Zeiger},
der auch ohne explizite Typumwandlung zu allen anderen Zeigertypen
zuweisungskompatibel ist.
Wir betrachten das folgende Fragment (\file{aufgabe-3.c})
eines Sortier-Programms:
\begin{lstlisting}
#include <stdio.h>
void sort (void **data, int (*compare) (void *x1, void *x2))
{
for (int i = 0; data[i]; i++)
for (int j = i + 1; data[j]; j++)
if (compare (data[i], data[j]) > 0)
{
void *tmp = data[i];
data[i] = data[j];
data[j] = tmp;
} }
[...]
int main (void)
{
char *strings[] = { "Thomas", "Dora", "Konrad", "Adalbert", "Sophie", NULL };
sort (strings, compare_strings);
for (int i = 0; strings[i]; i++)
printf ("%s\n", strings[i]);
printf ("\n");
int two = 2, ten = 10, zero = 0, three = 3, one = 1;
int *numbers[] = { &two, &ten, &zero, &three, &one, NULL };
sort (numbers, compare_numbers);
for (int i = 0; numbers[i]; i++)
printf ("%d\n", *numbers[i]);
return 0;
}
\end{lstlisting}
Dieses Programm stellt eine allgemeine Sortier-Funktion \lstinline{sort} zur Verfügung,
die prinzipiell beliebige Arrays sortieren kann
-- also z.\,B.\ sowohl Strings als auch Zahlen.
\begin{enumerate}[\quad(a)]
\item
Erklären Sie die Struktur des Arrays \lstinline{numbers}.
Was ist in dem Array gespeichert, und wo befinden sich die Zahlen?
Was ist der Unterschied zwischen \lstinline{&zero} und dem Wert \lstinline{NULL}?
\points{3}
\workspace{15}
\item
Was bedeutet \lstinline{int (*compare) (void *x1, void *x2)},
und für welchen Zweck wird es verwendet?\\
Stellen Sie einen Bezug zur objektorientierten Programmierung her.
\points{3}
\workspace{12}
\item
Was kann passieren, wenn man in den Arrays auf das letzte Element \lstinline{NULL} verzichtet
und warum?\\
\points{1}
\workspace{8}
\item
Ergänzen Sie das Fragment zu einem funktionsfähigen Programm,
das beide Arrays \lstinline{strings} und \lstinline{numbers}
sortiert ausgibt.
\points{5}
Abgabe über das Klausur-WLAN oder auf Datenträger ist erwünscht,
aber nicht zwingend.
Für Notizen verwenden Sie nötigenfalls
die Rückseite des letzten Klausurbogens und/oder zusätzliche Blätter.
\end{enumerate}
\exercise{PBM-Grafik}
Bei einer PBM-Grafikdatei handelt es sich
um ein abgespeichertes C-Array von Bytes (\lstinline{uint8_t}),
das die Bildinformationen enthält:
\begin{itemize}\itemsep0pt
\item Die Datei beginnt mit der Kennung \lstinline{P4},
danach folgen Breite und Höhe in Pixel als ASCII-Zahlen,
danach ein Trennzeichen und die eigentlichen Bilddaten.
\item Jedes Bit entspricht einem Pixel.
\item Nullen stehen für Weiß, Einsen für Schwarz.
\item MSB first.
\item Jede Zeile des Bildes wird auf ganze Bytes aufgefüllt. \end{itemize}
Viele Grafikprogramme können PBM-Dateien öffnen und bearbeiten.
Der Anfang der Datei (Kennung, Breite und Höhe)
ist auch in einem Texteditor lesbar.
Beispiel (\file{aufgabe-4.pbm}):\hfill
\makebox(0,0)[tr]{\framebox{\includegraphics[scale=3]{aufgabe-4.png}}}
\begin{lstlisting}
P4
14 14
<Bilddaten>
\end{lstlisting}
In dem untenstehenden Programmfragment (\file{aufgabe-4.c})
wird eine Grafik aus Textzeilen zusammengesetzt,
so daß man mit einem Texteditor "`malen"' kann:
\begin{lstlisting}
#include <stdio.h>
[...]
int main (void)
{
pbm_open (14, 14, "test.pbm");
pbm_line (" ");
pbm_line (" XXXXXX ");
pbm_line (" X X ");
pbm_line (" X X ");
pbm_line (" X X ");
pbm_line (" X XX XX X ");
pbm_line (" X X X X ");
pbm_line (" X X ");
pbm_line (" X X X X ");
pbm_line (" X X X X ");
pbm_line (" X XXXX X ");
pbm_line (" X X ");
pbm_line (" XXXXXX ");
pbm_line (" ");
pbm_close ();
return 0;
}
\end{lstlisting}
Ergänzen Sie das Programmfragment so,
daß es eine Datei \file{test.pbm} erzeugt,
die die Grafik enthält.
Das Programm soll typische Benutzerfehler abfangen
(z.\,B.\ weniger Zeilen als in \lstinline{pbm_open} angegeben),
keine fehlerhaften Ausgaben produzieren oder abstürzen,
sondern stattdessen sinnvolle Fehlermeldungen ausgeben.
Zum Vergleich liegt eine Datei \file{aufgabe-4.pbm}
mit dem gewünschten Ergebnis bei,\\
und die Datei \file{aufgabe-4.png} enthält dasselbe Bild.
\points{10}
Abgabe über das Klausur-WLAN oder auf Datenträger ist erwünscht,
aber nicht zwingend.
Für Notizen verwenden Sie nötigenfalls
die Rückseite des letzten Klausurbogens und/oder zusätzliche Blätter.
\makeatletter
\immediate\write\@mainaux{\string\gdef\string\totalpoints{\arabic{points}}}
\makeatother
\bigskip
\begin{flushright}
\textit{Viel Erfolg!} \end{flushright}
\clearpage
\thispagestyle{empty}
Raum für Notizen