配列に対して、データを格納すべき位置（配列の添字）をデータのキーの値を引数とする関数（ハッシュ関数）で求めることによって、探索だけでなく追加や削除も効率よく行うのがハッシュ法である。通常、キーのとり得る値の数に比べて、配列の添字として使える値の範囲は狭いので、衝突（collision）と呼ばれる現象が起こり得る。衝突が発生した場合の対処方法の一つとして、同一のハッシュ値をもつデータを線形リストによって管理するチェイン法（連鎖法ともいう）がある。8個のデータを格納したときの例を図1に示す。このとき、キー値は正の整数、配列の添字は0～6の整数、ハッシュ関数は引数を7で割った剰余を求める関数とする。このチェイン法を実現するために、表に示す構造体、配列及び関数を使用する。

設問2　【探索関数search】について、(1)、(2)に答えよ。(1) 図1の場合、キー値が23のデータを探索するために、ノードにアクセスする順序はどのようになるか。"key1→key2→…→23"のように、アクセスしたノードのキー値の順序で答えよ。(2) 図2のアからウに入れる適切な字句を答えよ。

設問3　【追加関数addNode】のプログラム、図3のエ、オに入れる適切な字句を答えよ。

設問4　【チェイン法の計算量】について、(1)、(2)に答えよ。(1) カに入れる適切な字句を25字以内で答えよ。(2) キに入れる計算量をO記法で答えよ。