総視聴再生時間43万分以上(2017年5月13日現在)の動画で基本情報技術者試験の過去問&キーワード解説!スキマ時間に動画!〜これじょIT〜

PR広告

平成29年度春 基本情報技術者過去問 午後問8 データ構造及びアルゴリズム 設問1

次のプログラムの説明及びプログラムを読んで、設問1、2に答えよ。

副プログラム ShortestPath は、N個(N>1)の地点と、地点間を直接結ぶ経路及び距離が与えられたとき、出発地から目的地に至る最短経路とその距離を求めるプログラムである。最短経路とは、ある地点から別の地点へ最短距離で移動する際の経由地を結んだ経路である。副プログラム ShortestPath では、出発地の隣接地点から開始して、目的地に向かって最短距離を順次確定する。ある地点の隣接地点とは、その地点から他の地点を経由せずに直接移動できる地点のことである。

図1は、地点数Nが7の経路の例で、経路をグラフで表現したものである。図1において、丸は地点を示し、各地点には0から始まる番号(以下、地点番号という)が順番に割り当てられている。線分は地点間を直接結ぶ経路を示し、線分の上に示す数字はその距離を表す。また、経路上は、双方向に移動できる。

平成29年度春 基本情報技術者過去問 午後問8 データ構造とアルゴリズム

図1 地点数Nが7の経路の例

〔プログラムの説明〕

(1) 副プログラム ShortestPath の引数の仕様を、表1に示す。ここで、出発地から目的地までを結ぶ経路は、少なくとも一つ存在するものとする。また、配列の要素番号は、0から始まる。

表1 副プログラムShortestPathの引数の仕様

引数 データ型 入出力 説明
Distance[][] 整数型 入力 地点間の距離が格納されている2次元配列
nPoint 整数型 入力 地点数
sp 整数型 入力 出発地の地点番号
dp 整数型 入力 目的地の地点番号
sRoute[] 整数型 出力 出発地から目的地までの最短経路上の地点の地点番号を目的地から出発地までの順に設定する1次元配列
sDist 整数型 出力 出発地から目的地までの最短距離

(2) Distance[i][j](i=0, ..., nPoint-1; j=0, ..., nPoint-1)には、地点iから地点jまでの距離が格納されている。ただし、地点iと地点jが同一の地点の場合は0、地点iが地点jの隣接地点ではない場合は-1が格納されている。図1の例における配列 Distance の内容は、表2のとおりである。

表2 図1の例における配列Distanceの内容

i/j 0 1 2 3 4 5 6
0 0 2 8 4 -1 -1 -1
1 2 0 -1 -1 3 -1 -1
2 8 -1 0 -1 2 3 -1
3 4 -1 -1 0 -1 8 -1
4 -1 3 2 -1 0 -1 9
5 -1 -1 3 8 -1 0 3
6 -1 -1 -1 -1 9 3 0

(3) 行番号5~10では、変数、配列に初期値を格納する。

 ① 最短距離を返却する変数 sDist に初期値として∞(最大値を表す定数)を格納し、出発地から目的地までの最短距離が設定されていないことを示す。

 ② 最短経路を返却する要素数が nPoint である配列 sRoute の全ての要素に初期値として-1を格納し、最短経路上の地点の地点番号が設定されていないことを示す。

 ③ 出発地から各地点までの最短距離を設定する配列を pDist とする。pDist は1次元配列であり、要素数は nPoint である。配列 pDist の全ての要素に初期値として∞を格納する。

 ④ 出発地から各地点までの最短距離が確定しているかどうかを識別するための配列を pFixed とする。pFixed は1次元配列であり、要素数は nPoint である。配列 pFixed の全ての要素に初期値として false を格納し、最短距離が未確定であることを示す。最短距離が確定したときに true を設定する。例えば、出発地から地点iまでの最短距離が確定したとき、pFixed[i] は true となり、その最短距離は pDist[i] に設定されている。pFixed[i] が false の場合は、地点iまでの最短距離は未確定であり、pDist[i] の値は最短距離として確定されていない。

