平成23年度秋季解答

問題6

ヒープソートの説明として、適切なものはどれか。

ア	ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し、更に間隔を詰めて同様の操作を行い、間隔が１になるまでこれを繰り返す。
イ	中間的な基準値を決めて、それよりも大きな値を集めた区分と、小さな値を集めた区分に要素を振り分ける。次に、それぞれの区分の中で同様な処理を繰り返す。
ウ	隣り合う要素を比較して、大小の順が逆であれば、それらの要素を入れ替えるという操作を繰り返す。
エ	未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して、未整列の部分を縮めていく。

解答：エ

＜解説＞

ヒープソートでは、未整列の部分を順序木に構成し、そこから最大値又は最小値を取り出して既整列の部分に移す。これらの操作を繰り返して、未整列部分を縮めていく整列アルゴリズムである。

ア	×	シェルソートの説明である。
イ	×	クイックソートの説明である。
ウ	×	バブルソートの説明である。
エ	○	ヒープソートの説明である。

問題へ

問題7

n個の正の整数x₁,x₂,…,x_n が並んだ線形リストを[x₁,x₂,…,X_n]で表し，空リストは[ ]で表す。次のように再帰的に定義される関数func(L)を，L=[1,3,2]を実引数として呼び出したとき， print文によって表示される数字はどれか。ここで，プログラム中の=は等号，:=は代入を表す。

	〔関数の定義〕
	(1)	first([x1,x2,…,xn])はx1を返す。
	(2)	butfirst([x1,x2,…,xn])は[x2,…,xn]を返す。butfirst([x])は[ ]を返す。
	(3)	max(x,y)は，X≧yであればxを返し，そうでなければyを返す。

ア	123
イ	133
ウ	223
エ	233

解答：エ

＜解説＞

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

print文は3回実行され、「233」を出力する。

したがって、エが正解である。

問題へ

問題8

データが昇順にソートされた配列X[i](i=0,1,・・・,n-1)を2分探索する。流れ図のaに入るものとして、適切なものはどれか。ここで、流れ図の中の割り算は小数点以下を切り捨てるものとする。

ア	left < right
イ	left ≦ right
ウ	left+1 < right
エ	left+1 ≦ right

解答：イ

＜解説＞

ループ１の繰り返し条件は、

• 探索値が見つからない間(sch=-1)、ループを繰り返す。
• 探索の対象となるデータがある間(left<rightまたはleft=right)、ループを繰り返す。

である。

よって、イが正解である。

問題へ

問題9

CPUのパイプライン処理を有効に機能させるプログラミング方法はどれか。

ア	CASE文を多くする。
イ	関数の個数をできるだけ多くする。
ウ	分岐命令を少なくする。
エ	メモリアクセス命令を少なくする。

解答：ウ

＜解説＞

パイプラインは，1つの命令の実行サイクルを複数のステージに分割し，各段階の処理を別々の装置が担当することによって，各命令のステージを重ねて，並列実行することにより 1命令あたりの実行効率を上げる方式である。

ア	×	CASE文を多くすることは、分岐命令が増えることと同じである。よってパイプライン処理の効率は悪くなる。
イ	×	関数の個数を多くすると、関数の戻り値によって次の処理が変わる可能性が増えるのでパイプライン処理の効率は悪くなる。
ウ	○	分岐命令がある場合、結果によって次に実行するべき命令がわからないため、パイプラインを止めて次に実行すべき命令が判明するのを待たなければならない。すなわち分岐命令を少なくすることでパイプラインハザードが減りパイプライン処理が有効に機能しやすくなる。
エ	×	メモリアクセス命令はCPUの内部処理ではないので並行実行しやすい。したがってメモリアクセス命令を減らせばCPUの内部処理が増えるためパイプライン処理の効率は悪くなる。

問題へ

問題10

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

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

解答：エ

＜解説＞

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

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

問題へ