トップ過去問一覧応用情報技術者 平成21年・春 > 問8
問8

相異なる n 個のデータが昇順に整列された表がある。この表を m 個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータの存在するブロックを探し出す。次に、当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで、 m は十分おおきく、 n は m の倍数とし、目的のデータは必ず表の中に存在するものとする。

○正解
×不正解

m + m/n

m/2 + n/2m

n/m

n/2m

解説

文章ではややこしく思うことも書いてみるとわかりやすくなります。

| 123 | | 456 | | 789 | 

  -m-   -m-   -m-  

3 6 9 と調べて欲しいデータ(例:5)がある場所を特定する(456の中にある)という流れです。

線形探索かつ平均なので (n/m)/2 回でどのブロックか特定でき m/2 でブロック内のどこかわかりそうです。

まとめて m/2 + n/2m です。

無料学習システムはこちら
→間違えた問題を繰り返し学習
→分野別学習
→模擬試験モード
デモサイト
無料ユーザ登録

問題文や解説文の内容の正確性については、できるかぎりチェックをしていますが、間違いがある可能性があります。 十分ご注意の上、参考までにご利用ください。