基本情報技術者 2016年 秋期 午後 問12
次のアセンブラプログラムの説明及びプログラムを読んで、設問1～3に答えよ。
〔プログラム1の説明〕
リストに対して、要素を挿入又は削除する副プログラムLPROCである。リストの構造を図1に示す。
(1) リストは一つ以上の要素をもち、一つの要素は連続する2語から成る。1語目には次の要素の先頭アドレス（図中では矢印で表す）が、2語目にはその要素の保持する値が格納される。要素は主記憶の0番地以外に配置され、最後の要素の1語目には、次の要素がないことを表すために、0が設定される。
(2) ROOTは1語から成り、最初の要素（要素1）の先頭アドレスが格納される。
(3) 主プログラムは、表1に示す値を各レジスタに設定してLPROCを呼ぶ。
① nは操作対象とする要素が、リストの先頭から何番目かを指定する正の整数である。
② 要素の挿入の場合は、その要素が先頭からn番目となる位置（要素nの直前）に挿入される。削除の場合は、先頭からn番目の要素（要素n）が削除される。
③ nとして、リストの現在の要素の個数Nよりも大きい値が与えられたとき、LPROCは何もせずに呼出し元に戻る。
(4) LPROCは、要素を挿入又は削除するとき、それぞれ別に用意された副プログラムEGET又はEFREEを呼ぶ。
(5) EGETは、挿入される要素に必要な領域を記憶管理領域から割り当てるために呼び出され、新たに割り当てられた、連続する2語から成る領域の先頭アドレスをGR2に設定して呼出し元に返す。
(6) EFREEは、削除された要素の先頭アドレスをGR2に設定して呼び出され、当該要素が使用していた領域を記憶管理領域に戻す。
(7) 副プログラムEGETから戻るとき、GR2以外の汎用レジスタの内容は元に戻す。
(8) 副プログラムEFREEから戻るとき、汎用レジスタGR1～GR7の内容は元に戻す。
(9) 副プログラムLPROCから戻るとき、汎用レジスタGR1～GR7の内容は元に戻す。
設問1：
問題文を見る プログラム1中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：JMI FIN
イ：LAD GR1,1,GR1
ウ：LAD GR4,1,GR4
エ：LD GR1,GR2
オ：LD GR1,0,GR2
bに関する解答群
ア：LD GR4,0,GR1
イ：LD GR4,0,GR2
ウ：ST GR2,0,GR1
エ：ST GR2,0,GR2
オ：ST GR4,0,GR1
カ：ST GR4,0,GR2
cに関する解答群
ア：LD GR4,0,GR1
イ：LD GR4,0,GR2
ウ：LD GR4,2,GR1
エ：LD GR4,2,GR2
オ：LD GR4,GR1
カ：LD GR4,GR2
模範解答
a：エ、b：ウ、c：イ
解説
解答の導き方
まず、リストの中で各レジスタが何を指すのかを整理します。
リストの要素は連続する2語でできています。1語目は次の要素のアドレス、2語目は要素が持つ値です。アドレスは、主記憶のどこにデータがあるかを示す番号です。最後の要素の1語目には、次の要素がないことを示す0が入ります。
プログラムでは、GR1が「次の要素のアドレスを書き込む場所」を指し、GR2が「その場所に記録されている次の要素のアドレス」を持つように進みます。最初は、GR1がROOTを指し、GR2には要素1のアドレスが読み込まれます。
-
aでは、リストを次の要素へ進めます。3行目で、操作する位置がGR4に保存されます。ループ内では、4行目でGR1が指す場所から次の要素のアドレスを読み込み、GR2に入れます。6行目ではGR4を1減らし、7行目で0になったかを確認します。0なら、GR2が指定された要素を指しているので、処理を進めます。まだ0でなければ、次の要素を調べる必要があります。そのため、GR2に入っている現在の要素のアドレスをGR1に移します。次のループでは、その要素の1語目から、さらに次の要素のアドレスを読み込めます。よって、aには LD GR1,GR2 が入り、解答群ではエです。なお、GR2が0なら、リストの末尾まで進んでも指定された位置に届いていません。5行目のJZE FINで処理を終えるので、の場合はリストを変更しません。
-
aの後、GR1とGR2が指す場所を確認します。目的の位置に達した時点で、GR1は「目的の要素のアドレスを書き込む場所」を指し、GR2は「目的の要素」を指しています。たとえば先頭の要素が対象なら、GR1はROOTを指します。2番目の要素が対象なら、GR1は要素1を指します。この形なら、先頭への挿入や先頭要素の削除も、特別な場合分けをせずに処理できます。
-
bでは、新しい要素をリストにつなぎます。12行目で、GR2が指している要素のアドレスをGR4に保存しています。ここで保存するのは、挿入位置にあった元の要素のアドレスです。13行目のEGETは、新しい要素の領域を用意し、その先頭アドレスをGR2に返します。つまり、EGETの後は、GR2が新しい要素を指し、GR4が挿入位置にあった元の要素を指します。新しい要素をリストにつなぐには、まずGR1が指す場所に新しい要素のアドレスを書き込みます。該当する命令は ST GR2,0,GR1 なので、bは解答群のウです。続く15行目で、GR4に保存しておいた元の要素のアドレスを新しい要素の1語目に書き込みます。これで、新しい要素の次に元の要素が続きます。16行目ではGR0にある挿入する値を、新しい要素の2語目に書き込みます。つまり、挿入時のつながりは「それまでの前の場所 → 新しい要素 → 元の目的位置の要素」となります。
-
cでは、削除する要素を飛び越すようにつなぎ直します。削除時も、GR1は削除対象のアドレスを書き込む場所を指し、GR2は削除対象の要素を指しています。削除後に前の場所からつなぐべきなのは、削除対象の次の要素です。そのアドレスは、削除対象の1語目に入っています。したがって、GR2が指す場所から1語目を読み込み、GR4に保存する LD GR4,0,GR2 が必要です。よって、cは解答群のイです。19行目で、GR4に保存した次の要素のアドレスを、GR1が指す場所に書き込みます。これで削除対象を飛び越して、前の要素から次の要素へつながります。20行目のEFREEには、削除対象のアドレスが入ったGR2を渡し、使い終わった領域を解放します。
誤りやすいポイント
- GR1とGR2の役割を逆にしないようにします。GR1は「アドレスを書き込む場所」、GR2は「その場所にある要素のアドレス」です。
- aでGR1を次の要素のアドレスに更新するのではありません。GR1には現在の要素のアドレスを入れ、次のループでその要素の1語目を読み込みます。
- EGETの後は、GR2が新しい要素のアドレスに変わります。そのため、挿入位置にあった元の要素のアドレスを、EGETの前にGR4へ保存しておく必要があります。
- 削除対象のアドレスと、削除対象の次の要素のアドレスは別です。削除対象のアドレスはGR2、次の要素のアドレスは削除対象の1語目から読み込んだGR4です。
- 最後の要素を削除する場合、次の要素のアドレスは0です。GR4の0を前の場所に書き込めば、リストの終端を正しく設定できます。
FAQ
Q: なぜ挿入と削除の両方で、GR1が「アドレスを書き込む場所」を指すのですか？
A: その場所を書き換えるだけで、要素をつないだり、削除対象を飛び越したりできるからです。先頭の要素を扱うときはROOTがその場所になります。
Q: GR4は何のために使っていますか？
A: 挿入では、EGETによってGR2の内容が新しい要素のアドレスに変わるため、元の要素のアドレスをGR4に残します。削除では、削除対象の次の要素のアドレスをGR4に残し、前の場所につなぎ直します。
Q: のとき、なぜリストを変更せずに戻れるのですか？
A: 次の要素がないことを示す0をGR2に読み込むと、5行目のJZE FINで処理が終わるためです。挿入や削除の処理には進みません。
関連キーワード: 連結リスト、ポインタ、アドレス、レジスタ、サブルーチン
設問2：
問題文を見る 図2に示す要素数が3個のリストについて、n=3でLPROCを実行し、要素を挿入する。行番号12のラベルLINSの命令を実行するときGR2に格納されている値として、正しい答えを、解答群の中から選べ。
解答群
ア：挿入する要素の先頭アドレス
イ：要素2の先頭アドレス
ウ：要素3の先頭アドレス
エ：0
模範解答
ウ
解説
解答の導き方
この問題では、要素を挿入する処理に入る時点で、GR2がどの要素の先頭アドレスを持っているかを追います。アドレスは、主記憶上の場所を示す番号です。
リストの各要素は、次の要素の先頭アドレスと値の2語でできています。ROOTには要素1の先頭アドレスが入っています。
また、挿入位置について本文には「先頭からn番目となる位置（要素nの直前）」とあります。したがって、n=3で挿入する場合は、既存の要素3の直前に新しい要素を入れます。
行4では、GR1が指す場所に格納された次の要素の先頭アドレスをGR2に読み込みます。行6では、調べた要素の分だけGR4を1減らし、行7ではGR4が0になったかを判定します。処理を順に追うと、次のようになります。
3回目にGR4が0になるので、行7からNEXTへ進みます。GR3は挿入時に0なので、行10の分岐先はLINSです。このとき、GR2には要素3の先頭アドレスが入っています。
なお、挿入用の領域を割り当てるEGETが呼ばれるのは、LINSに入った後の行13です。したがって、LINSに入った時点のGR2は、まだ新しく割り当てられた領域のアドレスではありません。
よって、正しい選択肢はウです。
誤りやすいポイント
- n=3を「要素3の後ろに挿入する」と考えないようにしましょう。本文では「要素nの直前」と説明されています。
- EGETがGR2を新しい領域の先頭アドレスにするのは、行13を実行した後です。LINSに入った時点では、GR2はリストをたどって見つけた要素のアドレスです。
- GR4は、調べた要素の数を数えるために使われています。3回目にGR4が0になったことで、要素3に到達したと分かります。
FAQ
Q: なぜGR2は要素3の先頭アドレスになるのですか？
A: ROOTからたどると、1回目に要素1、2回目に要素2、3回目に要素3のアドレスが読み込まれるためです。
A: ROOTからたどると、1回目に要素1、2回目に要素2、3回目に要素3のアドレスが読み込まれるためです。
Q: GR2が新しく挿入する要素のアドレスになるのはいつですか？
A: LINSに入った後、行13でEGETを呼び出したときです。EGETは、割り当てた領域の先頭アドレスをGR2に設定します。
A: LINSに入った後、行13でEGETを呼び出したときです。EGETは、割り当てた領域の先頭アドレスをGR2に設定します。
Q: GR2が0になるのはどのようなときですか？
A: 次の要素がないときです。この問題では要素数が3個あり、n=3なので、要素3に到達した時点で挿入処理に進みます。要素3の次を調べるところまでは進みません。
A: 次の要素がないときです。この問題では要素数が3個あり、n=3なので、要素3に到達した時点で挿入処理に進みます。要素3の次を調べるところまでは進みません。
関連キーワード: 連結リスト、アドレス、ポインタ、レジスタ、リストの挿入
設問3：
問題文を見る ラベルLIST以降に格納されている要素数が4個のリストについて、プログラム2のMAINを実行した。実行後のラベルE3で示される番地の内容として、正しい答えを、解答群の中から選べ。ここで、EGETで割り当てられた要素の先頭アドレスは、割り当てられた順に、、とする。
解答群
ア：α1
イ：α2
ウ：E1
エ：E2
オ：0
模範解答
ア
解説
解答の導き方
まず、リストは要素の並びを、各要素の先頭にある「次の要素のアドレス」でたどります。アドレスは、主記憶上の場所を示す番号です。したがって、ラベルが並んでいる順ではなく、各要素の先頭に格納されたアドレスを見て、リストの順番を判断します。
プログラム2では、ROOTにはLISTが格納されています。LISTの先頭にはE3、E3の先頭にはE1、E1の先頭にはE2、E2の先頭には0が格納されています。最後の0は、次の要素がないことを表します。よって、実行前のリストの順番は次のとおりです。
次に、MAINの3回のLPROC呼出しを順に追います。nはGR2で指定され、挿入では「先頭からn番目となる位置」に要素が入ります。削除では「先頭からn番目の要素」が取り除かれます。
1回目：値1の挿入
MAINはGR0に1、GR2に3、GR3に0を設定してLPROCを呼び出します。GR3が0なので挿入です。nは3ですから、現在の3番目の要素であるE1の直前に挿入します。
EGETが割り当てる要素の先頭アドレスは、割り当て順に、です。したがって、この回に割り当てられるアドレスはです。
挿入後の順番は次のとおりです。
この時点で、E3の先頭にある「次の要素のアドレス」はです。
2回目：値2の挿入
MAINはGR0を2に設定して、もう一度LPROCを呼び出します。このときGR2は設定し直されていないため、nは3のままです。これは、LPROCから戻るときにGR1～GR7の内容が元に戻るためです。
2回目も挿入なので、現在の3番目の要素であるの直前に要素が入ります。割り当てられるアドレスは2番目のです。
この時点では、E3の次の要素はです。
3回目：3番目の要素の削除
MAINはGR3に1を設定してLPROCを呼び出します。GR3が1なので削除です。GR2は引き続き3のままなので、3番目の要素であるが削除されます。
削除後は、の次にあったが、E3の次の要素になります。したがって、E3の先頭にあるアドレスはです。
問題が尋ねているのは、ラベルE3で示される番地の内容です。E3は要素の先頭を示すラベルなので、その番地には次の要素のアドレスが格納されています。よって、実行後の内容はです。
誤りやすいポイント
-
ラベルの並びをリストの順番だと考える
LIST、E1、E2、E3の順にデータが書かれていますが、リストの順番は先頭に格納されたアドレスをたどって判断します。実行前の順番はLIST、E3、E1、E2です。 -
挿入位置を「n番目の要素の後」と考える
問題文では、挿入する要素が先頭からn番目となる位置、つまり元のn番目の要素の直前に挿入されます。 -
2回目以降のnを別の値だと考える
MAINは最初にGR2へ3を設定し、その後は設定し直していません。LPROCはGR1～GR7を元に戻すため、後の呼出しでもnは3です。 -
削除した要素の次の要素まで削除されたと考える
削除されるのは3番目の要素だけです。その次のは残り、E3からたどれるようにつなぎ直されます。
FAQ
Q: なぜE3の内容は、最初に格納されていたE1のままではないのですか？
A: 挿入や削除のたびに、つながりを保つために要素の先頭にあるアドレスを書き換えます。1回目の挿入でE3の次はになり、2回目の挿入でになります。最後にが削除されると、次の要素であるへつなぎ直されます。
A: 挿入や削除のたびに、つながりを保つために要素の先頭にあるアドレスを書き換えます。1回目の挿入でE3の次はになり、2回目の挿入でになります。最後にが削除されると、次の要素であるへつなぎ直されます。
Q: 2回目と3回目の呼出しでも、GR2が3のままなのはなぜですか？
A: LPROCから戻るとき、GR1～GR7の内容は元に戻ります。GR2もこの範囲に含まれるため、MAINが変更しない限り3のままです。
A: LPROCから戻るとき、GR1～GR7の内容は元に戻ります。GR2もこの範囲に含まれるため、MAINが変更しない限り3のままです。
Q: やは、要素に格納される値ですか？
A: いいえ。これらはEGETが割り当てた領域の先頭アドレスです。要素の値と、要素が置かれている場所を示すアドレスは別のものです。
A: いいえ。これらはEGETが割り当てた領域の先頭アドレスです。要素の値と、要素が置かれている場所を示すアドレスは別のものです。
関連キーワード: 連結リスト、ポインタ、アドレス、レジスタ、メモリ管理
