問題
このページは問題閲覧ページです。正解率や解答履歴を残すには、 「条件を設定して出題する」をご利用ください。
[ 設定等 ]
二分探索木とは、各頂点に1つのキーが置かれた二分木であり、任意の頂点vについて次の条件を満たす。
(1)vの左部分木の頂点に置かれた全てのキーが、vのキーより小さい。
(2)vの右部分木の頂点に置かれた全てのキーが、vのキーより大きい。
以下では空の二分探索木に、8、12、5、3、10、7、6の順に相異なるキーを登録する場合を考える。最初のキー8は二分探索木の根に登録する。次のキー12は根の8より大きいので右部分木の頂点に登録する。次のキー5は根の8より小さいので左部分木の頂点に登録する。続くキー3は根の8より小さいので左部分木の頂点5に分岐して大小を比較する。比較するとキー3は5よりも小さいので、頂点5の左部分木の頂点に登録する。以降同様に全てのキーを登録すると下図に示す二分探索木を得る。
キーの集合が同じであっても、登録するキーの順番によって二分探索木が変わることもある。下図と同じ二分探索木を与えるキーの順番として、最も適切なものはどれか。
(1)vの左部分木の頂点に置かれた全てのキーが、vのキーより小さい。
(2)vの右部分木の頂点に置かれた全てのキーが、vのキーより大きい。
以下では空の二分探索木に、8、12、5、3、10、7、6の順に相異なるキーを登録する場合を考える。最初のキー8は二分探索木の根に登録する。次のキー12は根の8より大きいので右部分木の頂点に登録する。次のキー5は根の8より小さいので左部分木の頂点に登録する。続くキー3は根の8より小さいので左部分木の頂点5に分岐して大小を比較する。比較するとキー3は5よりも小さいので、頂点5の左部分木の頂点に登録する。以降同様に全てのキーを登録すると下図に示す二分探索木を得る。
キーの集合が同じであっても、登録するキーの順番によって二分探索木が変わることもある。下図と同じ二分探索木を与えるキーの順番として、最も適切なものはどれか。
1 .
8、5、7、12、3、10、6
2 .
8、5、7、10、3、12、6
3 .
8、5、6、12、3、10、7
4 .
8、5、3、10、7、12、6
5 .
8、5、3、12、6、10、7
( 技術士 第一次試験 令和元年度(2019年) 基礎科目「情報・論理に関するもの」 問8 )