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

PR広告

平成27年度秋基本情報技術者試験 午後問8 データ構造及びアルゴリズム 設問1

TOP :

平成27年度秋基本情報技術者試験 午後問8 データ構造及びアルゴリズム

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

〔プログラムの説明〕

 関数 BMMatch は、Boyer-Moor-Horspool法(以下、BM法という)を用いて、文字列検索を行うプログラムである。BM法は、検索文字列の末尾の文字から先頭に向かって、検索対象の文字列(以下、対象文字列)と1文字ずつ順に比較していくことで照合を行う。比較した文字が一致せず、照合が失敗した際には、検索文字列中の文字の情報を利用して、次に照合を開始する対象文字列の位置を決定する。このようにして明らかに不一致となる照合を省き、高速に検索できる特徴がある。

(1) 対象文字列をText[ ]、検索文字列をPat[ ]とする。ここで、配列の添字は1から始まり、文字列Text[ ]のi番目の文字はText[i]と表記される。Pat[ ]についても同様にi番目の文字はPat[i]と表記される。また、対象文字列と検索文字列は、英大文字から構成される。

 例えば、対象文字列Text[ ]が"ACBBMACABABC"、検索文字列Pat[ ]が"ACAB"の場合の例を図1に示す。

平成27年度秋応用情報技術者試験午後過去問8 データ構造及びアルゴリズム

(2) 関数 BMMatch では、照合が失敗すると、次に照合を開始する位置まで検索文字列を移動するが、その移動量を格納した要素数26の配列Skip[ ]をあらかじめ作成しておく。Skip[1]に文字"A"に対応する移動量を、Skip[2]に文字"B"に対応する移動量を格納する。このように、Skip[1]~Skip[26]に文字"A"~"Z"に対応する移動量を格納する。ここで、検索文字列の長さをPatLenとすると、移動量は次のようになる。

 ① 検索文字列の末尾の文字Pat[PatLen]にだけ現れる文字と、検索文字列に現れない文字に対応する移動量は、PatLenである。

 ② 検索文字列のPat[1]からPat[PatLen-1]に現れる文字に対応する移動量は、その文字が、検索文字列の末尾から何文字目に現れるかを数えた文字数から1を引いた値とする。ただし、複数回現れる場合は、最も末尾に近い文字に対応する移動量とする。

(3) 図1で示したPat[ ]の例の場合、次の①~④に示すように、Skip[ ]は図2のとおりになる。

 ① 文字"A"は検索文字列の末尾から2文字目(Pat[3])と4文字目(Pat[1])に現れるので、末尾に近いPat[3]に対応する移動量の1(=2-1)となる。

 ② 文字"B"は検索文字列の末尾の文字にだけ現れるので、移動量はPatLen(=4)となる。

 ③ 文字"C"は検索文字列の末尾から3文字目(Pat[2])に現れるので、移動量は2(=3-1)となる。

 ④ "A"、"B"及び"C"以外の文字については検索文字列に現れないので、移動量はPatLen(=4)となる。

平成27年度秋応用情報技術者試験午後過去問8 データ構造及びアルゴリズム

(4) 図1の例で照合する場合の手順は、次の①~⑨となり、その流れを図3に示す。この例では、PatLen=4なので、検索文字列の末尾の文字はPat[4]である。

平成27年度秋応用情報技術者試験午後過去問8 データ構造及びアルゴリズム

 ① Text[4]とPat[4]を比較する。Text[4]とPat[4]は同じ文字"B"である。

 ② Text[3]とPat[3]を比較する。Text[3]の"B"とPat[3]の"A"は異なる文字である。

 ③ ①で検索文字列の末尾の文字Pat[4]と比較したText[4]を基準に、Text[4]の文字"B"に対応する移動量であるSkip[2]の値4だけPat[ ]を右側に移動し、Text[8]とPat[4]の比較に移る。

 ④ Text[8]とPat[4]を比較する。Text[8]の"A"とPat[4]の"B"は異なる文字である。

 ⑤ ④で検索文字列の末尾の文字Pat[4]と比較したText[8] を基準に、Text[8]の文字"A"に対応する移動量であるSkip[1]の値1だけPat[ ]を右側に移動し、Text[9]とPat[4]の比較に移る。

 ⑥ Text[9]とPat[4]を比較する。Text[9]とPat[4]は同じ文字"B"である。

 ⑦ Text[8]とPat[3]を比較する。Text[8]とPat[3]は同じ文字"A"である。

 ⑧ Text[7]とPat[2]を比較する。Text[7]とPat[2]は同じ文字"C"である。

 ⑨ Text[6]とPat[1]を比較する。Text[6]とPat[1]は同じ文字"A"である。

 ⑥~⑨の比較で、対象文字列 Text[ ] の連続した一部分が検索文字列 Pat[ ] に完全に一致したので、検索は終了する。

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

 関数 BMMatch の引数と返却値の仕様は、次のとおりである。

平成27年度秋応用情報技術者試験午後過去問8 データ構造及びアルゴリズム

 関数 BMMatch では、次の関数 Index を使用する。

〔関数 Index の仕様〕

 引数にアルファベット順でn番目の英大文字を与えると、整数n(1 ≦ n ≦ 26)を返却値とする。

【プログラム】

○整数型関数: BMMatch(文字型: Text[], 整数型: TestLen, 文字型: Pat[], 整数型: PatLen)

○整数型: Skip[26], PText, PPat, PLast, I

■I: 1, I ≦ 26, 1
|・Skip[I] ← a
■
■I: 1, I ≦ PatLen - 1, 1 // ← γ
|・Skip[Index(Pat[I])] ← b
■
・PLast ← PatLen
■PLast ≦ TextLen
|・PText ← PLast // α
|・PPat ← PatLen
|■Text[PText] = Pat[PPat]
||▲PPat = 1 // β
|||・return (PText)
||▼
||・PText ← PText - 1
||・PPat ← PPat - 1
|■
|・PLast ← PLast + Skip[Index(Text[PLast])]
■
・return (-1)