(4) 行番号11では、出発地から出発地自体への最短距離 pDist[sp] に0を設定する。

(5) 行番号12~39の最短経路探索処理では、出発地から各地点までの最短距離を算出しながら、最短経路を求める。

 ① 行番号13~22

 配列 pFixed を調べ、出発地から全ての地点までの最短距離が確定していれば、最短経路探索処理を抜けて(6)に進む。

 ② 行番号23~29

 出発地からの最短距離が未確定の地点の中で、出発地からの距離が最も短い地点を探し、その地点を sPoint とし、その地点の最短距離を確定する。

 ③ 行番号30~38

 各地点に対して(ア)、(イ)を実行し、①に戻る。

 (ア) 地点 sPoint の隣接地点であり、かつ、出発地からの最短距離が未確定であるかどうかを調べる。

 (イ) (ア)の条件を満たす地点jに関して、出発地から地点 sPoint を経由して地点jに到達する経路の距離を求め、その距離が既に算出してある pDist[j] よりも短ければ、pDist[j] 及び pRoute[j] を更新する。ここで、pDist[j] は、出発地から地点jまでの仮の最短距離となる。pRoute[j] には、そのときの、地点jの直前の経由地の地点番号を設定する。

(6) 行番号40~48では、出発地から目的地までの最短距離を sDist に、最短経路上の地点の地点番号を目的地から出発地までの順に配列 sRoute に設定する。

[プログラム]

(行番号)

1 ◯副プログラム: ShortestPath(整数型:Distance[][], 整数型:nPoint, 整数型:sp, 整数型:dp, 整数型:sRoute[], 整数型:sDist)

2 ◯整数型:pDist[nPoint], pRoute[nPoint]

3 ◯論理型:pFixed[nPoint]

4 ◯整数型:sPoint, i, j, newDist

5 ・sDist ← ∞ /* 出発地から目的地までの最短距離に初期値を格納する */

6 ◼︎i:0, i < nPoint, 1

7 |・sRoute[i] ← -1 /* 最短経路上の地点の地点番号に初期値を格納する */

8 |・pDist[i] ← ∞ /* 出発地から各地点までの最短経路に初期値を格納する */

9 |・pFixed[i] ← false /* 各地点の最短距離の確定状態に初期値を格納する */

10 ◼︎

11 ・pDist[sp] ← 0 /* 出発地から出発地点自体への最短距離に0を設定する */

12 ◼︎true /* 最短経路探索処理 */

13 |・i ← 0

14 |◼︎i < nPoint /* 未確定の地点を一つ探す */

15 ||▲not(pFixed[i])

16 |||・break /* 最内側の繰返しから抜ける */

17 ||▼

18 ||・i ← i + 1

19 |◼︎

20 |▲i = nPoint /* 出発地から全ての地点までの最短経路が確定 */

21 ||・break /* していれば、最短経路探索処理を抜ける */

22 |▼

23 |◼︎j:i+1, j < nPoint, 1 /* 最短距離がより短い地点を探す */

24 ||▲a and pDist[j] < pDist[i]

25 |||・i ← j

26 ||▼

27 |◼︎

28 |・sPoint ← i /* α */

29 |・pFixed[b] ← true /* 出発地からの最短距離を確定する */

30 |◼︎j:0, j < nPoint, 1

31 ||▲Distance[sPoint][j] > 0 and not(pFixed[j])

32 |||・newDist ← pDist[sPoint] + Distance[sPoint][j]

33 |||▲newDist < pDist[j]

34 ||||・pDist[j] ← newDist

35 ||||・pRoute[j] ← sPoint

36 |||▼

37 ||▼

38 |◼︎

39 ◼︎ /* β */

40 ・sDist ← pDist[dp]

41 ・j ← 0

