平成25年度秋季解答

問題6

葉以外の節点はすべて二つの子をもち、根から葉までの深さがすべて等しい木を考える。
この木に関する記述のうち、適切なものはどれか。
ここで、深さとは根から葉に至るまでの枝の個数を表す。

ア	枝の個数がn ならば、葉を含む節点の個数もn である。
イ	木の深さがn ならば、葉の個数は2n -1である。
ウ	節点の個数がn ならば、深さはlog2n である。
エ	葉の個数がn ならば、葉以外の節点の個数はn -1である。

解答：エ

＜解説＞

完全二分木（葉以外の節点はすべて二つの子をもち、根から葉までの深さがすべて等しい木）は、次の図のようになる。

ア	×	枝の個数がnならば、葉を含む節点の個数はn+1である。
イ	×	木の深さが n ならば，葉の個数は 2n である。
ウ	×	節点の個数が n ならば，深さは (log2(n+1))-1 である。
エ	○	葉の個数がnならば、葉以外の節点の個数はn-1である。

問題へ

問題7

自然数をキーとするデータを、ハッシュ表を用いて管理する。
キーx のハッシュ関数h (x )を
　h (x ) = x mod n
とすると、キーa とb が衝突する条件はどれか。
ここで、n はハッシュ表の大きさであり、x mod n はx をn で割った余りを表す。

ア	a + b がn の倍数
イ	a - b がn の倍数
ウ	n がa + b の倍数
エ	n がa - b の倍数

解答：イ

＜解説＞

ハッシュ関数とは、与えられたデータから、固定長のデータ(ハッシュ値)を生成する関数である。本問題のハッシュ値はx mod n すなわちxをnで割ったあまりである。

ハッシュ値は、n=3の場合は次の表のようになる。

表より、二つのキー値のハッシュ値が等しくなる条件はキー値の差(a-b)がnの倍数であるときということが分かる。

問題へ

問題8

再帰的に定義された手続きprocで、proc(5)を実行したとき、印字される数字を順番に並べたものはどれか。

　proc(n )
　　n = 0ならば戻る
　　そうでなければ
　　{
　　　　n を印字する
　　　　proc(n - 1)を呼び出す
　　　　n を印字する
　　}
　　を実行して戻る

ア	543212345
イ	5432112345
ウ	54321012345
エ	543210012345

解答：イ

＜解説＞

トレースすると次のようになる。

問題へ

問題9

未整列の配列a [i](i = 1, 2, …, n)を、流れ図で示すアルゴリズムによって昇順に整列する。
n = 6でa [1]～a [6]の値がそれぞれ、21、5、53、71、3、17の場合、流れ図において、a [j - 1]とa [j ]の値の入替えは何回行われるか。

ア	3
イ	6
ウ	8
エ	15

解答：ウ

＜解説＞

トレースすると次のようになる。

問題へ

問題10

メモリインタリーブの説明のうち、適切なものはどれか。

ア	新しい情報をキャッシュメモリに取り出すとき、キャッシュ上では不要になった情報を主記憶に書き込む。
イ	主記憶のアクセス時間と磁気ディスクのアクセス時間とのギャップを補う。
ウ	主記憶の更新と同時にキャッシュの更新を行う。
エ	主記憶を幾つかの区画に分割し、連続したメモリへのアクセスを高速化する。

解答：エ

＜解説＞

キャッシュメモリ (cache memory) は、CPUなど処理装置がデータや命令などの情報を取得/更新する際に主記憶装置やバスなどの遅延／低帯域を隠蔽化させ、処理装置と記憶装置の性能差を埋めるために用いる高速小容量メモリのことである。

ア	×	ライトバック方式のキャッシュメモリのリフレッシュ動作の説明である。
イ	×	ディスクキャッシュの説明である。
ウ	○	ライトスルー方式のキャッシュメモリの説明である。
エ	×	メモリインタリーブの説明である。

問題へ