平成26年度秋期 情報処理安全確保支援士 午前Ⅰ 問4

午前I 問04：二分探索木は“左右のルール付き本棚”だよ

二分探索木では、左の子には小さい値、右の子には大きい値を置くというルールがあるよ。探すときや追加するときは、この大小関係を手がかりにして、辞書を引くみたいに左右へたどっていこう。

この問題で問われていること

ただ枝が2本に分かれるだけの二分木と、値の大小ルールを使って効率よく探せる二分探索木の違いを見分けられるかがポイントだよ。

Binary Search Tree

a binary search tree maintains the ordering rule that left subtree keys are smaller and right subtree keys are larger

left < parent < right

確認ポイント

• 左右に子が 2 つあるだけではありません。
• 順序関係が重要です。
• 探索木の条件を選ぶ。

正解

エ

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア

不正解だよ。これはライトスルー方式の特徴に近いんだ。ライトスルーは、メモを手元のノートと本部の台帳に毎回同時に書くので、内容がずれにくい。ライトバックは手元のノートだけ先に直して、あとで本部に反映する方式だから、常に一貫性を保ちながら書く、とは言いにくいよ。

選択肢イ

不正解だよ。ライトバック方式では、キャッシュにだけ新しい内容が残っていて主記憶が古いままのことがあるんだ。そのキャッシュを追い出すときは、古い台帳を最新に直すために主記憶へ書き戻しが必要になる場合があるよ。だから「書き戻しが不要」は逆なんだ。

選択肢ウ

不正解だよ。ライトバック方式は、書込み回数を減らす代わりに「あとでまとめて主記憶へ反映する」仕組みなので、どのキャッシュが最新版かを管理する回路はむしろやや複雑になるんだ。合鍵を何人もが持っている家で、誰が最新のメモを書き換えたか確認する手間が増える感じだね。

選択肢エ（正解）

正解だよ。ライトバック方式は、まずキャッシュだけに書き込んで、必要になったときだけ主記憶へまとめて書き戻す方式なんだ。毎回本社窓口まで報告に行かず、手元のメモにためておいて後でまとめて提出する感じなので、主記憶への書込み頻度を減らせるよ。