42 ・i ← dp

43 ◼︎i ≒ sp

44 |・c ← i

45 |・i ← d

46 |・j ← j + i

47 ◼︎

48 ・c ← sp

設問1

プログラム中の に入れる正しい答えを、解答群の中から選べ。

a に関する解答群

  • ア:not(pFixed[i])
  • イ:not(pFixed[j])
  • ウ:pFixed[i]
  • エ:pFixed[j]

b に関する解答群

  • ア:dp
  • イ:nPoint
  • ウ:nPoint - 1
  • エ:sp
  • オ:sPoint

c, d に関する解答群

  • ア:pRoute[dp]
  • イ:pRoute[i]
  • ウ:pRoute[j]
  • エ:pRoute[sp]
  • オ:sRoute[dp]
  • カ:sRoute[i]
  • キ:sRoute[j]
  • ク:sRoute[sp]

設問1の解説

aは24行目、bは29行目にあります。このプログラムは[プログラムの説明] (5) ②に説明があります。

② 行番号23~29

出発地からの最短距離が未確定の地点の中で、出発地からの距離が最も短い地点を探し、その地点を sPoint とし、その地点の最短距離を確定する。

出発地からの最短距離が未確定である必要があるので判定します。

pFixed[]は最短距離が確定した時にtrueが設定される配列です。ここでは、pFixed[j]がfalseで最短距離が確定していない場合処理をするので、プログラムには「not(pFixed[j])」と記載します。

したがって、aに入るのは「イ not(pFixed[j])」です。

29行目は「出発地からの最短距離を確定する」とコメントにあります。

sPointは出発地からの距離が最も短い地点です。この地点での最短距離が確定したのでpFixed[sPoint] = trueとする必要があります。

したがって、bに入るのは「オ sPoint」です。

cは44行目と48行目にあり、dは45行目にあります。

[プログラムの説明] (6) に説明があります。

(6) 行番号40~48では、「出発地から目的地までの最短距離を sDist に、最短経路上の地点の地点番号を目的地から出発地までの順に配列 sRoute に設定する。」とあります。

44行目では「最短経路上の地点の地点番号を目的地から出発地までの順に配列 sRoute に設定」しています。sRoute[j]にiの値を代入します。

したがって、cに入るのは「キ sRoute[j]」です。

45行目では、次のiの値を格納します。次のiの値は、pRoute[i]です。

したがって、dに入るのは「イ pRoute[i]」です。

設問2

次の記述中の に入れる正しい答えを、解答群の中から選べ

図1において、出発地の地点番号 sp の値が0、目的地の地点番号 dp の値が6の場合について、プログラムの動きを追跡する。行番号12~39の最短経路探索処理の繰返しで、行番号28のαにおいて sPoint に代入された値は、繰返しの1回目は0、2回目は1、3回目はeとなる。また、行番号30~38の処理が終了した直後のβにおける配列 pDist と配列 pRoute の値を、表3に示す。最短経路探索処理の繰返しが3回目のときのβにおける配列 pDist の値はfとなり、配列 pRoute の値はgとなる。ここで、配列 pRoute の全ての要素には初期値として0が格納されているものとする。

表3 βにおける配列pDistと配列pRouteの値

最短経路探索処理の繰返し 配列 pDist 配列 pRoute
1回目 0, 2, 8, 4, ∞, ∞, ∞ 0, 0, 0, 0, 0, 0, 0
2回目 0, 2, 8, 4, 5, ∞, ∞ 0, 0, 0, 0, 1, 0, 0
3回目 f g
... ... ...

e に関する解答群

  • ア:2
  • イ:3
  • ウ:4
  • エ:5
  • オ:6

f に関する解答群

  • ア:0, 2, 8, 4, 5, 10, 14
  • イ:0, 2, 8, 4, 5, 10, ∞
  • ウ:0, 2, 8, 4, 5, 11, 14
  • エ:0, 2, 8, 4, 5, 11, ∞
  • オ:0, 2, 8, 4, 5, 12, 14
  • カ:0, 2, 8, 4, 5, 12, ∞

