平成18年度秋季問題

問題11

図で表される有限オートマトンで受理される文字列はどれか。ここで，は初期状態を，は受理状態を表す。

ア	01011
イ	01111
ウ	10111
エ	11110

解答・解説へ

問題12

四則演算の式の書き方には，演算子をオペランドの前に書く方法（前置記法），オペランドの間に書く方法（中置記法），オペランドの後に書く方法（後置記法）の3通りがある。図は，2分木で表現された式のたどり方と，各記法によって表される式を例示したものである。

各記法で式を書く手順の説明として，適切なものはどれか。

ア	前置記法：節から上に戻るときにそこの記号を書く。
イ	中置記法：節に下りたときにそこの記号を書く。
ウ	後置記法：節から上に戻るときにそこの記号を書く。
エ	後置記法：葉ならばそこの記号を書いて戻る。演算子ならば下りるときに左括弧を書き，左の枝から右の枝に移るときに記号を書き，上に戻るときに右括弧を書く。

解答・解説へ

問題13

表は，配列を用いた連結セルによるリストの内部表現であり，リスト［東京，品川，名古屋，新大阪］を表している。このリストを［東京，新横浜，名古屋，新大阪］に変化させる操作はどれか。ここで，A( i ， j ) は表の第 i 行第 j 列の要素を表す。例えば，A(3，1) ＝“名古屋”であり，A(3，2) ＝ 4である。また，→ は代入を表す。

解答・解説へ

問題14

昇順に整列されたn個のデータが配列に格納されている。探索したい値を2分探索法で探索するときの、おおよその比較回数を求める式はどれか。

ア	log2n
イ	(log2n+1)/2
ウ	n
エ	n2

解答・解説へ

問題15

次の規則に従って配列の要素A［0］、A［1］、・・・・、A［9］に正の整数Kを格納する。16、43、73、24、85を順に格納したとき、85が格納される場所はどれか。ここで、X mod YはXをYで割った剰余を返す。また、配列の要素はすべて0に初期化されている。
[規則]
(1)　A［K mod 10]＝0ならば、K→A［K mod 10]とする。
(2) (1) で格納できないとき、A[ (K＋1) mod 10]＝0ならば、K→A［ (K＋1) mod 10]とする。
(3) (2) で格納できないとき、A［ (K＋4) mod 10]＝0ならば、K→A［ (K＋4) mod 10]とする。

ア	A［3］
イ	A［5］
ウ	A［6］
エ	A［9］

解答・解説へ