「Java によるアルゴリズムとデータ構造の基礎」
演習問題解答2-5（正解）エ。

2-6（正解）ウ。

（2019 年 7 月 18 日現在）

1-1（正解）イ。

1-2（正解）イ。

1-3（正解）イ。

1-4（正解）ア。

1-5（正解）ア。

6 行目の変数 i は for 文の外にあり，コンパイルエラーとなる。

1-6（正解）エ。

拡張 for 文の用法を問う問題である。

2-7

ア

1 + 2 + … + (N－1) なので，誤り。

イ

ループせず総和の計算になっていないので，誤り。

ウ

1 + 2 + … + N なので，正解。

エ

整数の総和の計算になっていないので，誤り。

（正解）エ。に 変 換す る方 法を 表し たもの で ある 。
た と えば， j = 2 として 2 進数に変化すると，“10”が得られ，NISHIN[ 1 ] =0, NISHIN[ 2 ] = 1 となるので，それぞれの処理をトレースする。
ア2-1(100 × 10)3 =100 3×10 3 の計算量となる。したがって，1,000 倍の計算時間を要す

j div 2 = 2 div 2 = 1 → NISHIN[ 1 ]=1 となり，誤り。

ウj mod 2 = 2 mod 2 = 0 → j = 0， j div 2 = 0 div 2 = 0 →NISHIN[ 1 ] = 0；
j mod 2 = 0 mod 2 = 0 → j = 0， j div 2 = 0 div 2 = 0 →NISHIN[ 2 ] = 0 となり，誤り。

演算速度をもつコンピュータを用いるので，計算時間は 1／4 である 500 秒になエる。

となり正解。

ループ前の初期化処理で， x = 1, n = 1 となる。

正解。 n > M は 2 > 2 となり，ループ 2 回目で x × n = 1 × 2 → x = 2， n + 1 =

3-1

2-4

がって，アが正解。

（正解）イ。ド ・ モル ガンの 法 則を 利用 して 式を 展開す る 。

イ

正解 。

3-2の 流 れ 図 は ， （  A  0  B  0  の 否 定 で あ る の で ， ド ・ モ ル ガ ン の 法 則 よ り A  0  B  0   A  0  B  0 が 得 られ るの で， エが 正解 。

（正解）イ。

「隣同士 T( j )と T( j－1)交換」の処理があるので，「バブルソート」であることがわかる。昇順に整列するので，「T( j ) ＜ T( j－1)」の場合

 X  X   Y  Y    X   Y   X  Y（正解）エ 。 左 の 流 れ 図 では ， 手 続 き は  A  0  B  0  の 場 合 に 実 行 さ れ る 。 右長さ m の配列 X の後に，長さ n の配列 Y を格納した配列 Z を作

デックス k の初期値が 1 であることに着目すると， Y [ k] → Z [ m + k ]である。したx = 2 であり，左図の x = 2 と同一である。

ド ・ モル ガン の法 則は ， X  Y  X  Y また は ， X  Y  X  Y で ある 。

（正解）ア。

成するアルゴリズムである。ループ 1 では， X [ k ]→ Z [k ]とし，ループ 2 のイン2 ＋1 → n = 3 となる。 n > M は，3 > 2 となりループを脱出する。このとき，

2-3j mod 2 = 2 mod 2 = 0 → NISHIN[ 1 ] = 0； j div 2 = 2 div 2 = 1 → j = 1；
j mod 2 = 1 mod 2 = 1 → NISHIN[ 2 ] =1； j div 2 = 1 div 2 = 0 ・・・（正解）ウ。 M = 2 としてトレースしてみる。左図では x = 2 となる。右図では，

ウ→ NISHIN[ 1 ] = 1 とイるので，同一のコンピュータでは 2 × 1,000 ＝ 2,000 秒となる。しかし，4 倍のまず，ループ 1 回目で， x × n = 1 × 1 → x = 1， n + 1 = 1＋1→ n = 2 である。

