\documentclass[loesungsseite]{schullzk}
\usepackage[utf8]{inputenc}

% Dieses Dokument ist in der Zusammenarbeit von Informatikreferendaren und
% ehemaligen Informatikreferendaren der Studienseminare (heute ZfsL) Arnsberg,
% Hamm und Solingen entstanden.
%
% Das Dokument steht unter der Lizenz: Creative Commons by-nc-sa Version 4.0
% http://creativecommons.org/licenses/by-nc-sa/4.0/deed.de
%
% Nach dieser Lizenz darf das Dokument beliebig kopiert und bearbeitet werden,
% sofern das Folgeprodukt wiederum unter gleichen Lizenzbedingungen vertrieben
% und auf die ursprünglichen Urheber verwiesen wird.
% Eine kommerzielle Nutzung ist ausdrücklich ausgeschlossen.
%
% Die Namensnennung durch einen Verweis und die Lizenzangabe der ursprünglichen
% Urheber auf den Materialien für Schülerinnen und Schüler ist erforderlich.
%
% Die Sammlung der Dokumente steht unter
% http://ddi.uni-wuppertal.de/material/materialsammlung/
% zur Verfügung.
%
% Das LaTeX-Paket zum Setzen der Dokumente der Sammlung steht
% unter  http://www.ctan.org/pkg/schule
% zur Verfügung.

\usepackage[pdfauthor={Referendare der Informatikfachseminare Arnsberg, Hamm und Solingen}]{hyperref}
\includexmp{lizenz}
\cclizenz{byncsaeu}
\footerQRLink{materialsammlung_qr_url.pdf}

\ihead{Kapiteltests zu verzweigte Datenstrukten}
\chead{}

\svnid{$Id: leitprogramm_verzweigte_datenstrukturen_kapiteltest.tex 1478 2016-04-11 15:57:22Z humbert $}

\begin{document}

\section*{Zu Kapitel 1:}

\begin{enumerate}
	\item Beschreiben Sie die binäre Suche in eigenen Worten.
	\item Nennen Sie die Vorteile der binären gegenüber der linearen Suche.
	\item Wenden Sie die binäre Suche auf folgende Liste an, um  
	  \enquote{Papagei} zu finden.
	\begin{enumerate}[1.]
		\item Affe
		\item Bär
		\item Chamäleon
		\item Delfin
		\item Erdmännchen
		\item Flunder
		\item Giraffe
		\item Hund
		\item Igel
		\item Jaguar
		\item Katze
		\item Luchs
		\item Maus
		\item Nasenbär
		\item Ozelot
		\item Papagei
		\item Qualle
		\item Rentier
		\item Schwein
		\item Tintenfisch
		\item Uhu
		\item Vogelspinne
		\item Wegschnecke
		\item Xenops (ein Singvogel)
		\item Yak
		\item Zebra
	\end{enumerate}
\end{enumerate}

\loesung{
	\begin{enumerate}
		\item Zu nennende Kriterien: Aufteilen der Listen in zwei gleiche Teile, danach \enquote{Springen} zur Mitte des verbleibenden Teils, usw.
		\item Erwartete Antwort: Liste nicht komplett durchlaufen werden, ist v.\,a. schnell, um herauszufinden, ob ein Element überhaupt vorhanden ist.
		\item Lösungschritte: 13, 20, 17, 16
	\end{enumerate}
}

\clearpage

\section*{Zu Kapitel 2:}
\begin{enumerate}
%<*a1-2>
	\item Beschreiben Sie in eigenen Worten, woraus ein binärer Suchbaum besteht und zeichnen Sie ein Beispiel mit 10~Knoten auf. Die Knoten sollen dabei ausschließlich Zahlen enthalten.
	\item Beschreiben Sie anhand Ihres Beispiels den \enquote{In order}-Durchlauf und demonstrieren Sie diesen.
%</a1-2>
\end{enumerate}

\loesung{
	\begin{enumerate}
		\item Zu nennende Elemente: Wurzel, Kanten, Knoten, Teilbäume. Wichtig beim aufgezeichneten Beispiel: Die Eigenschaft aus Abschnitt \enquote{Eigenschaften des binären Suchbaums} muss erfüllt sein, d.\,h. alle Knoten links eines vorgegebenen Knotens müssen kleiner sein als der Knoten selbst.
		\item 
	\end{enumerate}
}

\clearpage

