データ構造とアルゴリズム

(1)データ構造に関すること

スタックとキュー

キューとは、1次元配列に格納されたデータの一方からデータを格納し、 他方の端からデータを取り出すデータ構造のことです。 このようなデータの出し入れをFIFO(First-In First-Out：先入れ先出し)と呼びます。

また、スタックとは、1次元配列に格納された後から入れたデータを 先に取り出すデータ構造のことをいいます。 このようなデータの出し入れをLIFO(Last-In First-Out：後入れ先出し)と呼びます。

なお、

　データyをスタックに挿入することをpush(y),
　スタックからデータを取り出すことをpop(),
　データyをキューに挿入することをenq(y),
　キューからデータを取り出すことをdeq(),

とそれぞれ表わします。

たとえば、

push(a)
push(b)
enq(pop())
enq(c)
push(d)
push(deq())
x←pop()

としたとき（基本情報H18春[問12]）、次のような処理がおこなわれます。

よって、変数xにはbが入ります。

(2)アルゴリズムに関すること

流れ図

流れ図は、変数に実際の値を代入して処理後の値を確かめるのに用います。

流れ図の例１

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

初期値の候補
[ア]a=2b、[イ]2a=b、[ウ]2a=3b、[エ]3a=2b

順番	設問	選択肢
①	m(a),n(b)	[ア]a=2b(○) [イ]2a=b(○) [ウ]2a=3b(○) [エ]3a=2b(○)
②	ｍ(a)≠ｎ(b)	[ア]a=2b(○) [イ]2a=b(○) [ウ]2a=3b(○) [エ]3a=2b(○)
③	ｍ(a)＜ｎ(b)	[ア]a=2b(×) [イ]2a=b(○) [ウ]2a=3b(×) [エ]3a=2b(○)
⑤	ｎ(b)－ｍ(a)→ｎ(b－a)	[イ]2a=b(○) [エ]3a=2b(○)
②	ｍ(a)≠ｎ(b－a)	[イ]2a=b(×) [エ]3a=2b(○)
③	ｍ(a)＞ｎ(b－a)	[エ]3a=2b(○)
④	m(a)－ｎ(b－a)→m(2a－b)	[エ]3a=2b(○)
⑥	mの値を印字	[エ]3a=2b(○)

[エ]3a=2b（基本情報H18春[問42]）が①→②→③→⑤→②→③→④→②→⑥の順に実行させる初期値であることが分かりました。

流れ図の例２

次の流れ図は、シフト演算と加算の繰り返しによって2進数の乗算を行う手順を表したものです。 ここで、乗算と被乗算は符号なしの16ビットで表されます。 X、Y、Zは32ビットのレジスタであり、けた送りには論理シフトを用いる。

（基本情報H18春[問15]）

ここで、a、bに着目してみます。 Xは被乗数、Yは乗数、Zは乗算結果であることに注意して流れ図を見ます。

1. a
   　乗算Yの最下位ビットが1であれば、加算「Z+Y→Z」が必要です。
   　したがって、空欄aには、Yの最下位ビットが入ります。
2. b
   　乗数Yの1つ上位のけたの乗算を行うために、被乗数Xを1ビット左シフト、乗数Yを1ビット右シフトします。
   　したがって、空欄bには、Yを1ビット左シフト、Yを1ビット右シフトが入ります。

探索

線形探索法

線形探索は、配列の先頭から順番に目的のデータが見つかるまで探索する方法です。

線形探索法の平均探索回数

ｐ個のデータを線形探索するときの平均探索回数はｐ／２です。

たとえば、相異なるｎ個のデータが昇順に整列された表があり、 この表を１ブロックm個に分割し、各ブロックの最後尾のデータだけ線形探索することによって、 目的のデータの存在するブロックを探し出し、 次に該当ブロック内を線形探索して目的のデータを探し出すという探索のとき、 このときの平均探索回数は次のようになります。

なお、ｍ＜ｎとし、目的のデータは必ず表の中に存在するものとします。

ｎをｍ個づつブロックに分けて、その最後尾だけを探索することは ブロック数分の線形探索を行うことなので検索回数は(ｎ／m)／２回となります。

また、ブロック内の検索はｍ個の線形探索なのでｍ／２となります。

よって、平均探索回数はｍ／２＋(ｎ／m)／２回になります（基本情報H12秋[問14]）。

2分探索法

2分探索は、探索されるデータが昇順、または降順に整列している場合に使用できます。 探索データの中央の値と目的のデータを比較し、一致しなければ、中央の値の上下どちらにあるかを判断し、 探索データを半分に絞り込み、比較を続けていく方法です。

たとえば、昇順に整列済の配列要素A(1)、A(2)、…A(n)から、A(m)＝kとなる配列要素A(m)の添字mを ２分探索法によって見つける処理を図に示すと次のようになります。（基本情報H18春[問14]）

　この流れ図を見ても分かるように、(x＋y)／2→mで中央値を求めて解の選択の幅を狭めていることが分かります。 なお、終了時点でm＝0の場合、A(m)＝kとなる要素は存在しません。

戻る