\documentclass{bschlangaul-aufgabe}
\bLadePakete{mathe}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 9 (Hashing)},
  Thematik = {Hashing mit mod 11 und 13},
  Referenz = 66115-2019-H.T2-A9,
  RelativerPfad = Examen/66115/2019/09/Thema-2/Aufgabe-9.tex,
  ZitatSchluessel = examen:66115:2019:09,
  ZitatBeschreibung = {Thema 2 Aufgabe 9},
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Streutabellen (Hashing)},
  EinzelpruefungsNr = 66115,
  Jahr = 2019,
  Monat = 09,
  ThemaNr = 2,
  AufgabeNr = 9,
}

Verwenden Sie die Hashfunktion $h(k,i) = (h'(k) + i^2) \mod 11$ mit
$h'(k) = k \mod 13$, um die Werte $12$, $29$ und $17$ in die folgende
Hashtabelle einzufügen. Geben Sie zudem jeweils an, auf welche Zellen
der Hashtabelle zugegriffen wird.
\index{Streutabellen (Hashing)}
\footcite[Thema 2 Aufgabe 9]{examen:66115:2019:09}

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
0&1&2&3&4&5&6&7&8&9&10\\\hline
&&&16&&5&&&&22&\\\hline
\end{tabular}
\end{center}

\begin{bAntwort}
\bPseudoUeberschrift{Einfügen des Wertes 12}

$h'(12) = 12 \mod 13 = 12$

$h(12, 0) = 12 + 0^2 \mod 11 = 1$

\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
0&1&2&3&4&5&6&7&8&9&10\\\hline
&12&&16&&5&&&&22&\\\hline
\end{tabular}

\bPseudoUeberschrift{Einfügen des Wertes 29}

$h'(29) = 29 \mod 13 = 3$

$h(29, 0) = 3 + 0^2 \mod 11 = 3$ (belegt von 16)

$h(29, 1) = 3 + 1^2 \mod 11 = 4$

\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
0&1&2&3&4&5&6&7&8&9&10\\\hline
&12&&16&29&5&&&&22&\\\hline
\end{tabular}

\bPseudoUeberschrift{Einfügen des Wertes 17}

$h'(17) = 17 \mod 13 = 4$

$h(17, 0) = 4 + 0^2 \mod 11 = 4$ (belegt von 29)

$h(17, 1) = 4 + 1^2 \mod 11 = 5$ (belegt von 5)

$h(17, 2) = 4 + 2^2 \mod 11 = 8$

\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
0&1&2&3&4&5&6&7&8&9&10\\\hline
&12&&16&29&5&&&17&22&\\\hline
\end{tabular}

\end{bAntwort}

\end{document}