j div 2 = 2 div 2 = 1→ j = 1， j mod 2 = 1 mod 2 = 1
なり，誤り。

（正解）ウ。「未知数の個数の 3 乗に比例する計算時間が掛かる」ので，100 元連立一次方程式の計算量を 100 3 とすると，1,000 元連立一次方程式では 1,0003 =2-2

こ の アル ゴリ ズ ムは ，素 因数 分解 を用い て 10 進数 から 2 進 数に交換が必要である。したがって，イが正解。
3-3（正解）エ。

実行前後の図を比べると，処理内容は配列のデータの位置を右に90°回転していることがわかる。 したがって， i 方向の位置は j 方向で“i ”になり， j 方向の位置は i 方向の“7 － j ”になる。したがって，正解は“B ( j , 7 －i )←A (i , j )”である。したがって，エが正解。

エ
4-1

F( 231，15 ) ＝ F( 15，231 mod 15 ) ＝ F( 15，6 ) ＝ F( 6，（正解）イ。

5-615 mod 6 ) ＝ F( 6，3 ) ＝ F( 3，6 mod 3 ) ＝ F( 3，0 ) ＝ 3（正解）ア。
イ

したがって，イが正解。
4-2（正解）エ。

f ( 4, 2 )＝ f ( 3, 1 )＋ f ( 3, 2 ) = 1 + 3 = 6

ウ（正解）イ。 F(5) = 5 × G(4) ，G(4) = 4 + F(3)，F(3) = 3 × G(2)，G(2) = 2 + F(1)，配列では要素をメモリ上の連続領域に格納するので，中間要素のインデック
スはデータサイズから計算でき，参照時間は一定になるので，誤り。

f ( 3, 2 ) = f ( 2, 1 ) + f ( 2 ,2 )= f ( 1, 0 )+f ( 1, 1 ) + 1 = 1 + 1 + 1 = 34-4

配列では，挿入や削除はデータの移動を伴うので，処理時間は要素数に依存するので，誤り。

ここで， f ( 3, 1 ) = f ( 2, 0 )+f ( 2, 1 ) = 1+f ( 1, 0 )+f ( 1, 1 ) = 1+1+1 = 3

4-3

データの移動は，配列ではデータの移動が必要であるので，誤り。

エ5-7

ポインタで実現するリストの特徴の説明であるので，誤り。

（正解）ウ。

A→K→T を A→G→K→T に変更することを考える。A の次ポイ

F(1) = 1 である。 したがって，上式を逆にたどり G(2) = 3， F(3) = 9, G(4) = 4 +ンタ（a）を 400 に，G の次ポインタ（x）を 300 する。また，G の前ポインタ（y）9 = 13， F(5) = 5 × 13 = 65 であるので，イが正解。

を 100 に，K の前ポインタ（f）を 400 にする必要がある。

（正解）イ。

X と y は対象外であるので，ウが正解。

再帰とは，実行中に自分自身を呼び出すことであり，再帰呼出しを行っても正しい結果を返すことができる性質をもつプログラムを「再帰的プロ

5-8グラム」と呼ぶ。

（正解）エ。
ア

挿入するデータの次ノードへの参照に現在の先頭ポインタの値をセット，リ4-5（正解）エ。

分割統治法の説明であるので，エが正解。

ストの先頭ポインタに挿入するデータのポインタをセット。ポインタを参照す

4-6（正解）ウ。

n の階乗は， n! = n×(n－1)!であるから，ウが正解。

る回数は 1 回。
イ

5-1（正解）ウ。

変更前

東京→品川→名古屋→新大阪，変更後

頭ポインタ→先頭データで 1 回。

東京→新横浜→名古屋→新大阪

5-2

現在の先頭のデータが持つ次ノードへの参照を，先頭ポインタにセット。先ウ末尾ポインタから末尾データへ飛び，末尾データの次ノードへの参照を追加「東京」から「新横浜」，「新横浜」から「名古屋」へのリンクをはればよい。

するデータにする。末尾ポインタに追加するデータの参照をセットする。末尾

