平成26年度春季解答

問題1

2進数で表現すると無限小数になる10進小数はどれか。

ア	0.375
イ	0.45
ウ	0.625
エ	0.75

解答：イ

＜解説＞

10進数の有限小数のうち、2進数に変換しても有限小数になるのは次の場合である。

• (1/2)ⁿという形式の数値：1/2=0.5,1/4=0.25,1/8=0.125
• (1/2)ⁿという形式の有限個の和：0.75=0.5+0.25=1/2+1/4

ア	×	0.375=0.25+0.125=1/4+1/8
イ	○	上記の形式で表現できない。したがって、無限小数となる。
ウ	×	0.625=0.5+0.125=1/2+1/8
エ	×	0.75=0.5+0.25=1/2+1/4

問題へ

問題2

三つのグラフA～Cの同形関係に関する記述のうち、適切なものはどれか。 ここで、二つのグラフが同形であるとは、一方のグラフの頂点を他方のグラフの頂点と1対1に漏れなく対応付けることができ、一方のグラフにおいて辺でつながれている頂点同士は他方のグラフにおいても辺でつながれていて、一方のグラフにおいて辺でつながれていない頂点同士は他方のグラフにおいても辺でつながれていないことをいう。

ア	AはCと同形であるが、Bとは同形でない。
イ	BはCと同形であるが、Aとは同形でない。
ウ	どの二つのグラフも同形である。
エ	どの二つのグラフも同形でない。

解答：ア

＜解説＞

解説省略

問題へ

問題3

次のBNFにおいて非終端記号<A>から生成される文字列はどれか。

<R₀>　：：= 0 | 3 | 6 | 9

<R₁>　：：= 1 | 4 | 7

<R₂>　：：= 2 | 5 | 8

<A>　：：= <R₀> | <A><R₀> | <B><R₂> | <C><R₁>

<B>　：：= <R₁> | <A><R₁> | <B><R₀> | <C><R₂>

<C>　：：= <R₂> | <A><R₂> | <B><R₁> | <C><R₀>

ア	123
イ	124
ウ	127
エ	128

解答：ア

＜解説＞

解説省略

問題へ

問題4

次の表は、入力記号の集合が{0, 1}、状態集合が{a, b, c, d}である有限オートマトンの状態遷移表である。 長さ3以上の任意のビット列を左(上位ビット)から順に読み込んで最後が110で終わっているものを受理するには、どの状態を受理状態とすればよいか。

ア	a
イ	b
ウ	c
エ	d

解答：ウ

＜解説＞

1. 110の左端の1を読み込む：状態がa又はcの時はb、bまたはdの時はdに遷移する
2. 110の中央の1を読み込む：状態がb又はdの時に1を読み込むとdに遷移する
3. 110の右端の0を読み込む：状態がdの時に0を読み込むとcに遷移する

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

問題へ

問題5

記憶領域を管理するアルゴリズムのうち、ベストフィット方式の特徴として、適切なものはどれか。

ア	空きブロック群のうち、アドレスが下位のブロックを高い頻度で使用するので、アドレスが上位の方に大きな空きブロックが残る傾向にある。
イ	空きブロック群のうち、要求された大きさを満たす最小のものを割り当てるので、最終的には小さな空きブロックが多数残る傾向にある。
ウ	空きブロックの検索にハッシュ関数を使用しているので、高速に検索することができる。
エ	空きブロックをアドレスの昇順に管理しているので、隣接する空きブロックを簡単に見つけられ、より大きな空きブロックにまとめることができる。

解答：イ

＜解説＞

記録管理アルゴリズムには次のものがある。

ベストフィット方式

空きブロック群を大きさ順に検索し、要求された大きさを満たす最小のブロックを割り当てる方式。
空きブロック群のうち、要求された大きさを満たす最小のものを割り当てるので、最終的には小さな空きブロックが多数残る傾向にある。

ファーストフィット方式

空きブロック群を大きさ順に検索し、要求された大きさを満たす最初のブロックを割り当てる方式。
アドレスが上位の方に大きな空きブロックが残る傾向にある。

ワーストフィット方式

空きブロック群を大きさ順に検索し、要求された大きさを満たす最大のブロックを割り当てる方式

 

ア	×	ファーストフィット方式の特徴である。
イ	○	ベストフィット方式の特徴である。
ウ	×	空きブロックにはデータが格納されていないので、ハッシュ関数やハッシュ値は使用できない。
エ	×	ベストフィット方式は、空きブロック群をまとめる際には用いない。

問題へ