平成17年春期基本情報技術者試験午後問9、アセンブラ言語
- 2016/11/21
- 14:55
問題文、解答、解説の順で掲載しております。
無料から学べる講座
http://ai-light.com/itkeiei/
ニコニコチャンネル
http://ch.nicovideo.jp/ai-light
YouTubeチャンネル
https://www.youtube.com/user/ailightcom
Access・Excel倶楽部
http://ai-light.com/accessclub/
株式会社アイライト公式HP
http://www.ai-light.com/
(Access・Excelでシステム開発会社を探されている法人様はこちら)
***********************************************************************************************************
次のアセンブラプログラムの説明及びプログラムを読んで,設問1,2に答えよ。
〔プログラムの説明〕
ある商店の在庫状況を記録した在庫表から,商品番号をキーとして,商品の在庫量を2分探索法で検索する副プログラムBSEARCHである。
(1) 在庫表は,先頭に扱い商品数N,その後ろに商品番号とその商品の在庫量の対を商品番号順(昇順)に格納したものである。扱い商品数,商品番号,在庫量は,それぞれ0以上の整数値で1語に格納されている。
在庫表の様式
N | 商品番号[1] | 在庫量[1] | 商品番号[2] | 在庫量[2] | … | 商品番号[N] | 在庫量[N] |
(2) 主プログラムは,商品番号(検索キー)をGR1に,在庫表の先頭アドレスをGR2に設定し,BSEARCHを呼ぶ。
(3) BSEARCHは,検索キーに対応する在庫量をGR0に設定し,主プログラムに戻る。該当する商品番号が在庫表に存在しない場合は,-1をGR0に設定し,主プログラムに戻る。
(4) 副プログラムから戻るとき,汎用レジスタGR1~GR7の内容は元に戻す。
〔プログラム〕
(行番号)
1 BSEARCH START
2 RPUSH
3 LAD GR3,1 ; 左端標識 LT の初期設定
4 LD GR4,0,GR2 ; 右端標識 RT の初期設定
5 LAD GR2,-1,GR2 ; 表の基底アドレス
6 LAD GR0,-1 ; 戻り値の初期設定
7 SLOOP CPL GR3,GR4 ; LT > RT ?
8 JPL EXIT
9 LD GR5,GR3 ; LT,RTの中央の位置 MID の計算
10 ADDL GR5,GR4 ; ”
11 { a } ; ”
12 LD GR6,GR5 ; 商品番号 [MID] のアドレス計算
13 SLL GR6,1 ; ”
14 ADDL GR6,GR2 ; ”
15 CPL GR1,0,GR6 ; KEY = 商品番号[MID] ?
16 JZE FIND
17 { b }
18 LAD GR3,1,GR5 ; MID+1 → LT
19 JUMP SLOOP
20 RTSET LAD GR4,-1,GR5 ; MID-1 → RT
21 JUMP SLOOP
22 FIND LD GR0,1,GR6
23 EXIT RPOP
24 RET
25 END
設問1 プログラム中の{ }に入れる正しい答えを,解答群の中から選べ。
a に関する解答群
ア LAD GR5,1,GR5 イ LAD GR5,2,GR5 ウ SLL GR5,1
エ SLL GR5,2 オ SRL GR5,1
b に関する解答群
ア JMI RTSET イ JMI SLOOP ウ JPL RTSET
エ JPL SLOOP オ LAD GR2,1,GR2 カ LD GR5,GR6
設問2 GR1とGR2を次のように設定して副プログラムBSEARCHを呼び出したとき,行番号20の命令は何回実行されるか,正しい答えを,解答群の中から選べ。