すなわち，A(1, 2)=5 で A(5, 2)=3 とすれば良いので，ウが正解。

ポインタ→末尾データで 1 回。

（正解）イ。

変更前

東京→新横浜→熱海→浜松→名古屋，変更後

東京→新エ

正解。末尾データを削除には，末尾の 1 つ前のノードがもつ次ノードへの参

横浜→熱海→静岡→浜松→名古屋

照を空にする。末尾ポインタに末尾の一つ前のデータのポインタをセットす「熱海」のポインタを 150 に，「静岡」のポインタを 70 とすればよい。したがっる。単方向リストなので末尾のデータから逆方向の参照はできず，先頭から末て，イが正解。

尾の一つ前まで順番にポインタをたどっていく必要があるので，参照回数が多

5-3（正解）エ。

くなる。

5-4（正解）ウ。

5-5

初期データは，A→E→C→G→B である。

3 番目（C）と 4 番目（G）との間に値が H を挿入するので，next[ 3 ] = 8 とし6-1（正解）ア。

キューは，データを先入れ先出し（FIFO）で蓄える。て，next[ 8 ] = 7 であればよい。したがって，ウが正解。

6-2（正解）ア。

スタックは，データを後入れ先出し（LIFO）で蓄える。

（正解）ア。

6-3（正解）イ。

実行された 10 命令を一つずつ戻りながら，最初の PUSH 命令まイ

先頭へのデータの挿入は，配列ではデータの移動が必要であるため，誤り。

でさかのぼっていく。

ウ

配列では削除や挿入の操作を効率的に行えないので，誤り。

1. PUSH

スタックの一番上にあるデータ「192」を取り除く。

2. POP取り出されたデータ「?」(値が不明)をスタックに積む。

3. POP

取り出されたデータ「?」をスタックに積む。

イ

push(A)｛ A｝→push(B)｛ B,A｝→pop( ){A}→push(C)｛ C,A｝→push(D)｛ D,C,A｝→pop( ){ C,A }となり，A の取り出しはできないので，誤り。

4. PUSH

スタックの一番上にあるデータ「?」を取り除く。

5. PUSH

スタックの一番上にあるデータ「?」を取り除く。

→pop( ){ B,A }→pop( ){ A }→push(D) { D, A }6. PUSH

スタックの一番上にあるデータ「55」を取り除く。

→pop( ){ A}→pop( )｛ ｝となり，ウが正解。

7. PUSH

スタックの一番上にあるデータ「326」を取り除く。

8. POP
9. PUSHウエ

push(A) ｛A ｝

→push(B) ｛B,A ｝→push(C) ｛C,B,A ｝

push(A)｛A｝→push(B)｛B,A｝→ push(C)｛C,B,A｝→push(D)｛D,C,B,A｝→ pop( )｛C,B,A｝→ pop( )｛B,A｝となり，A の取り出しはできないので，取り出されたデータ「?」をスタックに積む。
スタックの一番上にあるデータ「?」を取り除く。

誤り。

10. これが最初の PUSH 命令である。スタックの一番上にあるデータは「7」なの6-4で，１番目の命令では「7」が PUSH されたことがわかる。したがって，正解

7-1（正解）ウ。

はイ。

7-2（正解）ア。

スタックの状態の推移は，以下のようになる。

7-3（正解）ア。

PUSH 1 ｛ 1｝→ PUSH 5 ｛ 5,1｝→ POP｛ 1｝ → PUSH 7｛ 7,1｝ → PUSH

7-4

（正解）ア。

（正解）ウ。

6｛ 6,7,1｝→ PUSH 4 ｛ 4,6,7,1 ｝→ POP｛ 6,7,1｝ → POP｛ 7,1｝ → PUSH

前順走査なので，節点 → 左部分木 → 右部分木の順に走査する。

3｛ 3,7,1｝ したがって，ウが正解。

7-5（正解）ウ。

6-5（正解）ウ。

7-6（正解）ウ。

