平成26年度 技術士第二次試験問題【必須科目】
【16】情報工学部門
T−2
主記憶上で、配列にN個の見出し(key)付きデータが格納されているものとする。
このデータに対する操作に関する次の記述のうち、最も不適切なものはどれか。

 @ 線形探索法を用いて見出し探索を行う場合、1つの見出しの探索に
   要する最悪の計算量はO(N)である。
 A 2分探索法を用いて見出 し探索を行う場合、1つの見出しの探索に
   要する最悪の計算量はO(log2N)である。
 B データが見出し順にソートされているとき、新たなデータをその状態を
   くずさないように追加するために必要な最悪の計算量はO(log2N)である。
 C 2分探索法を用いて見出し探索を行う場合には、事前にデータを
   見出し順にソートしておかねばならない。
 D 2分探索法は、見出しの探索空間を1回の比較操作ごとに
   約2分の1ずつに狭める探索法である。



【正解】 B
計算量はオーダー記法
O()で表される大体(というより大雑把)の
処理時間を捉えるための指標である。
数字が1〜32まであったとして、1がどこにあるか調べるとき、
1が先頭にあったら計算量は1であり、O(1)と表記する。
もし1が一番最後にあったら1を見つけるのに32回調べないといけないので
計算量は32ということになり、O(32)と表記する。
@
線形検索法は最初から順番に検索していく方法である。
 上記のとおり最悪の計算量はO(N)である。
A
2分検索法は検索値と、データを2分割した真ん中の値を比較し、
 検索値がデータの真ん中の値よりも小さければ、データの前半部分を、
 大きければデータの後半部分を検索して、検索範囲を2分の1ずつ狭めて
 いく方法である。
 例えば32個のデータから9を調べるとき
 16 → 8 → 12 → 10 → 9の順番で検索する。
 最悪の計算量は O(log2N) となる。
B不適切である。2分検索法であれば、O(log2N)であるが、
 方法が明記されていないため、線形法で処理した場合、
 最悪の計算量はO(N)である。
C正しい。
D正しい。


EXCELのVBAのご相談なら ファーストマクロ 



T−1 目次 T−3
ファーストマクロ TOPページ