アルゴリズムとプログラミング (全23問中22問目)
No.22
ファイルを4冊だけ置くことができる机で，A～Fの6冊のファイルを使って仕事をする。机上に5冊目のファイルを置きたいとき，机上の4冊のファイルのうち，最後に参照してから最も時間が経過しているファイルを引き出しにしまうことにする。ファイルがA，B，C，D，B，A，E，A，B，Fの順で必要になった場合，最後に引き出しにしまうファイルはどれか。
出典：平成21年春期 問85
- A
- B
- D
- E
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズムとプログラミング
正解
ウ
解説
置換アルゴリズムであるLRU(Least Recently Used)方式の考え方に関する出題です。4つの枠を用意し、机上の状態を追っていきます。
A ⇒ A
B ⇒ AB
C ⇒ ABC
D ⇒ ABCD
B ⇒ ABCD（入替えなし）
A ⇒ ABCD（入替えなし）
E ⇒ ABED (最後の参照が最も昔であるCとEを入れ替え)
A ⇒ ABED（入替えなし）
B ⇒ ABED（入替えなし）
F ⇒ ABEF（最後の参照が最も昔であるDとFを入れ替え)
したがって最後に引き出しにしまうファイルは「D」です。
A ⇒ A
B ⇒ AB
C ⇒ ABC
D ⇒ ABCD
B ⇒ ABCD（入替えなし）
A ⇒ ABCD（入替えなし）
E ⇒ ABED (最後の参照が最も昔であるCとEを入れ替え)
A ⇒ ABED（入替えなし）
B ⇒ ABED（入替えなし）
F ⇒ ABEF（最後の参照が最も昔であるDとFを入れ替え)
したがって最後に引き出しにしまうファイルは「D」です。