平成24年度春季解答

問題6

A,B,Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、データの出力順序は何通りあるか。

ア	3
イ	4
ウ	5
エ	6

解答：ウ

＜解説＞

スタックとは、ある場所に格納したデータを、新しく格納した順に取り出すようにする方式。一番古く格納されたデータが一番最後に取り出される、LIFO（Last In, First Out：後入れ先出し）型のバッファのことである。

出力順序を考えると次の6つの組み合わせがある。

○	A→B→C	AをPush→AをPop→BをPusu→BをPop→CをPop→CをPop
○	A→C→B	AをPush→AをPop→BをPusu→CをPush→CをPop→BをPop
○	B→A→C	AをPush→BをPush→BをPop→AをPop→CをPush→CをPop
○	B→C→A	AをPush→BをPush→BをPop→CをPush→CをPop→AをPop
×	C→A→B	AをPush→BをPush→CをPusu→CをPop ※Bを取出さずにその下のAを取り出すことができない。
○	C→B→A	AをPush→BをPush→CをPusu→CをPop→BをPop→AをPop

よって、C→A→Bを除く5通りの出力が存在する。

問題へ

問題7

次の手順はシェルソートによる整列を示している。データ列7,2,8,3,1,9,4,5,6を手順(1)～(4)に従って整列するとき、手順(3)を何回繰り返して完了するか。ここで、[ ]は、小数点以下を切り捨てた結果を表す。
[手順]
(1) [データ数÷3]→Hとする。
(2) データ列を、互いにH要素分だけ離れた要素の集まりからなる部分列とし、それぞれの部分列を、挿入法を用いて整列する。
(3) [H÷3]→Hとする。
(4) Hが0であればデータ列の整列は完了し、0でなければ(2)に戻る。

ア	2
イ	3
ウ	4
エ	5

解答：ア

＜解説＞

[手順]に沿って、シュミレートする。

	(1)	データの個数は9である。[9÷3]=3であり、H=3となる
	(2)	データ列を部分列とみなし、それぞれ整列する(整列過程は手順(3)の実行回数には影響しない)
	(3)	H=[H÷3}=[3÷3]=1となる
	(4)	H≠0なので(2)へ戻る
	(2)	データ列を部分列とみなし、それぞれ整列する
	(3)	H=[H÷3}=[1÷3]=0(小数点以下切捨て)となる
	(4)	H=0なので処理を終了する。

処理を終了するまでに、(3)の処理は2回ある。したがって、アが正解である。

問題へ

問題8

関数gcd(m、n)が次のように定義されている。m=135、n=35のとき、gcd(m、n)は何回呼ばれるか。ここで、最初のgcd(135,35)の呼び出しも、1回に数えるものとする。また、m、n(m>n≧0)は整数とし、m mod nはmをnで割った余りを返すものとする。

ア	2
イ	3
ウ	4
エ	5

解答：ウ

＜解説＞

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

1. gcd(135, 35) //n>0
2. gcd(35, 135 mod 35) //n=30
3. gcd(30, 35 mod 30) //n=5
4. gcd(5, 30 mod 5)＝30 //n=0

4回の呼び出しで最大公約数である5を得られることがわかります

問題へ

問題9

相異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータの存在するブロックを探し出す。次に、当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで、mは十分に大きくnはmの倍数とし、目的のデータは必ず表の中に存在するものとする。

解答：イ

＜解説＞

各ブロックを表中の1つの要素とすれば、表にはm/m個の要素がある。

これを順次検索する場合、目的のブロックが見つかるまでには最短で1回，最長でn/m回の系ン作が必要になる。平均すると(n/m+1)÷2≒n/2mである。

このブロック内を順次探索するので平均m/2解の検索で当該ブロック中に存在する検索値が発見できる。

よってイが正解である。

問題へ

問題10

キャッシュメモリにおけるダイレクトマップ方式の説明として、適切なものはどれか。

ア	アドレスが連続した二つ以上のメモリブロックを格納するセクタを、キャッシュ内の任意のロケーションに割り当てる。
イ	一つのメモリブロックをキャッシュ内の単一のロケーションに割り当てる。
ウ	メモリブロックをキャッシュ内の任意のロケーションに割り当てる。
エ	メモリブロックをキャッシュ内の二つ以上の配置可能なロケーションに割り当てる。

解答：イ

＜解説＞

キャッシュメモリ内のブロックと主記憶との対応付けには以下の方式がある。

フルアソシアティブ方式

主記憶上のどのブロックも、キャッシュメモリの任意のブロックに対応付ける方式である。

ダイレクトマッピング方式

アドレスなどを用いて主記憶のあるブロックをキャッシュメモリの特定の1つのブロックに対応付ける方式である。

セットアソシアティブ方式

主記憶のあるブロックをキャッシュメモリの複数の特定のブロックに対応付ける方式である。

ア	×	フルアソシアティブ方式の説明である。
イ	○	ダイレクトマップ方式の説明である。
ウ	×	フルアソシアティブ方式の説明である。
エ	×	セットアソシアティブ方式の説明である。

問題へ