修了試験 2014-01-26実施分 基本情報技術者試験 問7
2,000個の相異なる要素が,キーの昇順に整列された表がある。 外部から入力したキーによってこの表を2分探索して,該当するキーの要素を取り出す。 該当するキーが必ず表中にあることが分かっているとき,キーの比較回数は最大何回か。
正答3
解説
正解はウ。 2分探索の最大比較回数は,ceil(log2(N+1))で求まる。 N=2,000のとき,2^10=1,024,2^11=2,048なので,log2(2,001)は10と11の間となり,最大比較回数は11回となる。まとめて解く
修了試験 2014-01-26実施分を通しで解く(80問)→