【 基本情報技術者 】平成22年 秋期 午前 問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()は余りを求めるので、

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

【解答】ウ

[この問題の出題歴]

基本情報技術者 平成16年　秋期 問14

基本情報技術者 平成25年　春期 問7

【 基本情報技術者 】平成22年 秋期 午前 問6 木構造

節点1，2，…，n  をもつ木を表現するために，大きさ n の整数型配列A[1]，A[2]，…，A[n] を用意して，節点i の親の節点を A[i] に格納する。節
点kが根の場合は A[k]＝0 とする。表に示す配列が表す木の葉の数は，幾つか。

ア　　1

イ　　3

ウ　　5

エ　　7

【解説】

木構造とは、階層構造でデータを管理するもので、木を逆さにしたような形をしています。

根から枝分れしながらノードが関連付けていき、直接結ばれているノード間には、なんらかの親子関係がつくられているものです。

根とは、親を持たないもので、通常１つの木構造に１つしかありません。

節とは　親も子ももち、葉は、子を持たない要素の事です。

問題文では、親の節点の値を　配列要素にいれています。

つまり、 2と3の値の要素は、1の節点から分岐されているということです

同様に　4,5は　3を親に持っています。

このことから　木構造を推測すると下記のようになります。

子をもたない葉の要素は　

2と4と6、7,8　の5つに　なります。

【解答】ウ

【 基本情報技術者 】平成21年 春期 午前 問5 スタック

関数や手続を呼び出す際に，戻り番地や処理途中のデータを一時的に保存するのに適したデータ構造はどれか。

ア　2分探索木

イ　キュー

ウ　スタック

エ　双方向連結リスト

【解説】

プログラムの動き方として、ローカル変数や　もとの手続きの呼び出し位置などを　格納していくと、関数が終了するたびに　前に格納したデータから順に取り出して手続きを復帰させます。

つまり、直近に呼び出した関数や　手続の戻り番地や変数の値ほど、先に取り出す必要がでてきます。

スタック　は、LIFO(Last in First Out，後入れ先出し)　のデータ構造です。

主ルーチンからサブルーチン（副プログラム）を呼び出すときに　主ルーチンの戻り番地や変数の値を　一時的に格納しておくときなどに使われ、関数が終了するたびに、復帰させる情報を　取り出すのに適し、使われています。

【解答】ウ