6-6（正解）ウ。

6-7

キューの状態の推移は，以下のようになる。

与えられたプログラムを設問の 2 分木に適用すると次のようになる。最初に 2 分木の根である"+"から開始。

ENQ1｛ 1｝→ENQ2｛ 2,1｝→ENQ3｛ 3,2,1｝→DEQ｛ 3,2｝→ENQ4｛ 4,3,2｝

・[proc(+)]"+"の左には"a"があるので，Proc(a)が呼び出される。

→ENQ5｛ 5,4,3,2｝→DEQ｛ 5,4,3｝→ENQ6｛ 6,5,4,3｝→DEQ｛ 6,5,4｝→DEQ

・[Proc(a)]"a"の左右にはノードがないので，a を出力し，Proc(+)に戻る。

｛ 6,5｝

・[proc(+)]"+"の右には"*"があるので，Proc(*)が呼び出される。

し た が っ て ， 次の DEQ の操作で取り出される値は 5 である。正解はウ。

・[Proc(*)]"*"の左には"-"があるので，Proc(-)が呼び出される。

変数 p は現在の配列の要素数を保持している変数である。f(x)は配・[Proc(-)]"-"の左には"b"があるので，Proc(b)が呼び出される。

列の最後に引数である x を代入する関数であり，g( )は配列の最後の要素を返す関・[Proc(b)]"b"の左右にはノードがないので，b を出力し，Proc(-)に戻る。

数と考えることができる。「配列の最後にデータを追加する」および「最後に追・[Proc(-)]"-"の右には"c"があるので，Proc(c)が呼び出される。

加されたデータを取り出す」という 2 つの操作を合わせると LIFO（後入れ先出し）・[Proc(c)]"c"の左右にはノードがないので，c を出力し，Proc(-)の処理に戻り，（正解）イ。

-を出力し，Proc(*)に戻る。のデータ構造が実現される。したがって，イが正解。
6-8（正解）イ。

・[Proc(*)]"*"の右には"d"があるので，Proc(d)が呼び出される。

6-9（正解）ウ。

・[Proc(d)]"d"の左右にはノードがないので，d を出力し，Proc(*)の処理に戻6-10（正解）ウ。
ア

スタックの状態の推移は，以下のようになる。

り，*を出力し，Proc(+)に戻る。

push(A)｛A｝→pop( ){ }→ push(B)｛B｝→ push(C)｛C,B｝→push(D)｛D,C,B｝

・Proc(+)は，+を出力し，処理が終了。

→ pop( )｛C,B｝となるので，B の取り出しはできないので，誤り。

出力された記号を順番に並べると「 abc－ d*＋」となり，ウが正解。

7-7（正解）ウ。 この木構造において深さ(k)が増加すると節点数(n)は次のように変・B2 )h =178) 10 より，mod( 178, 8 ) = 2・・・衝突発生化する。 k＝1→n＝3

したがって，ウが正解。

k＝2→n＝7

k＝3→n＝15

ここでは選択肢の式に k＝3 を代入して， n が 15 になるか否かで判定する。

8-8（正解）ウ。

8-9（正解）ア。

ア

n = k(k＋1)＋1=3(3+1)+1=12+1=13 で，誤り。

イn＝2k＋3=2 3+3=8+3=11 で，誤り。

1)×55 = 80520

ウ

正解。 n＝280520 の下 4 けた「0520」に 0.5 を乗じると参照すべきアドレス 0260 が求めらエn＝(k－1)(k＋1)＋4=(3－1)(3＋1)=8 で，誤り。

k＋ 1－1=2 4－1=16－1=15れる。したがって，アが正解。
8-108-1（正解）ア。

時間計算量は，「2 分探索」は O(log n) ，「線形探索」は O(n)，8-38-48-5（正解）イ。

（正解）イ。
表に従って，キー“SEP”を１文字ずつ数値に割り当てる。 “S”＝ 19，“E”＝ 5，“P”＝ 16 であるので， 19 ＋ 5 ＋ 16 ＝ 40， したがって，ハッシュ値 h ＝ 40

