基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成26年 秋期 基本情報技術者 午後 問08
問08   必須問題

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

 二つの文字列の差異を測る指標に編集距離がある。編集距離の概念は,文書比較や 検索キーワードの候補の提示などに用いられている。編集距離とは,1文字の追加操作又は 削除操作を繰り返し適用し,ある文字列を別の文字列に変換するのに必要な最小の操作回数である。 例えば文字列 "abcabba" を文字列 "cbabac" に変換する場合,図1に示す操作1〜5によって変換が 完了する。図1は,最小の操作回数で変換する一例を示しており,編集距離は5となる。

図1 文字列 "abcabba" を文字列 "cbabac" に変換する場合の例

 関数 CalcEditDistance は,二つの文字列間の編集距離を返す関数である。

(1) 変換元の文字列を Str1[],変換先の文字列を Str2[] とする。また, 配列の添字は0から始まり,文字列 Str1[] の i 番目の文字は Str1[i−1] と表記する。 したがって,Str1[] = "abcabba" の場合,1番目の文字 = Str1[Ø]= "a", 2番目の文字 = Str1[1] = "b" となる。Str2[] についても同様である。

(2) 関数 CalcEditDistance は,エディットグラフと呼ばれるグラフの最短距離取得問題の 考え方に基づいて,編集距離を求めている。編集距離の求め方は次のとおりである。

@ 次の手順で,xy 平面上にエディットグラフを作成する。ここで,Str1Len は Str1[] の文字数, Str2Len は Str2[] の文字数である。 (a) Ø ≦ X ≦ Str1Len を満たす全ての整数 X に対して,点 (X,Ø) から点 (X,Str2Len) に線分を引く。

(b) Ø ≦ Y ≦ Str2Len を満たす全ての整数 Y に対して,点 (Ø,Y) から点 (Str1Len,Y) に線分を引く。

(C) Ø ≦ X < Str1Len,Ø ≦ Y < Str2Len を満たす全ての整数 X,Y の組に対して, Str1[X] と Str2[Y] が同一の文字の場合,点(X,Y)から点(X+1,Y+1)に線分を引く。

A エディットグラフを構成する線分をたどって,点(Ø,Ø)から点(Str1Len,Str2Len)へ移動する 経路を考える。 点(X,Y)から点(X+1,Y)又は点(X,Y+1)への移動距離を1、 点(X,Y)から点(X+1,Y+1)への移動距離を0としたときの,点(Ø,Ø)から点(Str1Len,Str2Len) までの短移動距離が編集距離となる。

(3) Str1[]="abcabba",str2[]="cbabac" の場合のエディットグラフを図2の左に示す。 この場合に,最短短移動距離となる経路の一つを図2の右にで示す。

図2 Strl[]="abcabba",Str2[]="cbabac" の場合の
エディットグラフ(左)と最短移動距離となる経路の例(右)

(4) 関数 CalcEditDistance では,点(Ø,Ø)から点(X,Y)への最短移動距離を D[X,Y] に求めている。D[X,Y] は,既に算出されている D[X−1,Y−1], D[X,Y−1],D[X−1,Y] を用いて求めることができる。これによって編集距離を算出している。

〔関数 CalcEditDistance の引数と返却値〕

 関数 CalcEditDistance の引数の仕様は,次のとおりである。各配列の添字は,0 から始まる。

 関数 CalcEditDistance では,次の関数 Min を使用している。

〔関数 Min の仕様〕

 引数として与えられた二つ以上の整数値の中で最も小さい値を返却値とする。

〔プログラム〕

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

a に関する解答群

ア Str1[X−1] = Str2[Y−1]

イ Str1[X−1] ≠ Str2[Y−1]

ウ Str1[X] = Str2[Y]

エ Str1[X] ≠ Str2[Y]

オ Str1[X−1] = Str1[X] and Str2[Y−1] = Str2[Y]

カ Str1[X−1] ≠ Strl[x] and Str2[Y−1] ≠ Str2[Y]

b に関する解答群

ア D[0,Str2Len]

イ D[Str1Len,0]

ウ D[Str1Len,Str2Len]

エ D[Str1Len,Str2Len]+1

オ D[Str1Len−1,Str2Len−1]

カ D[Str1Len−1,Str2Len−1]+1

解答 a ←クリックすると正解が表示されます

解答 b ←クリックすると正解が表示されます

設問2 次の記述中の に入れる正しい答えを, 解答群の中から選べ。

 Str1[]="peace",Str2[]="people" の場合のエディットグラフは となる。
 CalcEditDistance("peace",5,"people",6) を実行した場合, 関数 CalcEditDistance が終了するまでに行α 回実行され, 行β 回実行される。また, 返却値は となる。 ここで,関数 CalcEditDistance 中の には正しい答えが入っているものとする。

c に関する解答群

d に関する解答群

ア 2         イ 4         ウ 6         エ 8

オ 10         カ 12         キ 14         ク 16

e に関する解答群

ア 14         イ 16         ウ 18         エ 20

オ 22         カ 24         キ 26         ク 28

f に関する解答群

ア 4         イ 5         ウ 6         エ 8

オ 8         カ 9         キ 10         ク 11

解答 c ←クリックすると正解が表示されます

解答 d ←クリックすると正解が表示されます

解答 e ←クリックすると正解が表示されます

解答 f ←クリックすると正解が表示されます


[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]