解答群
ア 0 イ 1 ウ 2 エ 3 オ 4
カ 7 キ 8
***********************************************************************************************************
無料から学べる講座
http://ai-light.com/itkeiei/
ニコニコチャンネル
http://ch.nicovideo.jp/ai-light
YouTubeチャンネル
https://www.youtube.com/user/ailightcom
Access・Excel倶楽部
http://ai-light.com/accessclub/
株式会社アイライト公式HP
http://www.ai-light.com/
(Access・Excelでシステム開発会社を探されている法人様はこちら)
***********************************************************************************************************
2分探査法
http://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2
********************************************************************************
解答
設問1 答 aオ 答 bア 設問2 答ウ
********************************************************************************
解説
2行目のRPUSHで、GRの内容をGR1,GR2,・・・・GR7の順でスタックに格納する。
3行目で1をGR3にセットする。コメントの通りに初期値設定を行っている。
4行目でGR2の内容をGR4にセットする。
例えば、図1のように商品が5つあり、商品数Nが100番地に値が格納されているとする。
図1 在庫表例
5 | 商品番号[1] | 在庫量[1] | 商品番号[2] | 在庫量[2] | 商品番号[3] | 在庫量[3] | 商品番号[4] | 在庫量[4] | 商品番号[5] | 在庫量[5] |
100 101 102 103 104 105 106 107 108 109 110
この場合に問題文よりGR2には、在庫表の先頭アドレスが入っているのでGR2には100がセットされている。
5行目で、GR2+(-1)番地のアドレスの値をGR2にセットする。図1の例ではGR2の値は99となる。
6行目で、GR0に-1をセットする。コメントにある通り、戻り値の初期設定を行っている。
7-8行目でGR3>GR4の時、EXITラベルに飛ぶ。初回の時は、GR3=1,でGR4=5となっているので、この条件には該当しない。
9・10・11行目ではコメントの通りLT,RTの中央の位置を計算している。これは参考文献で説明されているように2分探索法は、昇順および降順に並んでいる数列に対して、その中央の値との大小関係を比較することを順に確認しながら値を検索する手法だからである。
よって、2分探索法ではその中央値を計算することが必要になってくる。
10行目でGR5が1で、GR4は図1の例では5が格納されているから、結果、GR5の値は6となる。
{ a }
で、アの選択肢では、GR5に1を足すことになる。よって、図1の例では、結果が7となり、中央値は求まっていない。イの選択肢も同様である。
ウの選択肢はGR5を左に1シフトする。図1の例を8ビットで表現すると、6は
00000110
と表現される。これを1ビット左にシフトすると
00000011
となり、結果は3となる。よって、中央値が求まる。
同様にエ・オの選択肢を考えると、不適切なことがわかる。
2進数表現と10進数表現を比べると以下のようになる。
27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 |
0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
よって、22を左に1シフトすると21となり、値を半分にしたことになる。
13行目で論理右シフトすることによって、GR6の結果は6となり、右シフトしたことで数値を2倍にしたことがわかる。これは、アドレスを求める際に、項目は「商品番号」「在庫量」と2つの項目を使っているので、2倍をすることが必要である。
14行目で論理加算を行っているが、GR2には5行目より99が入っており、GR6は6が入っているから、結果99+6でGR6の値は105となる。図1より105番地には商品番号[3]が入っており、これで中央の値が取得できる。
15・16行目で、GR1の値とGR6の値が等しいかを確認している。等しい場合には、検索している商品番号がヒットしたことを示しているから、22行目に処理が移る。
22行目で、GR6+1のアドレスに入っている値をGR0にセットしてプログラムを終了している。GR6+1のアドレスに入っている値とは、図1では在庫量[3]の値を取得したことになる。
{ b }
15・16行目で、値が等しくない場合には、GR1の値>GR6の値であれば、値は中央値より後半に存在することになるから、左端標識LTに中央値をセットすればよい。また、GR1の値<GR6の値であれば、値は中央値より前半に存在することになるから、右端標識RTに中央値をセットすればよい。
よって、解答はアとなる。
設問2
1回目のループの際、15行目でGR1には2がGR6には中央値に該当する商品番号である7がセットされている。GR1
10行目で、GR5(1)+ GR4(8)→GR5(9)
11行目で、GR5(9)→GR5(4)
20行目で、GR5(4)-1→GR4(3)
2回目のループでは、GR1には2がGR6には3がセットされる。よって、GR1
10行目で、GR5(1)+ GR4(3)= GR5(4)
11行目で、GR5(4)→GR5(2)
20行目で、GR5(2)-1→GR4(1)
3回目のループでは、GR1には2がGR6には1がセットされる。よって、GR1>GR6であるから20行目は実行されず18行目が実行される。GR3に2がセットされる。7行目に戻った処理で、GR3が2で、GR4が1であるから処理を抜けることになる。
GR4の推移は次のようになる。
10行目で、GR5(1)+ GR4(1)= GR5(2)
11行目で、GR5(2)→GR5(1)
20行目で、GR5(1)-1→GR3(2)
よって、解答はウとなる。
参考:平成17年春期基本情報技術者試験午後問9
***********************************************************************************************************
無料から学べる講座
http://ai-light.com/itkeiei/
ニコニコチャンネル
http://ch.nicovideo.jp/ai-light
YouTubeチャンネル
https://www.youtube.com/user/ailightcom
Access・Excel倶楽部
http://ai-light.com/accessclub/
株式会社アイライト公式HP
http://www.ai-light.com/
(Access・Excelでシステム開発会社を探されている法人様はこちら)
***********************************************************************************************************
- 関連記事
-
- 平成19年春期基本情報技術者試験午後問9、アセンブラ言語 (2016/12/09)
- 平成17年春期基本情報技術者試験午後問9、アセンブラ言語 (2016/11/21)