ハッシュ探索は O(1)である。したがって，アが正解。
8-255550) 11 = 5×11 4 ＋5×11 3＋5×112 ＋5×11 1 = ＝(11 3＋112 ＋11＋2 分探索において， N 個の要素を探索する場合，最大比較回数は，

÷ 27 ＝１余り 13。

「log2N+1」である。データの個数が 4 倍になると 「 log24 N+1 」 となり，log24 N

ア

APR→ 1＋ 16＋ 18 ＝35＝log22 2 +log2N=2+ log2N であるから，2 回増えることになる。したがって，イがイ

FEB→ 6＋ 5＋ 2 ＝13正解。

ウ

JAN→ 10＋ 1＋ 14 ＝25（正解）イ。 2 分探索法はソート済（昇順または降順）のデータに対する探索法

エNOV→ 14＋ 15＋ 22 ＝51である。したがって，イが正解。

したがって，イが正解。

（正解）ウ。 2 分探索法はソート済（昇順または降順）のデータに対する探索法

8-11（正解）イ。

ハッシュ値 h ＝ 13 ÷ 27 ＝ 0 余り 1313 )＝mode( 15,13 ) = 2 となる。

（正解）ウ。 2 分探索法は，整列されたデータの中央の値と対象データを比較し，したがって，イが正解。
8-12（正解）ウ。

ハッシュ値 h ＝ 25 ÷ 27 ＝ 0 余り 25
ハッシュ値 h ＝ 51 ÷ 27 ＝ 1 余り 24

ハッシュ関数に"54321"を当てはめると，mod( 5＋4＋3＋2＋1，である。したがって，ウが正解。

前方にデータがある場合は，前半分のデータの中央のデータと比較し，後方にデハッシュ値 h ＝ 35 ÷ 27 ＝ 1 余り 8

ハッシュ値は，「キー値をハッシュ表の大きさ 10 で割った余り」

ータがある場合は，後半分のデータの中央のデータと比較する。この操作を繰りなので，キー値の 1 の位がそのままハッシュ値になる。

返すことによって，検索する方法である。

まず，1 件目のレコードがハッシュ表の任意の場所に格納される。

A(k) と x を比較し，A(k)< x の場合は， k+1 を lo に入れる。A(k)>x の場合

次に，2 件目のレコードのハッシュ値が 1 件目のものと衝突しないためには，キは， k－1 を hi に入れる。したがって，ウが正解。

ー値の 1 の位が異なっていればよいので，衝突しない確率は 9／10 になる。

8-6（正解）ア。

2 分探索法は，O(log n)である。したがって，アが正解。

最後の 3 件目のレコードが格納されるときには，衝突が起こらないためには 1，28-7（正解）ウ。

9 個のデータを 10 進数に変換し，ハッシュ値を求める。

件目両方のキー値の 1 の位が異なる必要があるため，衝突しない確率は 8／10 に・1A )h =26) 10 より，mod( 26, 8 ) = 2・35 )h =53) 10 より，mod( 53, 8 ) = 5なる。

・3B )h =59) 10 より，mod( 59, 8 ) = 3・54 )h =84) 10 より，mod( 84, 8 ) = 4

したがって，3 件のレコードすべてが衝突しない確率は，「1，2 件目が衝突しな・8E )h =142) 10 より，mod( 142, 8 ) = 6・A1 )h =161) 10 より，mod( 161, 8 ) = 1・AF )h =175) 10 より，mod( 175, 8 ) = 7い確率」と「1，2 件目と 3 件目が衝突しない確率」の積なので，(9／10)×(8／10)＝0.72 となる，したがって，ウが正解。

9-1（正解）ア。

バブルソートのアルゴリズムである。行 2～3 の処理が初めて終了

字列に分割した後，隣り合う要素ごとに整列と併合を繰り返しながら整列を行う

したとき，A[ 1 ] が最小値になる。したがって，アが正解。
9-2

