%  Zwischenklausur ALP3 WS 2003/2004
\documentclass [11pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\usepackage[latin1]{inputenc}
\textwidth=15,5cm
\textheight=25cm
\hoffset = -17mm
\voffset = -35mm

\begin{document}

\def\blatt#1#2#3#4
{
\count0=4
\begin{centering}
{\large \bf Algorithmen und Programmieren 3
%\hfill Matrikelnummer: \vrule width 3cm height -2.5pt depth 3pt

% WS 2003/2004,
erste Nachklausur zur ersten Teilklausur% \hfill\null

%\null
%\hfill FAMILIENNAME: \vrule width 4cm height -2.5pt depth 3pt

Donnerstag, 26. Februar 2004.
%\hfill Vorname: \vrule width 4cm height -2.5pt depth 3pt
\par}
%\bigskip
\par \bigskip
\end{centering}
\hrule
\medskip

\noindent \emph{Anleitung}:
Streichen Sie \emph{eine} Aufgabe deutlich auf dem Angabeblatt.
Diese Aufgabe wird nicht in die Bewertung einbezogen.
Wenn Sie selbst keine Aufgabe streichen, wird die erste
Aufgabe nicht in die Bewertung einbezogen.
Bearbeiten Sie die "ubrigen drei Aufgaben.\medskip

\emph{Bearbeiten Sie jede Aufgabe auf einem getrennten Blatt.}
Jede Aufgabe hat 10 Punkte. Bearbeitungszeit: 90 Minuten

% $$
% \begin{tabular}[c]{|l|c|c|c|c|c|}
% \hline
% Aufgabe&1&2&3&4&Summe\\
% \hline
% Punkte&10&10&10&10&30\\
% \hline
% Punkte&&&&&\\
% \hline
% \end{tabular}
% $$
\medskip
\hrule
\medskip



\begin{enumerate}
%\parskip=0,5\parskip
%\itemsep=0,4\itemsep
\item \aufgabe #1
\item \aufgabe #2
\item \aufgabe #3
\item \aufgabe #4
\end{enumerate}
\eject
}

\newbox\prog
\setbox\prog=\vbox{
\begin{verbatim}
class Liste { Object wert; Liste next; }
\end{verbatim}
\vskip -3,5ex
\hrule height 0pt
\begin{verbatim}
static Liste umkehre(Liste x)
{ if(x==null) return x;
  else return umkehre3(null, x, x.next);
}
static Liste umkehre3(Liste davor, Liste x, Liste danach)
{ x.next = davor;
  if (danach==null) return x;
  else return umkehre3(x, danach, danach.next);
}
\end{verbatim}}

\long\def\aufgabe #1{\ifcase #1\or

Wir wollen eine Variante von $a$-$b$-Bäumen konstruieren, bei der
weniger Speicher verschwendet wird.
Es sei $a=50$. Wie klein kann man $b$ wählen, wenn man
\begin{itemize}
\item beim Einfügen \emph{zwei} Geschwisterknoten zu Hilfe nimmt, falls
  diese den Überlauf aufnehmen können, und
\item beim Entfernen bis zu \emph{drei} Geschwisterknoten zum
  Ausborgen in Betracht zieht?
\end{itemize}
Begründen Sie Ihre Antwort!
\or
%\item %(10 Punkte)
Eliminieren Sie die Endrekursion aus dem folgenden Programmstück,
das eine verkettete Liste umkehrt.
Gehen Sie dabei systematisch Schritt für Schritt vor, und geben Sie
alle Zwischenschritte bei der Transformation explizit an.
Schreiben Sie am Ende eine einzige Methode als Ersatz für \texttt{umkehre}.
\\
\noindent\null\qquad\rlap{\copy\prog}


\or % \item

Schreiben Sie ein Java-Programm, das die Knoten eines binären Baumes
in \emph{Niveau-Reihenfolge} ausgibt, das heißt, zuerst die Wurzel,
dann die Knoten mit Tiefe 1, dann mit Tiefe 2, und so weiter.

Ihr Programm soll lineare Laufzeit haben.


\or % \item %(10 Punkte)
 Gegeben ist ein Graph mit den Knoten $V=\{1,2,\ldots,n\}$ und
  $m$ Kanten in Adjazenzlistenspeicherung.
Die Kanten in $(i,j)$ den Adjazenzlisten sollen nach den Endknoten
  umsortiert werden; das heißt, in der Adjazenzliste von $i$ soll die
  Kante $(i,j)$ vor $(i,k)$ kommen, wenn $j<k$ ist.

  \begin{enumerate}
  \item 
Skizzieren Sie einen Algorithmus, der diese Sortieraufgabe \emph{in
  linearer Zeit}, das heißt, in $O(m+n)$ Zeit
löst.%\\
%(Hinweis: Denken Sie an Radix-Sort.)

\item Schreiben Sie ein Java-Programm für diese Aufgabe.
  \end{enumerate}

\fi
}

\def\alleperm
{
\blatt 1234
\blatt 2341
\blatt 3412
\blatt 4123

\blatt 1243
\blatt 2431
\blatt 4312
\blatt 3124

\blatt 1432
\blatt 4321
\blatt 3214
\blatt 2143

\blatt 1423
\blatt 4231
\blatt 2314
\blatt 3142

\blatt 1342
\blatt 3421
\blatt 4213
\blatt 2134

\blatt 1324
\blatt 3241
\blatt 2413
\blatt 4132
}

\blatt 1423
%\alleperm

%\blatt 1234
\end{document}