\section*{Zu Kapitel 3:}
\begin{enumerate}
	\item Beschreiben Sie, welche Attribute und Methoden Objekte vom Typ \textsc{Knoten} benötigen.
	\item Wie lässt sich der Aufbau eines binären Suchbaums objektorientiert realisieren?
	\item Beschreiben Sie in eigenen Worten, wie beim Einfügen eines neuen Knotens vorzugehen ist.
\end{enumerate}

\loesung{
	\begin{enumerate}
		\item Zu nennen sind hier: linker/rechter Nachfolger, ein Attribut zum Speichern eines Wertes; Ausgabe des linken/rechten Nachfolgers; setzen derselben
		\item Erwartete Antwort: kennt-Beziehung zwischen den Knoten, so dass die Knoten \enquote{aneinander hängen}.
		\item Erwartete Antwort: Betrachte Wurzel; Entscheidung für \enquote{links} oder \enquote{rechts}; wenn kein Nachfolger dort vorhanden, füge ein; sonst wiederhole Vorgehensweise.
	\end{enumerate}
}

\clearpage

\section*{Zu Kapitel 4:}
%<*a3-abb>
\begin{center}
	\begin{tikzpicture}[level distance=10mm, level/.style={sibling distance=55mm/#1}, every node/.style={draw,circle,fill=white,text width=1em,text centered}]
		\node (root) {12}
			child {node {11}
				child {node {10}
					child {node {4}}
					child[missing] {node {x}}
				}
				child[missing] {node {14}}
			}
			child {node {27}
				child {node {14}
					child[missing] {node {x}}
					child {node {21}}
				}
				child {node {42}
					child {node {29}}
					child[missing] {node {x}}
				}
			};
	\end{tikzpicture}
\end{center}
%</a3-abb>

\begin{enumerate}
%<*a3-1>
	\item Geben Sie die Höhendifferenzen für alle Knoten an. An welcher Stelle ist die Ausgeglichenheitsbedingung verletzt?
	\item Welche Rotation muss durchgeführt werden, um den Baum auszugleichen?
%</a3-1>
\end{enumerate}

\loesung{
	\begin{enumerate}
		\item Siehe Baum
			\begin{center}
% 				\begin{tikzpicture}[level distance=10mm, level/.style={sibling distance=55mm/#1}, every node/.style={draw,circle,fill=white,text width=1em,text centered},every label/.style={label position=above,fill=orange!40,circle,draw=none,text width=1em,minimum height=0}, every label/.prefix code={\scriptsize}]
% 					\node[label=0] (root) {12}
% 						child {node[label=-2] {11}
% 							child {node[label=-1] {10}
% 								child {node[label=0] {4}}
% 								child[missing] {node {x}}
% 							}
% 							child[missing] {node {14}}
% 						}
% 						child {node[label=0] {27}
% 							child {node[label=+1] {14}
% 								child[missing] {node {x}}
% 								child {node[label=0] {21}}
% 							}
% 							child {node[label=-1] {42}
% 								child {node[label=0] {29}}
% 								child[missing] {node {x}}
% 							}
% 						};
% 					\node[draw,circle,line width=2pt,red,fit=(root-1),fill=none,yshift=.8em] {};
% 				\end{tikzpicture}
			\end{center}
		\item Erwartete Antwort: Eine R-Rotation um den Knoten~11.
			\begin{center}
% 				\begin{tikzpicture}[level distance=10mm, level/.style={sibling distance=55mm/#1}, every node/.style={draw,circle,fill=white,text width=1em,text centered},every label/.style={label position=above,fill=orange!40,circle,draw=none,text width=1em,minimum height=0}, every label/.prefix code={\scriptsize}]
% 					\node[label=0] (root) {12}
% 						child {node[label=0] {10}
% 							child {node[label=0] {4}
% 								child[missing] {node[label=0] {4}}
% 								child[missing] {node {x}}
% 							}
% 							child{node[label=0] {11}}
% 						}
% 						child {node[label=0] {27}
% 							child {node[label=+1] {14}
% 								child[missing] {node {x}}
% 								child {node[label=0] {21}}
% 							}
% 							child {node[label=-1] {42}
% 								child {node[label=0] {29}}
% 								child[missing] {node {x}}
% 							}
% 						};
% 					\end{tikzpicture}
				\end{center}
	\end{enumerate}
}

\end{document}
