応用情報技術者一覧

NO IMAGE

すべての葉が同じ深さであり、かつ、葉以外のすべての節点が二つの子を持つ要素数nの完全2分木がある。どの部分木をとっても左の子孫は親より小さく、右の子孫は親より大きいという関係が保たれている。2分木で探索する場合、ある要素を探索するときの最大比較回数のオーダはどれか。

【問題】 すべての葉が同じ深さであり、かつ、葉以外のすべての節点が二つの子を持つ要素数nの完全2分木がある。どの部分木をとっても左の...

NO IMAGE

従業員番号と氏名の対がn件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで、検索する従業員番号はランダムに出現し、探索は常に表の先頭から行う。また、与えられた従業員番号がこの表に存在しない確率をaとする。

【解答】 「与えられた従業員番号がこの表に存在しない確率をaとする」ということは、「与えられた従業員番号がこの表に存在する確率」は1...

NO IMAGE

葉以外の節点は全て二つの子をもち、根から葉までの深さが全て等しい木を考える。この木に関する記述のうち、適切なものはどれか。ここで、深さとは根から葉に至るまでの枝の個数を表す。また、節点には根及び葉も含まれる。

【問題】 葉以外の節点は全て二つの子をもち、根から葉までの深さが全て等しい木を考える。この木に関する記述のうち、適切なものはどれか。...