基本情報技術者(科目A)過去問集 - アルゴリズム

データの整列方法に関する記述のうち，適切なものはどれか。

2分探索において，データの個数が4倍になると，最大探索回数はどうなるか。ここで，データの個数は十分に多いものとする。

関数f(x)は，引数も戻り値も実数型である。この関数を使った，①〜⑤から成る手続を考える。手続の実行を開始してから②～⑤を十分に繰り返した後に，③で表示されるyの値に変化がなくなった。このとき成立する関係式はどれか。

① x ← a
② y ← f(x)
③ yの値を表示する。
④ x ← y
⑤ ②に戻る。

アルファベット3文字で構成されるキーがある。次の式によってハッシュ値hを決めるとき，キー “SEP” と衝突するのはどれか。ここで，a mod b は，aをbで割った余りを表す。

h = (キーの各アルファベットの順位の総和) mod 27

昇順に整列されたn個のデータが配列に格納されている。探索したい値を2分探索法で探索するときの，およその比較回数を求める式はどれか。

整列アルゴリズムの一つであるクイックソートの記述として，適切なものはどれか。

キーが小文字のアルファベット1文字（a，b，…，z のいずれか）であるデータを，大きさが10のハッシュ表に格納する。ハッシュ関数として，アルファベットのASCIIコードを10進表記法で表したときの1の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCIIコードでは，昇順に連続した2進数が，アルファベット順にコードとして割り当てられている。

ハッシュ法の説明として，適切なものはどれか。

次の流れ図において，
　① → ② → ③ → ⑤ → ② → ③ → ④ → ② → ⑥
の順に実行させるために，①においてmとnに与えるべき初期値aとbの関係はどれか。ここで，a，bはともに正の整数とする。

次の関数 f(n，k) がある。f(4，2) の値は幾らか。

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

バブルソートの説明として，適切なものはどれか。

配列Aの1番目からN番目の要素に整数が格納されている（N>1）。次の図は，Xと同じ値が何番目の要素に格納されているかを調べる流れ図である。この流れ図の実行結果として，適切な記述はどれか。

自然数nに対して，次のとおり再帰的に定義される関数 f(n) を考える。f(5) の値はどれか。

　f(n)：if n≦1 then return 1 else return n+f(n-1)

整数x，y（x＞y≧0）に対して，次のように定義された関数F（x，y）がある。F（231，15）の値は幾らか。ここで，x mod yはxをyで割った余りである。

与えられた正の整数 x₀，x₁（x₀＞x₁）の最大公約数を，次の手順で求める。x₀=175，x₁=77の場合，手順（2）は何回実行するか。ここで，“A←B” は，BをAに代入することを表す。

〔手順〕
（1）i ← 2
（2）x_i ← “x_i-2をx_i-1で割った剰余”
（3）x_i=0 ならばx_i-1を最大公約数として終了する。
（4）“i ← i+1” として（2）に戻る。

2分木の各ノードがもつ記号を出力する再帰的なプログラムProc（n）の定義は，次のとおりである。このプログラムを，図の2分木の根（最上位のノード）に適用したときの出力はどれか。

Proc（n）{
　nに左の子 l があればProc（l）を呼び出す。
　nに右の子 r があればProc（r）を呼び出す。
　nの記号を出力して終了する。
}

配列 A[i]（i=1，2，...，n） を，次のアルゴリズムによって整列する。行2～3の処理が初めて終了したとき，必ず実現されている配列の状態はどれか。

〔アルゴリズム〕
行番号
　　1　iを1からn-1まで1ずつ増やしながら行2～3を繰り返す
　　2　jをnからi+1まで1ずつ減らしながら行3を繰り返す
　　3　もし A[j]＜A[j-1] ならば，A[j]とA[j-1]を交換する

正の整数Mに対して，次の二つの流れ図に示すアルゴリズムを実行したとき，結果xの値が等しくなるようにしたい。aに入れる条件として，適切なものはどれか。

再帰的に定義された手続 proc で，proc（5）を実行したとき，印字される数字を順番に並べたものはどれか。

proc（n）
　n=0 ならば戻る
　そうでなければ
　{
　　nを印字する
　　proc（n-1）を呼び出す
　　nを印字する
　}
　を実行して戻る

要素番号が0から始まる配列 TANGO がある。n個の単語が TANGO[1] から TANGO[n] に入っている。図は，n番目の単語を TANGO[1] に移動するために，TANGO[1] から TANGO[n-1] の単語を順に一つずつ後ろにずらして単語表を再構成する流れ図である。aに入れる処理として，適切なものはどれか。

探索表の構成法を例とともに a〜c に示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す。

	a	b	c
ア	2分探索	線形探索	ハッシュ表探索
イ	2分探索	ハッシュ表探索	線形探索
ウ	線形探索	2分探索	ハッシュ表探索
エ	線形探索	ハッシュ表探索	2分探索

