東京理科大学 infoserv［更新日］2000.10.23

問１０ 　次のアセンブラプログラムの説明及びプログラムを読んで，設問に答えよ。

〔プログラムの説明〕

単方向リストの作成と削除を行うための副プログラム群である。 リストは ROOT から始まり，各要素は次の要素へのポインタと値によって構成される。 リストの最後の要素のポインタには，NULL が格納されている。 単方向リストの例を図 1 に示す。


図１　単方向リスト

(1)

リスト領域は，要素を格納するための FLIST（偶数番地）から始まる大きさ FLSIZE語の領域である。 各要素は 2 語からなり，図 2 に示す構造をしている。 F はその要素が使用されているかどうかを示す 1 ビットのフラグであり， ガーベジコレクション（副プログラム GC）で使用される。 Address と F をあわせた 1 語を，次の要素へのポインタとして使う。 NULL は #0000 で表す。 V には要素の値を格納する。


図２　リスト領域と要素の構造
(2)

主プログラムの最初で，副プログラム FLINIT を呼び出して初期化を行う。

(3)

副プログラム FLINIT は，次の初期化を行う（プログラムは省略）。

  • ROOT に NULL を格納する。
  • リスト領域の終端番地の次の番地（FLIST＋FLSIZE）を FLMAXP に格納する。 　FLMAXP は副プログラム GC で使用する。
  • リスト領域のすべての要素を連結した単方向リスト（フリーリストと呼ぶ）を作成し， リストの先頭番地を FLPTR に格納する。
(4)

副プログラム GC は，リスト領域の使用されていない要素（F が“未使用”）を 集めてフリーリストを作成し，リストの先頭番地を FLPTR に格納する（プログラムは省略）。

(5)

副プログラム GET は，フリーリストから要素を 一つ取り出す。 GET は呼び出されるたびに，取り出した要素の先頭番地を GR1 に格納する。 ただし，フリーリストの要素がなくなった場合には，副プログラム GC を呼び出して， フリーリストを再度作成する。 それでも要素がない場合には，メッセージを出力して実行を終了する。

(6)

副プログラム ADD は，GR0 に格納されている値をもつ要素を作り， ROOT から始まるリストの先頭に挿入する。 主プログラムは，追加するデータを GR0 に格納しADD を呼び出す。 図 1 のリストに値 25 の要素を追加する例を図 3 に示す。


図３　リストへの挿入
(7)

副プログラム DEL は，ROOT から始まるリストから要素を順に検索し，GR0 と同じ値をもつ要素が見つかれば，その要素を削除する。 主プログラムは削除するデータを GR0 に格納し，DEL を呼び出す。 図 1 のリストから値 30 の要素を削除する例を図 4 に示す。


図４　リストからの削除
(8)

ADD 及び DEL から戻るとき，汎用レジスタ GR1 〜 GR3 の内容を元に戻す。

(9)

GET から戻るとき，汎用レジスタ GR2，GR3 の内容を元に戻す。

〔プログラム〕 

; リストに要素を追加する
; パラメタ GR0:追加する値
ADD      PUSH   0,GR1         
         ST     GR0,TEMP
         CALL   GET          ; リストの要素を獲得する
         LD     GR0,TEMP
         
         LD     GR0,ROOT
            ; リストに追加する
         ST     GR1,ROOT
         POP    GR1
         RET

; リストから要素を削除する
; パラメタ GR0:削除する値
DEL      PUSH   0,GR1
         PUSH   0,GR2
         PUSH   0,GR3
         LEA    GR1,ROOT
         LD     GR2,0,GR1
DLOOP    LEA    GR2,0,GR2
         JZE    DEND         ; リストの末尾
         CPA    GR0,1,GR2    ; 同じ値が見つかったか
         JZE    DELEND
         LEA    GR1,0,GR2
         
         JMP    DLOOP 
DELEND   
         ST     GR3,0,GR1
         LD     GR3,FLAG
         ST     GR3,0,GR2
DEND     POP    GR3
         POP    GR2
         POP    GR1
         RET

; フリーリストから要素を取り出す
; パラメタ なし
; 結果 GR1:要素の番地
GET      LD     GR1,FLPTR
         LEA    GR1,0,GR1
         JNZ    GL01
         CALL   GC           ; 副プログラムGCを呼び出す
         LD     GR1,FLPTR
         LEA    GR1,0,GR1
         
         OUT    ERMSG,ERMLEN ; 空き要素なし
         EXIT
GL01     LD     GR0,0,GR1
         ST     GR0,FLPTR
         RET
FLIST    DS     1000
FLSIZE   DC     1000
FLMAXP   DS     1
FLPTR    DS     1
FLAG     DC     1
ERMSG    DC     'NO AVAILABLE ELEMENT'
ERMLEN   DC     20
ROOT     DS     1
TEMP     DS     1
         END
設問 　 プログラム中の に入れる正しい答えを， 解答群の中から選べ。

a，b に関する解答群

ア　ST GR0,0,GR1　　　　イ　ST GR0,1,GR1　　　　ウ　ST GR2,0,GR1

エ　ST GR2,1,GR1　　　　オ　ST GR3,0,GR1　　　　カ　ST GR3,1,GR1

c，d に関する解答群

ア　LD GR0,0,GR2　　　　イ　LD GR0,1,GR2　　　　ウ　LD GR2,0,GR2

エ　LD GR2,1,GR2　　　　オ　LD GR3,0,GR2　　　　カ　LD GR3,1,GR2

e に関する解答群

ア　JMI GL01　　　　イ　JNZ GL01　　　　ウ　JPZ GL01

エ　JZE GL01

東京理科大学 infoserv 戻る 次頁：問11