平成23年秋期試験午後問題 問8

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】

問8 データ構造及びアルゴリズム

次のプログラムの説明及びプログラムを読んで,設問1,2に答えよ。

 1行の代入文を解析し,演算の優先順位に従って一つずつ演算を行っていく一連の代入文に変換して出力する。 代入文とその出力結果の例を,次に示す。ここで,出力結果にある wk#1 などは,中間結果を保存するための作業変数である。
pm08_1.gif
 代入文の形式は,次のとおりである。
   変数=式
 "="は代入演算子で,右辺の式の値を評価した結果を,左辺の変数に代入する。
 式は,変数又は定数(以下,項という)の一つ以上の並びで,項が二つ以上のときは各項の間に算術演算子を置く。変数は,英字("A"~"Z","a"~"z")で始まる1文字以上の英数字の列である。定数は,1文字以上の 数字("0"~"9")の列である。
 算術演算子は,加算("+"),減算("-"),乗算("*"),除算("/")の4種類である。乗除算は加減算に優先する。同一優先順位の算術演算子は,左から順に演算する。

〔代入文の構文解析〕
 解析処理は,次の手順による。
  • 代入文を走査して,英字・数字・代入演算子・算術演算子以外の文字が含まれていれば,errに-1を格納して手順(5)へ進む。errは,文法上の誤りがあった場合のエラーコードを格納する変数である。
  • n文字からなる代入文を,文字型配列Sの要素番号1~nに格納し,S[0]に開始マーク"《"を,S[n+1]に終端マーク"》"を,それぞれ格納する。次に,整数型配列 V を用意し,S[i]の内容に対応した表1のコードをV[i]に格納する。その例を,次に示す。
    pm08_2.gif
  • 初期値として st に"開始"を,err及びiに0を,それぞれ格納する。stは,解析の状態を格納している変数である。
  • iに1を加算する。表2で,現在のstの状態(行)と着目している文字S[i]の内容(列)が交差するセルの内容を実行する。ただし,セルが空白の場合は,何も実行しない。実行の結果,errの値が0以外となったら手順(5)へ,stの値が"終端"となったら手順(6)へそれぞれ進む。それ以外の場合は,この手順(4)を繰り返す。
    pm08_3.gif
  • errの値に応じて適切なエラーメッセージを表示し,処理を終了する。
  • 文法上の誤りがなかった旨を表示し,処理を終了する。

設問1

〔代入文の構文解析〕に関する次の記述中の に入れる正しい答えを,解答群の中から選べ。

 文法上の誤りがある次の代入文①~④を解析処理に手順によって解析した。
代入文①
Answer=One+Two+Three+
代入文②
HexaSum=7FFF+0001
代入文③
Position=Index++
代入文④
X1+10*X2=Ans
 解析処理手順(5)に進んだとき,aの場合はerrの値が51 に,bの場合はerrの値が64になっている。
a,b に関する解答群
  • 代入文①
  • 代入文②
  • 代入文③
  • 代入文④
解答選択欄
  • a:
  • b:
  • a=
  • b=

解説

この設問の解説はまだありません。
〔代入文の変換〕
 変換処理は,次の手順による。〔代入文の構文解析〕の手順は実行済みで,代入文には文法上の誤りがないものとする。
  • 初期値として,wに0を格納する。
  • 配列S,Vの開始マークから終端マークまでの範囲を検査し,優先順位が最も高い最初の算術演算子の要素番号を変数 next に格納する。その例を,次に示す。算術演算子がなければ,next に0を格納する。
    pm08_4.gif
  • nextが0なら,配列S中の代入文を出力して,処理を終了する。
  • nextの位置の演算子とその前後の項からなる文字列を抜き出す(図1の①)。wに1を加算し,出力する代入文を編集して出力する。出力する代入文は,文字列"wk#",文字列に変換した値 w,文字"=" 及び抜き出した文字列をこの順に連結したものである。次に,配列Sについて,抜き出した元の文字列を,文字列"wk#"及び文字列に変換した値 w で置き換える(図1の②)。置き換えるときに,文字数が増える場合は以降の文字を後ろにずらし,減る場合は以降の文字を前に詰める。さらに,更新された配列Sの内容に応じて配列Vの内容を更新する。文字"#"に対応するコードは,英字のコードと同じとする。
    pm08_5.gif
  • 手順(2)へ戻り,処理を繰り返す。

設問2

〔代入文の変換〕に関する次のプログラム中及び記述中の に入れる正しい答えを,解答群の中から選べ。
 なお,プログラム中の関数Getpos(配列,値)は,値が格納されている配列中の最初の要素番号を返す。また,配列S,Vは大域変数として与えられ,副プログラム中から参照できるものとする。
  • 手順(2)の処理を行う2種類の副プログラム1,2を作成した。
    pm08_6.gif
     プログラム1の α の行では,iに1を格納している。
     ここで,αの行を"i ← e"とすれば,繰返し処理の繰返し回数を最小にすることができる。
  • 手順(4)の処理中で使用する副プログラム3を作成した。このプログラムは,配列S,Vの 要素番号 from 以降(終端マークまで)の要素を前後に移動する。move は,移動する桁数と方向を示し,符号が正の場合は後ろにずらし,符号が負の場合は前に詰める。moveの値が-3(左に3桁詰める)の場合の例を,次に示す。ここで,配列S,Vは十分な大きさがあるものとする。
    pm08_7.gif
pm08_8.gif
c,d に関する解答群
  • priority < V[i]
  • priority ≦ V[i]
  • priority ≧ V[i]
  • priority > V[i]
e に関する解答群
  • Getpos(S[], "«") + 1
  • Getpos(S[], "«") + 2
  • Getpos(S[], "=") - 1
  • Getpos(S[], "=") + 2
f,g に関する解答群
  • from, i < to, 1
  • from, i ≦ to, 1
  • to, i ≧ from,-1
  • to, i > from,-1
解答選択欄
  • c:
  • d:
  • e:
  • f:
  • g:
  • c=
  • d=
  • e=
  • f=
  • g=

解説

この設問の解説はまだありません。

Pagetop