手法がマージソートである。したがって，エが正解。

（正解）ウ。

10-2（正解）エ。

ア

10-3（正解）イ。

イ

クイックソートは，基準の値を決めて，基準より小さい値を前に，基準より大きい値を後ろに入れ替える方法であるので，誤り。

外側ループ：1 から n－1 まで反復，内側ループは， i＋1 から n まで反復。

選択ソートは，データの中で最も小さいものを探して交換する方法であるの

i が 1 の時，内側ループは， j ＝ 2, 3, 4, …, n－1, n まで反復（ n － 1 回）。

で，以下のようになる。したがって，誤り。

i が 2 の時，内側ループは， j ＝ 3, 4, …, n－1, n まで反復（ n － 2 回）。
i が 3 の時，内側ループは， j ＝ 4, …, n－1, n まで反復（ n － 3 回）。

( 4, 1, 3, 2 )ウ( 1, 4, 3, 2 )最小値 1 と 4 を交換

・・・( 1, 2, 3, 4 )最小値 2 と 4 を交換

i が n－1 の時，内側ループは， j ＝ n （１回）。

挿入ソートは，データの整列部分の適切な位置に未整列の部分の先頭の値をしたがって，「＊印の処理（比較）」は，挿入していく方法であるので，以下のようになる。したがって，正解。

1 ＋ 2 ＋ 3 ＋ … ＋ n－1 ＝ n（ n－１）／2 となり，イが正解。

( 4, 1, 3, 2 )

エ

10-4

( 1, 4, 3, 2 )1 を 4 の前に挿入

手順に沿って整列を行うと次のようになる。

( 1, 3, 4, 2 )

3 を 1 と 4 の間に挿入(1) H←9÷3＝3( 1, 2, 3, 4 )

2 を 1 と 3 の間に挿入(2) 要素ごとがたがいに 3 つずつ離れた要素からなる 3 つの部分文字列に分解し，バブルソートは，隣り合うデータを比較し，順番が逆の場合は交換する方法

それぞれ整列を行う。

であるので，以下のようになる。したがって，誤り。

［部分列 1］7, 3, 4→ 整列 → 3, 4, 7

［部分列 2］2, 1, 5→ 整列 → 1, 2, 5

［部分列 3］8, 9, 6→ 整列 → 6, 8, 9

( 4, 1, 3, 2 )( 1, 4, 3, 2 )

4 と 1 を交換

( 1, 3, 4, 2 )4 を 3 を交換

(3) H←3÷3＝1( 1, 3, 2, 4 )

4 を 2 を交換

(4) H≠0 なので 2 に戻る。

( 1, 2, 3, 4 )

3 を 2 を交換

(5) 要素ごとがたがいに 1 つずつ離れた要素からなる 3,4,7,1,2,5,6,8,9 を整列し，9-3（正解）エ。

9-4（正解）ウ。

・・・

1 回目

1,2,3,4,5,6,7,8,9 とする。
(6) H←1÷3＝0（小数点未満切り捨て）

隣り合うデータを比較し，必要であれば交換を行うという一連の・・・

2 回目

操作を(n – 1)回行う。全体の比較回数は， (n - 1) + ( n - 2) + ・・・＋ 1 = n

この時点で H が 0 になるためデータ列の整列は完了する。

(n - 1) / 2 となる。したがって，ウが正解。

したがって(3)の処理が繰り返される回数は 2 回となるので，アが正解。
10-5

10-1（正解）ア。

（正解）ア。

このアルゴリズムは，データ群を，枢軸（pivot）より大きいデー（正解）エ。

タ群と小さいデータ群とに分割し，それぞれのデータ群に対して要素が一つにな

図の整列過程を見ると，大きさが 1 の部分文字列の併合を繰り返して最終的な整るまで，同じ操作を再帰的に適用するものである。

列済み文字列にしていることがわかる。このように整列対象を大きさ 1 の部分文

10-6（正解）ア。

10-7（正解）ウ。