設問1

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

a、b に関する解答群

  • ア 0
  • イ 1
  • ウ I - PatLen
  • エ PatLen
  • オ PatLen - 1
  • カ PatLen - I

解説

設問1は問題文の...

(2) 関数 BMMatch では、照合が失敗すると、次に照合を開始する位置まで検索文字列を移動するが、その移動量を格納した要素数26の配列Skip[ ]をあらかじめ作成しておく。Skip[1]に文字"A"に対応する移動量を、Skip[2]に文字"B"に対応する移動量を格納する。このように、Skip[1]~Skip[26]に文字"A"~"Z"に対応する移動量を格納する。ここで、検索文字列の長さをPatLenとすると、移動量は次のようになる。

 ① 検索文字列の末尾の文字Pat[PatLen]にだけ現れる文字と、検索文字列に現れない文字に対応する移動量は、PatLenである。

 ② 検索文字列のPat[1]からPat[PatLen-1]に現れる文字に対応する移動量は、その文字が、検索文字列の末尾から何文字目に現れるかを数えた文字数から1を引いた値とする。ただし、複数回現れる場合は、最も末尾に近い文字に対応する移動量とする。

に関連しています。

aの解説

 ① 検索文字列の末尾の文字Pat[PatLen]にだけ現れる文字と、検索文字列に現れない文字に対応する移動量は、PatLenである。

が、aに該当します。

Skip[1]からSkip[26]にPatLenの値を入れ初期化します。

「I: 1, I ≦ 26, 1」は、アルファベット26個分ループします。

Skip[I] ← PatLen // PatLenで初期化

aにはエが入ります。

bの解説

 ② 検索文字列のPat[1]からPat[PatLen-1]に現れる文字に対応する移動量は、その文字が、検索文字列の末尾から何文字目に現れるかを数えた文字数から1を引いた値とする。ただし、複数回現れる場合は、最も末尾に近い文字に対応する移動量とする。

が、bに該当します。「移動量は、その文字が、検索文字列の末尾から何文字目に現れるかを数えた文字数から1を引いた値とする。ただし、複数回現れる場合は、最も末尾に近い文字に対応する移動量とする。」とあるので、bには「カ PatLen - I」が入ります!

abの解答を確かめるために、(3)の例をもとに、アルゴリズムを試してみます。

(3) 図1で示したPat[ ]の例の場合、次の①~④に示すように、Skip[ ]は図2のとおりになる。

 ① 文字"A"は検索文字列の末尾から2文字目(Pat[3])と4文字目(Pat[1])に現れるので、末尾に近いPat[3]に対応する移動量の1(=2-1)となる。

 ② 文字"B"は検索文字列の末尾の文字にだけ現れるので、移動量はPatLen(=4)となる。

 ③ 文字"C"は検索文字列の末尾から3文字目(Pat[2])に現れるので、移動量は2(=3-1)となる。

 ④ "A"、"B"及び"C"以外の文字については検索文字列に現れないので、移動量はPatLen(=4)となる。

平成27年度秋応用情報技術者試験午後過去問8 データ構造及びアルゴリズム

■I: 1, I ≦ 26, 1
|・Skip[I] ← PatLen // a
■

ここのループでは、アルファベット26個分ループし、検索文字列Pat[]の長さPatLen(=4)を入力し初期化します。

Skip[1] = 4, Skip[2] = 4, Skip[3] = 4, Skip[4] = 4, ... Skip[26] = 4,

となります!

■I: 1, I ≦ PatLen - 1, 1 
|・Skip[Index(Pat[I])] ← PatLen - I // b
■

ここのループではPat[1] = A, Pat[2] = C, Pat[3] = A, Pat[4] = Bの場合、PatLen = 4なので、I = 1から I = PatLen - 1 = 3までループします。

I = 1

Skip[Index(Pat[1])] ← PatLen - 1

Pat[1] = A, PatLen = 4なので、Index(A) = 4 - 1 = 3

Skip[Index(A)] = 3

Index(A) = 1 となるので(Index()はそのアルファベットの順番をかえします。Aなら1, Bなら2, Zなら26)

従って、Skip[1] = 3

I = 2

Skip[Index(Pat[2])] ← PatLen - 2

Pat[2] = C, PatLen = 4なので、Index(C) = 4 - 2 = 2

Skip[Index(C)] = 2

Index(C) = 3 となるので(Index()はそのアルファベットの順番をかえします。Cなら3)

従って、Skip[3] = 2

I = 3

Skip[Index(Pat[3])] ← PatLen - 3

Pat[3] = A, PatLen = 4なので、Index(A) = 4 - 3 = 1

Skip[Index(A)] = 1

Index(C) = 1 となるので(Index()はそのアルファベットの順番をかえします。Aなら1)

従って、Skip[1] = 1

この部分が問題文の「複数回現れる場合は、最も末尾に近い文字に対応する移動量とする。」になります。

ここのループではPat[1] = A, Pat[2] = C, Pat[3] = A, Pat[4] = Bの場合はAが2つ出てきますが、末尾に近いPat[3]に対応する移動量となります!

平成27年度秋基本情報技術者試験 午後 問8 データ構造及びアルゴリズム 目次

平成27年度秋基本情報技術者試験 午後 目次

業務で書いたことがないプログラミング言語の解説は控えさせていただきますので、解説はありません。

TOP :

タグ: ,,,

PR広告

フェイスブックコメント

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

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

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

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

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

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

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

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

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