【基本情報技術者】平成25年春期　午前問7　ハッシュ法

5けたの a1a2a3a4a5 をハッシュ法を用いて配列に格納したい。ハッシュ関数を mod(a1＋a2＋a3＋a4＋a5，13) とし，求めたハッシュ値に対応する位置の配列要素に格納する場合、 54321 は次の配列のどの位置に入るか。ここで、mod(x，13) の値は x を 13 で割った余りとする。

ア　1　　　イ　2　　　ウ　7　　　エ　11

【解説】
ハッシュ法　とは、探索するデータのキー値からデータの格納アドレスを直接計算する方法です。
この計算の際に使われる関数を　ハッシュ関数　といいます。

この問題のハッシュ関数は、各桁の数値をそれぞれ足し算をし、
さらに13で割った余りをもって配列要素の格納位置を定めます。

　　　mod(a1＋a2＋a3＋a4＋a5、13)　

なので、そのまま "54321" を当てはめると、

　　　mod(5＋4＋3＋2＋1，13)＝2

mod()は余りを求めるので、つまり　

　　　15÷13＝1　余り2

と　いうことになります。
したがってデータ "54321" は配列の 2番目 の位置に格納されることになります。

【解答】イ

[ この問題の出題歴 ]
基本情報技術者平成16秋期午前　問14
基本情報技術者平成22秋期午前　問7

【基本情報技術者】平成23年特別　午前問5　２分探索木

空の2分探索木に，8，12，5，3，10 7，6 の順にデータを与えたときにできる2分探索木はどれか。

【解説】

２分探索木とは、左の子のデータが親（上位）より小さく、右の子は必ず親より大きい ようにデータを配置したもの。

データを与えられた順番に配置していくと、一番上位（ルート）が　8、次の節が　12と5に　それぞれ　右左に振られる。

その次の3、10、7が　同レベルに位置できるなら配置することで、6は、最下位レベルと設置されます。

【解答】エ

【基本情報技術者】平成24年秋期　午前問5　キューとスタックの操作

四つのデータA，B，C，Dがこの順に入っているキューと空のスタックがある。手続　pop_enq，deq_push　を使ってキューの中のデータをD，C，B，Aの順に並べ替えるとき、deq_push の実行回数は最小で何回か。ここで、pop_enq はスタックから取り出したデータをキューに入れる操作であり、deq_push はキューから取り出したデータをスタックに入れる操作である。

ア　2　　　イ　3　　　ウ　4　　　エ　5

【解説】
「キュー」 と 「スタック」 のデータ構造を思い出してください。

●キュー
先入れ先出し（FirstIn　FirstOut）。　
データを　追加操作は enqueue (エンキュー)、データを　取り出す操作は dequeue (デキュー)　と呼ばれる。

●スタック
後入れ先出し（FirstIn　LastOut）。　
データを　追加操作は push (プッシュ)、データを　取り出す操作は pop (ポップ)　と呼ばれる。

問題文より、求めるのは、　deq_push の実行回数。
つまり、この問題文の手続では、キューの中でのデータを取り出す操作（dequeue(デキュー)）の最小回数を求めることになります。

初期状態は、キューの中は　ABCDの順に投入されているので　スタックは　空　です。

求めるのは、「キューの中のデータをD，C，B，Aの順に並べ替える」ことですから、

になることが　望まれています。

スタックは　作業領域と考え、後にキューに入力されるデータを下に置くことが望ましいとされます。

すなわち、ABCD　の順に　スタックに入力されれば、取り出すときに　DCBAの順になり、それをキューに投入すれば並び替えがおこなわれたことになります。

キューからの取り出しは　ABCDの並びになっているので　順にスタックに投入していき、Dがキューの先頭に来た時に　スタックから取り出しキューに投入していけば、並び替えは終了します。

　　　　　手順１.　キューからAを取り出しスタックに追加する。(deq_push)