平成17年春期基本情報技術者試験午後問9、アセンブラ言語
- 2016/11/21
- 14:55
本ページは平成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でシステム開発会社を探されている法人様はこちら）
***********************************************************************************************************
次のアセンブラプログラムの説明及びプログラムを読んで，設問１，２に答えよ。
〔プログラムの説明〕
ある商店の在庫状況を記録した在庫表から，商品番号をキーとして，商品の在庫量を２分探索法で検索する副プログラムBSEARCHである。
(1) 在庫表は，先頭に扱い商品数N，その後ろに商品番号とその商品の在庫量の対を商品番号順（昇順）に格納したものである。扱い商品数，商品番号，在庫量は，それぞれ0以上の整数値で１語に格納されている。
在庫表の様式
(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
設問１ プログラム中の{ }に入れる正しい答えを，解答群の中から選べ。
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
設問２ 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
********************************************************************************
解答
設問１ 答 aオ 答 bア 設問２ 答ウ
********************************************************************************
解説
2行目のRPUSHで、GRの内容をGR1,GR2,････GR7の順でスタックに格納する。
3行目で1をGR3にセットする。コメントの通りに初期値設定を行っている。
4行目でGR2の内容をGR4にセットする。
例えば、図１のように商品が５つあり、商品数Nが100番地に値が格納されているとする。
図１ 在庫表例
100 101 102 103 104 105 106 107 108 109 110
この場合に問題文よりGR2には、在庫表の先頭アドレスが入っているのでGR2には100がセットされている。
5行目で、GR2+(-1)番地のアドレスの値をGR2にセットする。図１の例ではGR2の値は99となる。
6行目で、GR0に-1をセットする。コメントにある通り、戻り値の初期設定を行っている。
7-8行目でGR3>GR4の時、EXITラベルに飛ぶ。初回の時は、GR3=1,でGR4=5となっているので、この条件には該当しない。
9・10・11行目ではコメントの通りLT,RTの中央の位置を計算している。これは参考文献で説明されているように2分探索法は、昇順および降順に並んでいる数列に対して、その中央の値との大小関係を比較することを順に確認しながら値を検索する手法だからである。
よって、2分探索法ではその中央値を計算することが必要になってくる。
10行目でGR5が１で、GR4は図１の例では５が格納されているから、結果、GR5の値は6となる。
{ a }
で、アの選択肢では、GR5に１を足すことになる。よって、図１の例では、結果が７となり、中央値は求まっていない。イの選択肢も同様である。
ウの選択肢はGR5を左に１シフトする。図１の例を8ビットで表現すると、6は
00000110
と表現される。これを１ビット左にシフトすると
00000011
となり、結果は３となる。よって、中央値が求まる。
同様にエ・オの選択肢を考えると、不適切なことがわかる。
2進数表現と10進数表現を比べると以下のようになる。
よって、22を左に１シフトすると21となり、値を半分にしたことになる。
13行目で論理右シフトすることによって、GR6の結果は6となり、右シフトしたことで数値を２倍にしたことがわかる。これは、アドレスを求める際に、項目は「商品番号」「在庫量」と２つの項目を使っているので、２倍をすることが必要である。
14行目で論理加算を行っているが、GR2には5行目より99が入っており、GR6は6が入っているから、結果99+6でGR6の値は105となる。図１より105番地には商品番号[3]が入っており、これで中央の値が取得できる。
15・16行目で、GR1の値とGR6の値が等しいかを確認している。等しい場合には、検索している商品番号がヒットしたことを示しているから、22行目に処理が移る。
22行目で、GR6+1のアドレスに入っている値をGR0にセットしてプログラムを終了している。GR6+1のアドレスに入っている値とは、図１では在庫量[3]の値を取得したことになる。
{ b }
15・16行目で、値が等しくない場合には、GR1の値>GR6の値であれば、値は中央値より後半に存在することになるから、左端標識LTに中央値をセットすればよい。また、GR1の値＜GR6の値であれば、値は中央値より前半に存在することになるから、右端標識RTに中央値をセットすればよい。
よって、解答はアとなる。
設問２
1回目のループの際、15行目でGR1には２がGR6には中央値に該当する商品番号である7がセットされている。GR1GR4の推移は次のようになる。
10行目で、GR5(1)+ GR4(8)→GR5(9)
1１行目で、GR5(9)→GR5(4)
20行目で、GR5(4)-1→GR4(3)
２回目のループでは、GR1には2がGR6には３がセットされる。よって、GR1GR4の推移は次のようになる。
10行目で、GR5(1)+ GR4(3)= GR5(4)
1１行目で、GR5(4)→GR5(2)
20行目で、GR5(2)-1→GR4(1)
３回目のループでは、GR1には2がGR6には１がセットされる。よって、GR1>GR6であるから20行目は実行されず18行目が実行される。GR3に２がセットされる。7行目に戻った処理で、GR3が２で、GR4が１であるから処理を抜けることになる。
GR4の推移は次のようになる。
10行目で、GR5(1)+ GR4(1)= GR5(2)
1１行目で、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でシステム開発会社を探されている法人様はこちら）
***********************************************************************************************************
無料から学べる講座
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でシステム開発会社を探されている法人様はこちら）
***********************************************************************************************************
次のアセンブラプログラムの説明及びプログラムを読んで，設問１，２に答えよ。
〔プログラムの説明〕
ある商店の在庫状況を記録した在庫表から，商品番号をキーとして，商品の在庫量を２分探索法で検索する副プログラムBSEARCHである。
(1) 在庫表は，先頭に扱い商品数N，その後ろに商品番号とその商品の在庫量の対を商品番号順（昇順）に格納したものである。扱い商品数，商品番号，在庫量は，それぞれ0以上の整数値で１語に格納されている。
在庫表の様式
| 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
設問１ プログラム中の{ }に入れる正しい答えを，解答群の中から選べ。
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
設問２ 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
********************************************************************************
解答
設問１ 答 aオ 答 bア 設問２ 答ウ
********************************************************************************
解説
2行目のRPUSHで、GRの内容をGR1,GR2,････GR7の順でスタックに格納する。
3行目で1をGR3にセットする。コメントの通りに初期値設定を行っている。
4行目でGR2の内容をGR4にセットする。
例えば、図１のように商品が５つあり、商品数Nが100番地に値が格納されているとする。
図１ 在庫表例
| 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にセットする。図１の例ではGR2の値は99となる。
6行目で、GR0に-1をセットする。コメントにある通り、戻り値の初期設定を行っている。
7-8行目でGR3>GR4の時、EXITラベルに飛ぶ。初回の時は、GR3=1,でGR4=5となっているので、この条件には該当しない。
9・10・11行目ではコメントの通りLT,RTの中央の位置を計算している。これは参考文献で説明されているように2分探索法は、昇順および降順に並んでいる数列に対して、その中央の値との大小関係を比較することを順に確認しながら値を検索する手法だからである。
よって、2分探索法ではその中央値を計算することが必要になってくる。
10行目でGR5が１で、GR4は図１の例では５が格納されているから、結果、GR5の値は6となる。
{ a }
で、アの選択肢では、GR5に１を足すことになる。よって、図１の例では、結果が７となり、中央値は求まっていない。イの選択肢も同様である。
ウの選択肢はGR5を左に１シフトする。図１の例を8ビットで表現すると、6は
00000110
と表現される。これを１ビット左にシフトすると
00000011
となり、結果は３となる。よって、中央値が求まる。
同様にエ・オの選択肢を考えると、不適切なことがわかる。
2進数表現と10進数表現を比べると以下のようになる。
| 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
よって、22を左に１シフトすると21となり、値を半分にしたことになる。
13行目で論理右シフトすることによって、GR6の結果は6となり、右シフトしたことで数値を２倍にしたことがわかる。これは、アドレスを求める際に、項目は「商品番号」「在庫量」と２つの項目を使っているので、２倍をすることが必要である。
14行目で論理加算を行っているが、GR2には5行目より99が入っており、GR6は6が入っているから、結果99+6でGR6の値は105となる。図１より105番地には商品番号[3]が入っており、これで中央の値が取得できる。
15・16行目で、GR1の値とGR6の値が等しいかを確認している。等しい場合には、検索している商品番号がヒットしたことを示しているから、22行目に処理が移る。
22行目で、GR6+1のアドレスに入っている値をGR0にセットしてプログラムを終了している。GR6+1のアドレスに入っている値とは、図１では在庫量[3]の値を取得したことになる。
{ b }
15・16行目で、値が等しくない場合には、GR1の値>GR6の値であれば、値は中央値より後半に存在することになるから、左端標識LTに中央値をセットすればよい。また、GR1の値＜GR6の値であれば、値は中央値より前半に存在することになるから、右端標識RTに中央値をセットすればよい。
よって、解答はアとなる。
設問２
1回目のループの際、15行目でGR1には２がGR6には中央値に該当する商品番号である7がセットされている。GR1
10行目で、GR5(1)+ GR4(8)→GR5(9)
1１行目で、GR5(9)→GR5(4)
20行目で、GR5(4)-1→GR4(3)
２回目のループでは、GR1には2がGR6には３がセットされる。よって、GR1
10行目で、GR5(1)+ GR4(3)= GR5(4)
1１行目で、GR5(4)→GR5(2)
20行目で、GR5(2)-1→GR4(1)
３回目のループでは、GR1には2がGR6には１がセットされる。よって、GR1>GR6であるから20行目は実行されず18行目が実行される。GR3に２がセットされる。7行目に戻った処理で、GR3が２で、GR4が１であるから処理を抜けることになる。
GR4の推移は次のようになる。
10行目で、GR5(1)+ GR4(1)= GR5(2)
1１行目で、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)