nの階乗を再帰的に計算する関数 F(n) の定義において，aに入れるべき式はどれか。ここで，nは非負の整数とする。

　n＞0のとき，F(n)＝[　a　]
　n＝0のとき，F(n)＝1

自然数をキーとするデータを，ハッシュ表を用いて管理する。キーxのハッシュ関数 h(x) を
　h(x) = x mod n
とすると，任意のキーaとbが衝突する条件はどれか。ここで，nはハッシュ表の大きさであり，x mod nはxをnで割った余りを表す。

関数 f(x，y) が次のとおり定義されているとき，f(775，527) の値は幾らか。ここで，x mod y はxをyで割った余りを返す。

　f(x，y)：if y = 0 then return x else return f(y，x mod y)

xとyを自然数とするとき，流れ図で表される手続を実行した結果として，適切なものはどれか。

	qの値	rの値
ア	x÷yの余り	x÷yの商
イ	x÷yの商	x÷yの余り
ウ	y÷xの余り	y÷xの商
エ	y÷xの商	y÷xの余り

次の流れ図は，2数A，Bの最大公約数を求めるユークリッドの互除法を，引き算の繰返しによって計算するものである。Aが876，Bが204のとき，何回の比較で処理は終了するか。

次の流れ図は，10進整数j（0＜j＜100）を8桁の2進数に変換する処理を表している。2進数は下位桁から順に，配列の要素 NISHIN(1) から NISHIN(8) に格納される。流れ図のa及びbに入れる処理はどれか。ここで，j div 2 はjを2で割った商の整数部分を，j mod 2はjを2で割った余りを表す。

	a	b
ア	j ← j div 2	NISHIN(k) ← j mod 2
イ	j ← j mod 2	NISHIN(k) ← j div 2
ウ	NISHIN(k) ← j div 2	j ← j mod 2
エ	NISHIN(k) ← j mod 2	j ← j div 2

配列Aが図2の状態のとき，図1の流れ図を実行すると，配列Bが図3の状態になった。図1のaに入れる操作はどれか。ここで，配列A，Bの要素をそれぞれ A(i，j)，B(i，j) とする。

顧客番号をキーとして顧客データを検索する場合，2分探索を使用するのが適しているものはどれか。

0≦x≦1 の範囲で単調に増加する連続関数 f(x) が f(0)<0≦f(1) を満たすときに，区間内で f(x)=0 であるxの値を近似的に求めるアルゴリズムにおいて，（2）は何回実行されるか。

〔アルゴリズム〕
（1）x₀ ← 0，x₁ ← 1とする。
（2）x ← $\frac{x_0+x_1}{2}$ とする。
（3）x₁ - x ＜ 0.001 ならばxの値を近似値として終了する。
（4）f(x)≧0 ならば x₁ ← x として，そうでなければ x₀ ← x とする。
（5）（2）に戻る。

長さ m，n の文字列をそれぞれ格納した配列 X，Y がある。図は，配列Xに格納した文字列の後ろに，配列Yに格納した文字列を連結したものを，配列に格納するアルゴリズムを表す流れ図である。図中の a，b に入れる処理として，適切なものはどれか。ここで，1文字が一つの配列要素に格納されるものとする。

	a	b
ア	Z(k) ← X(k)	Z(m＋k) ← Y(k)
イ	Z(k) ← X(k)	Z(n＋k) ← Y(k)
ウ	Z(k) ← Y(k)	Z(m＋k) ← X(k)
エ	Z(k) ← Y(k)	Z(n＋k) ← X(k)

次に示すユークリッドの互除法（方法1，方法2）で，正の整数a，bの最大公約数は，それぞれとnのどちらの変数に求まるか。ここで，m mod nは，mをnで割った余りを表す。

	方法1	方法2
ア	m	m
イ	m	n
ウ	n	m
エ	n	n

右の流れ図が左の流れ図と同じ動作をするために，a，bに入るYesとNoの組合せはどれか。

	a	b
ア	No	No
イ	No	Yes
ウ	Yes	No
エ	Yes	Yes

2分探索に関する記述のうち，適切なものはどれか。

クイックソートの処理方法を説明したものはどれか。

表探索におけるハッシュ法の特徴はどれか。

昇順に整列済みの配列要素 A(1)，A(2)，...，A(n) から，A(m)=k となる配列要素A(m)の添字mを2分探索法によって見つける処理を図に示す。終了時点で m=0 である場合は，A(m)=k となる要素は存在しない。図中のaに入る式はどれか。ここで，“/” は，小数点以下を切り捨てる除算を表す。

次の流れ図は，シフト演算と加算の繰返しによって2進整数の乗算を行う手順を表したものである。この流れ図中のa，bの組合せとして，適切なものはどれか。ここで，乗数と被乗数は符号なしの16ビットで表される。X，Y，Zは32ビットのレジスタであり，桁送りには論理シフトを用いる。最下位ビットを第0ビットと記す。

	a	b
