過去問.com - 資格試験の過去問 | 予想問題の解説つき無料問題集

技術士の過去問 令和元年度(2019年) 基礎科目「情報・論理に関するもの」 問8

問題

このページは問題閲覧ページです。正解率や解答履歴を残すには、 「条件を設定して出題する」をご利用ください。
[ 設定等 ]
二分探索木とは、各頂点に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 .
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 )
このページは問題閲覧ページの為、解答履歴が残りません。
解答履歴を残すには、
条件を設定して出題する」をご利用ください。

この過去問の解説 (3件)

8

二分探索木に関する問題です。

選択肢を条件に沿って配列すると、下記のようになります。

    8

  5    12

3   7  10

  6

   8

 5    10

3  7    12

 6

   8 

 5   12

3  6 10

    7

④  

   8

 5   10

3 7    12

 6

   8

 5   12

3  6 10

    7

したがって、1が正解となります。 

 

付箋メモを残すことが出来ます。
4

<正解>1

[解説]

二分探索木に関する問題です。

問題文に与えられた条件で各選択肢を検討していきます。

問題文では、8、12、5、3、10、7、6の順にキーを登録しており、

まず、8の右に12、8の左に5が登録されています。

選択肢1から5の中で8の右に12が登録されるのは、1と3と5になります。

次に5の右に7、5の左に3が登録されています。

選択肢1、3、5のうち右に7が登録されるのは、1になります。

よって、1が正解となります。

4
手順に沿って落ち着いて1番から5番を並び替えます。

①     8
   5     12
 3   7  10 
    6
となり、1が図と同じになります。

②     8
   5     10
 3   7    12 
    6


③     8
   5     12
 3   6  10   
      7


④     8
   5     10
 3   7    12 
    6  


⑤     8
   5     12
 3   6  10 
      7  

問題に解答すると、解説が表示されます。
解説が空白の場合は、広告ブロック機能を無効にしてください。
他のページから戻ってきた時、過去問ドットコムはいつでも続きから始めることが出来ます。
また、広告右上の×ボタンを押すと広告の設定が変更できます。
この技術士 過去問のURLは  です。
付箋は自分だけが見れます(非公開です)。