g に関する解答群

  • ア:0, 0, 0, 0, 1, 3, 0
  • イ:0, 0, 0, 0, 1, 3, 5
  • ウ:0, 0, 0, 0, 2, 2, 0
  • エ:0, 0, 0, 0, 2, 2, 5
  • オ:0, 0, 4, 0, 1, 2, 0
  • カ:0, 0, 4, 0, 2, 2, 5

設問2の解説

e, f, gの穴埋めです。

この問題はアルゴリズムのトレースをします。

動画と合わせて解説をします。

出発地の地点番号spの値が0、目的地の地点番号dpの値が6です。

【1回目のループ 12行目から39行目の最短経路探索処理】

i = 0

・14行目から19行目

ここでは未確定の地点を一つ探します。

i = 0から配列の大きさ分7(= nPoint)の範囲で探します。

pFixed[0]がfalseなので、16行目でbreakとなり、19行目終了時点でi = 0です。

・20行目から22行目

i = 0, nPoint = 7なので最短経路探索処理を継続します。

・23行目から29行目

pFixed[0], pFixed[1], pFixed[2], pFixed[3], pFixed[4], pFixed[5], pFixed[6]すべてfalseですが、pDist[j] < pDist[i]とならないので、i = 0のままです。

sPoint ← 0 となります。※問題文にある通り

pFixed[0/* = sPoint */] = trueとなります。

これは0地点での出発地からの最短距離を確定します。

・30行目から39行目

sPoint = 0, nPoint = 7の状態で、このループに入ります。

1回目のループ j = 0

Distance[0 /* = sPoint */][0 /* = j */] = 0 なので、1回目のループは終了します。

2回目のループ j = 1

Distance[0 /* = sPoint */][1 /* = j */] = 2

pFixed[1 /* = j */] = false

なので

newDist ← pDist[0 /* = sPoint */] + Distance[0 /* = sPoint */][1 /* = j */]

newDist = 0 + 2 = 2

となります。

newDist = 2, pDist[1] = ∞であることから

2 < ∞が成り立ち

pDist[1] = newDist /* = 2 */

pRoute[1] = sPoint /* = 0 */

となります。

3回目のループ j = 2

Distance[0 /* = sPoint */][2 /* = j */] = 8

pFixed[2 /* = j */] = false

なので

newDist ← pDist[0 /* = sPoint */] + Distance[0 /* = sPoint */][2 /* = j */]

newDist = 0 + 8 = 8

となります。

newDist = 8, pDist[2] = ∞であることから

2 < ∞が成り立ち

pDist[2] = newDist /* = 8 */

pRoute[2] = sPoint /* = 0 */

となります。

4回目のループ j = 3

Distance[0 /* = sPoint */][3 /* = j */] = 4

pFixed[3 /* = j */] = false

なので

newDist ← pDist[0 /* = sPoint */] + Distance[0 /* = sPoint */][3 /* = j */]

newDist = 0 + 4 = 4

となります。

newDist = 4, pDist[3] = ∞であることから

2 < ∞が成り立ち

pDist[3] = newDist /* = 4 */

pRoute[3] = sPoint /* = 0 */

となります。

5回目のループ j = 4

Distance[0 /* = sPoint */][4 /* = j */] = -1

pFixed[4 /* = j */] = false

なので、ループが終了します。

6回目のループ j = 5

Distance[0 /* = sPoint */][5 /* = j */] = -1

pFixed[5 /* = j */] = false

なので、ループが終了します。

7回目のループ j = 6

Distance[0 /* = sPoint */][6 /* = j */] = -1

pFixed[6 /* = j */] = false

なので、ループが終了します。

βに到達し、配列pDistと配列pRouteは次のようになります。