ア	Yの第0ビット	Xを1ビット左シフト，Yを1ビット右シフト
イ	Yの第0ビット	Xを1ビット右シフト，Yを1ビット左シフト
ウ	Yの第15ビット	Xを1ビット左シフト，Yを1ビット右シフト
エ	Yの第15ビット	Xを1ビット右シフト，Yを1ビット左シフト

次の文章はあるソート（整列法）について述べたものである。そのソートはどれか。

　“データの並びに対して基準となるある値を定めて，その値より小さいデータの並びが前半に，大きいデータが後半に並ぶように並べ替える。このようにして出来た前半の並び，及び後半の並びそれぞれに対して，再帰的に同じ操作を繰り返す。ここで，データの並びに対してその都度決める基準値は分割される。前半の並びと後半の並びの大きさが同じ程度の大きさになるように選ぶことが望ましい。”

流れ図は，1からN（N≧1）までの整数の総和（1+2+…+N）を求め，結果を変数xに入れるアルゴリズムを示している。流れ図中のaに当てはまる式はどれか。

整列されたn個のデータの中から，求める要素を2分探索法で探索する。この処理の計算量のオーダを表す式はどれか。

2,000個の相異なる要素が，キーの昇順に整列された表がある。外部から入力したキーによってこの表を2分探索して，該当するキーの要素を取り出す。該当するキーが必ず表中にあることが分かっているとき，キーの比較回数は最大何回か。

昇順に整列されたn個のデータが格納されている配列Aがある。流れ図は，2分探索法を用いて配列Aからデータを探し出す処理を表している。a，b に入る操作の適切な組合せはどれか。ここで，除算の結果は小数点以下が切り捨てられる。

	a	b
ア	k+1→hi	k-1→lo
イ	k-1→hi	k+1→lo
ウ	k+1→lo	k-1→hi
エ	k-1→lo	k+1→hi

長さ m，n の文字列を格納した配列 X，Y がある。図は，長さの文字列の後ろに長さんの文字列を連結したものを配列Zに格納するアルゴリズムを表す流れ図である。図中の a，b に入れる処理として，適切なものはどれか。ここで，1文字が一つの配列要素に格納されるものとする。

	a	b
ア	X(k) → Z(k)	Y(k) → Z(m＋k)
イ	X(k) → Z(k)	Y(k) → Z(n＋k)
ウ	Y(k) → Z(k)	X(k) → Z(m＋k)
エ	Y(k) → Z(k)	X(k) → Z(n＋k)

n!の値を，次の関数 F(n) によって計算する。乗算の回数を表す式はどれか。

次のような一連の代入文がある。
　x+y → x
　x-y → y
　x-y → x
x，yの初期値をそれぞれA，Bとするとき，最後の代入文の実行が終了した時点におけるxとyの値の適切な組合せはどれか。

	x	y
ア	A	B
イ	B	A
ウ	2B	A-B
エ	A-B	A-B

2分探索法に関する次の記述のうちで，適切なものはどれか。

流れ図に従って，選択ソートによって値を大きい順に整列するとき，α印の処理（比較）が実行される回数を表す式はどれか。

次の流れ図は，1から100までの整数の総和を求め，結果を変数に代入するアルゴリズムを示したものであるが，一部誤りがある。どのように訂正すればよいか。

ハッシュ表探索において，同一のハッシュ値となる確率が最も低くなるのは，ハッシュ値がどの分布で近似されるときか。

あらかじめ整列された1000人の電話番号から，目的の電話番号を2分探索法を用いて探索するとき，最大およそ何回の比較が必要になるか。

6個の数値180，315，282，410，645，525を並べ替える。手順1～4は途中までの手順を示したものである。手順4まで終わったときの結果はどれか。

手順1 並びの左側から順に，数値の1の位の値によって0～9のグループに分ける。
手順2 次に0のグループの数値を左側から順に取り出して並べ，その右側に1のグループ，以下順に2～9のグループの数値を並べていく。
手順3 手順2で得られた数値の並びの左側から順に，数値の10の位によって0～9のグループに分ける。
手順4 手順2と同様に，0のグループの数値から順に並べる。

ここで，グループ内では，処理が行われた数値を左側から順に並べるものとする。

次の手順はシェルソートによる整列を示している。データ列7，2，8，3，1，9，4，5，6を手順（1）（4）に従って整列するとき，手順（3）を何回繰り返して完了するか。ここで，[ ] は小数点以下を切り捨てた結果を表す。

〔手順〕
（1）[データ数÷3]→Hとする。
（2）データ列を互いにH要素分だけ離れた要素の集まりからなる部分列とし，それぞれの部分列を，挿入法を用いて整列する。
（3）[H÷3]→Hとする。
（4）Hが0であればデータ列の整列は完了し，0でなければ（2）に戻る。

ヒープソートの説明として，適切なものはどれか。