Grundlegende Algorithmen: Lösungshinweise

Kapitel 4

4.1

Nein, da nicht surkektiv.

4.2

Es muss ggT(l,n)=1 gelten, da sonst die verallgemeinerte Hashfunktion nicht surjektiv ist.
Primäre und sekundäre Häufung bleiben bestehen.

4.3

---

4.4

Ja, durch sukzessives Einfügen in den Suchbaum und anschließendes Traversieren des Baumes in Preorder.
Zeitbedarf O(nlog(n)).

4.5

Durch Induktion und Ausnutzen der Rekursion |T(h)|≥1+|T(h-1)|+|T(h-2)|.

4.6

Minimale Anzahl für gerades h: 2^(h/2+2)-3.
Minimale Anzahl für ungerades h: 3*2^((h+1)/2)-3.
Maximale Anzahl: 2^(h+1)-1.

4.7

---

4.8

Für einen Hinweis das Kapitel nochmal lesen.

4.9

Einsetzen und Nachrechnen.

4.10

Maximale Anzahl: (b^h+1-1)/(b-1).
Minimale Anzahl: 1+(a^h-1)/(a-1) (Die Wurzel darf ein Kind haben!).

4.11

---

4.12

Fleißaufgabe.