問題プレビューID: 40061539応用情報技術者試験 2018年(平成30年度)春期 午前

問 6
応用情報技術者試験 2018年(平成30年度)春期 午前

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

解説

正解は「イ」です。

表は mm 個ごとのブロックに分割されるので,ブロック数は n/mn / m です。

まず,各ブロックの最後尾のデータだけを線形探索して目的のデータが存在するブロックを探します。線形探索の平均比較回数は探索対象の個数の半分なので,n/m2=n2m\frac{n/m}{2} = \frac{n}{2m} 回です。

次に,見つけたブロック内(mm 個のデータ)を線形探索します。この平均比較回数は m2\frac{m}{2} 回です。

両者の合計が求める平均比較回数であり,m2+n2m\frac{m}{2} + \frac{n}{2m} となります。

  • ア・ウ・エ: ブロック探索とブロック内探索のどちらかの回数を欠いたり,割合を誤ったりした式であり,正しくありません。

関連問題

本文が同じ・似ている問題を表示しています