IT分野の担当教員の山口あかねです。
でも、実は帰ってきたブログのおねーさまです。またばりばり情報処理試験のCASLの解説を書きたいと思います。
IT分野では、私たちの生活の身近なところで日々使われているコンピュータシステムやＷｅｂアプリケーションを設計し、開発する勉強を日々行っています。卒業生はシステムエンジニアやＷｅｂエンジニアなどとして就職をしています。もちろん国家資格の取得にも力を入れているので資格を取りたい人には最適な分野です。
「平成２８年秋 基本情報 午後問１２」ばりばり解説！
ではさっそく、平成２８年秋基本情報午後問１２の解説です。簡単なリスト処理のプログラム問題です。
リスト処理のアルゴリズムがしっかりわかっていて、図が的確に描ければ簡単に解くことができる問題です。
解き方
まずプログラムの説明をざっと読みます。図１にリストの構造が描かれているので「リスト処理の問題かな？」と推測できます。リスト処理の問題は初歩的なものであればデータの検索、挿入、削除の操作をすることが問題になります。
表１に操作が書かれていて、挿入と削除とあるのでこの２つの操作をするプログラムが出題されていることがこの段階で理解できます。２つの操作はGR3のレジスタの値が0か1かでどちらの処理をするかを分岐させるようです。
自分で具体例の図を描くことが必須！
プログラムの説明によりこのあたりのことまでがわかれば、次は図１に従って自分で具体例の図を描いてみます。よく授業の時にも「自分で具体例のお絵かきができれば問題の５０％は解答できたようなもの」と言っていますがこの問題では、図を描くことが必須です。
要素数は３個で考えてみました。こんな感じです。
実際のメモリにはこのように配置されているわけですが、これを考えやすいようにリスト構造図にするとこうなります。
次にプログラムですが、次のような構造になっています。ラベルの上に線を描け！飛び先チェック！です。
- 最初のループで該当要素の場所を探索。
- GR3の値に従って「挿入」か「削除」の処理へ分岐。
- 飛び先で該当の処理を行う。
１重ループの後に２方向分岐というとても単純なものです。分岐の際にラベルの配列から該当するラベルを取り出して分岐をする、という方法を使っています。これもよくあるパターンです。
穴埋めの設問１を設問２と一緒に考えるためにまずは、挿入の操作でトレースをしてみましょう。いつものようにレジスタ表を書きます。
８行目に到達した段階で、次の要素に行くためには今GR2に入っている次の要素のアドレス10をGR1に入れて、現在の要素のアドレスとする必要があります。ですので、空欄ａにはGR2の内容をGR1に入れる命令が入ります。
解答は（エ） LD GR1,GR2 となります。
LINSラベルに分岐した後の挿入操作では、副プログラムEGETを呼び出し挿入要素のための領域を確保します。図解するとこのようなイメージです。色がついているところが確保された領域です。
副プログラムEGETから戻ってきた段階でのレジスタの状態は下記の通りです。GR4には確保領域の先頭アドレスが入っています。
挿入操作は、図のような操作をします。
- 要素２の次へのポインタを確保領域のアドレスにする。（１４番地に１８を入れる）
- 確保領域の次へのポインタを要素３のアドレスにする。（挿入要素の１語目：１８番地に１２を入れる）
- 確保領域にデータの値を入れる。（挿入要素の２語目：１９番地に２５０を入れる）
これを１４行目から１６行目で行います。２．が１５行目で、３．が１６行目で行われているので、１．が１３行目の空欄で行われれば良いわけです。
具体的に言えば、１８を１４番地に入れればいいということです。つまり、GR2の内容をGR1の中に入っているアドレスの場所に入れれば良いわけです。
空欄ｂは（ウ） ST GR4,0,GR1 が解答となります。
空欄cは削除操作です。LDELに分岐した時のレジスタの状態と操作の図解は下記の通りです。
空欄cのコメントによるとGR4に要素３（n=2なので、n+1は３）のアドレス１２を入れれば良いということになります。このアドレスは要素２の１語目に入っているので
答えは（イ） LD GR4,0,GR2 となります。
設問２は上記の図で「１０行目に到達した時」のレジスタの内容を参照してください。この時にGR2に格納されている値は１２です。これは要素３の先頭アドレスですので、
答えは（ウ）となります。
設問３は、プログラム２のデータ領域を図解すると下記のようになります。
更にリスト構造図にすると下記の通りです。２番目の後ろに要素を挿入する場合は次のように記憶内容のアドレスを変更すれば良いのでラベルE3番地の記憶内容は要素２の１語目ということになり、答えは（ア）のα１となります。
2016年（平成28年度）秋期の解説
- Date：
- Tag：
- この記事を
友だちに教える - LINE
- - HatenaBookmark
- GooglePlus