pDist = {0, 2, 8, 4, ∞, ∞, ∞}

pRoute = {0, 0, 0, 0, 0, 0, 0}

となります。※表3 βにおける配列pDistと配列pRouteの値 1回目にある通り


【2回目のループ 12行目から39行目の最短経路探索処理】

i = 1

・14行目から19行目

ここでは未確定の地点を一つ探します。

i = 0から配列の大きさ分7(= nPoint)の範囲で探します。

pFixed[0]がtrueとなるので次のループとなり、i = 1の時pFixed[1] = trueとなり、16行目でbreakとなり、19行目終了時点でi = 1です。

・20行目から22行目

i = 1, nPoint = 7なので最短経路探索処理を継続します。

・23行目から29行目

pFixed[0] = trueなので無視されpFixed[1], pFixed[2], pFixed[3], pFixed[4], pFixed[5], pFixed[6]がfalseですが、 pDist[j] < pDist[i]とならないので、i = 1のままです。

sPoint ← 1 となります。※問題文にある通り

pFixed[1/* = sPoint */] = trueとなります。

これは0地点での出発地からの最短距離を確定します。

・30行目から39行目

sPoint = 1, nPoint = 7の状態で、このループに入ります。

1回目のループ j = 0

Distance[1 /* = sPoint */][0 /* = j */] = 2

not(pFixed[0]) = false

なので、1回目のループは終了します。

2回目のループ j = 1

Distance[1 /* = sPoint */][1 /* = j */] = 0

not(pFixed[1]) = true

です。Distance[1 /* = sPoint */][1 /* = j */] > 0ではないのでループは終了します。

3回目のループ j = 2

Distance[1 /* = sPoint */][2 /* = j */] = -1

not(pFixed[2]) = true

です。Distance[1 /* = sPoint */][2 /* = j */] > 0ではないのでループは終了します。

4回目のループ j = 3

Distance[1 /* = sPoint */][3 /* = j */] = -1

not(pFixed[3]) = true

です。Distance[1 /* = sPoint */][3 /* = j */] > 0ではないのでループは終了します。

5回目のループ j = 4

Distance[1 /* = sPoint */][4 /* = j */] = 3

not(pFixed[3]) = true

なので

newDist ← pDist[1 /* = sPoint */] + Distance[1 /* = sPoint */][4 /* = j */]

newDist ← 2 + 3 = 5

pDist[4 /* = j */] = ∞

newDist < pDist[4]が成り立つので

pDist[4] = 5

pRoute[4] = 1

となります。

6回目のループ j = 5

Distance[1 /* = sPoint */][5 /* = j */] = -1

not(pFixed[5]) = true

です。Distance[1 /* = sPoint */][5 /* = j */] > 0ではないのでループは終了します。

7回目のループ j = 6

Distance[1 /* = sPoint */][6 /* = j */] = -1

not(pFixed[6]) = true

です。Distance[1 /* = sPoint */][6 /* = j */] > 0ではないのでループは終了します。

βに到達し、配列pDistと配列pRouteは次のようになります。

pDist = {0, 2, 8, 4, 5, ∞, ∞}

pRoute = {0, 0, 0, 0, 1, 0, 0}

となります。※表3 βにおける配列pDistと配列pRouteの値 2回目にある通り


【3回目のループ 12行目から39行目の最短経路探索処理】

i = 2

・14行目から19行目

ここでは未確定の地点を一つ探します。

i = 0から配列の大きさ分7(= nPoint)の範囲で探します。

pFixed[0], pFiexd[1]がtrueとなるので次のループとなり、i = 2の時pFixed[2] = trueとなり、16行目でbreakとなり、19行目終了時点でi = 2です。

・20行目から22行目

i = 2, nPoint = 7なので最短経路探索処理を継続します。

・23行目から29行目

j = 0の時pFixed[0] = true,

j = 1の時pFixed[1] = true

なので無視されます。

j = 2

pFixed[2] = false

pDist[2 /* = j */] = 8

pDist[2 /* = i */] = 8

であるので、iの値は変わりません。

j = 3

pFixed[3] = false

pDist[3 /* = j */] = 4

pDist[2 /* = i */] = 8

pDist[3] < pDist[2]が成り立つので

i ← j

で、i = 3となります。

j = 4

pFixed[4] = false

pDist[4 /* = j */] = 5

pDist[3 /* = i */] = 4

pDist[4] < pDist[3]が成り立たないので次のループ

j = 5

pFixed[5] = false

pDist[5 /* = j */] = ∞

pDist[3 /* = i */] = 4

pDist[5] < pDist[3]が成り立たないので次のループ

j = 6

pFixed[6] = false

pDist[6 /* = j */] = ∞

pDist[3 /* = i */] = 4

pDist[6] < pDist[3]が成り立たないので次のループ

sPoint ← 3 (= i) となります。eには3が入ります。

pFixed[3/* = sPoint */] = trueとなります。

これは0地点での出発地からの最短距離を確定します。

・30行目から39行目

sPoint = 3, nPoint = 7の状態で、このループに入ります。

1回目のループ j = 0

Distance[3 /* = sPoint */][0 /* = j */] = 4

not(pFixed[0]) = false

なので、1回目のループは終了します。

2回目のループ j = 1

Distance[3 /* = sPoint */][1 /* = j */] = -1

not(pFixed[1]) = false

なので、2回目のループは終了します。

3回目のループ j = 2

Distance[3 /* = sPoint */][2 /* = j */] = -1

not(pFixed[2]) = true

です。

Distance[3 /* = sPoint */][2 /* = j */] > 0ではないのでループは終了します。

4回目のループ j = 3

Distance[3 /* = sPoint */][3 /* = j */] = 0

not(pFixed[3]) = true

です。

Distance[3 /* = sPoint */][3 /* = j */] > 0ではないのでループは終了します。

5回目のループ j = 4

Distance[4 /* = sPoint */][4 /* = j */] = -1

not(pFixed[3]) = true

です。

Distance[4 /* = sPoint */][4 /* = j */] > 0ではないのでループは終了します。

6回目のループ j = 5

Distance[3 /* = sPoint */][5 /* = j */] = 8

not(pFixed[5]) = true

です。

Distance[3 /* = sPoint */][5 /* = j */] > 0なので

newDist ← pDist[3 /* = sPoint */] + Distance[3 /* = sPoint */][5 /* = j */]

newDist ← 4 + 8 = 12

newDist < pDist[5]が成り立つので

pDist[5] = 12 /* = newDist */

pRoute[5] = 3 /* = sPoint */

7回目のループ j = 6

Distance[3 /* = sPoint */][6 /* = j */] = -1

not(pFixed[6]) = true

です。

Distance[1 /* = sPoint */][6 /* = j */] > 0ではないのでループは終了します。

βに到達し、配列pDistと配列pRouteは次のようになります。

pDist = {0, 2, 8, 4, 5, 12, ∞} fの答えはカ

pRoute = {0, 0, 0, 0, 1, 3, 0} gの答えはア

となります。

PR広告

フェイスブックコメント

平成28年度秋 基本情報技術者試験 午後 テキスト・動画解説

平成28年度秋 基本情報技術者試験 午前 テキスト・動画解説

平成28年度春 基本情報技術者試験 午後 テキスト・動画解説

平成28年度春 基本情報技術者試験 午前 テキスト・動画解説

平成27年度秋 基本情報技術者試験 午後 テキスト・動画解説

平成27年度春 基本情報技術者試験 午後 テキスト・動画解説

平成27年度春 基本情報技術者試験 午前 テキスト・動画解説

平成26年度秋 基本情報技術者試験 午前 テキスト・動画解説

平成26年度春 基本情報技術者試験 午前 テキスト・動画解説