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

令和元年 秋期 基本情報技術者 午後 問08
問08   必須問題

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

 

〔プログラムの説明〕

 関数 BitapMatch は,Bitap 法を使って文字列検索を行うプログラムである。

 Bitap 法は,検索対象の文字列(以下,対象文字列という)と検索文字列の照合に, 個別の文字ごとに定義されるビット列を用いるという特徴をもつ。

 なお,本問では,例えば2進数の 16 ビット論理型の 定数 ØØØØØØØØØØØ1Ø1Ø1は, 上位の Ø を省略して“1Ø1Ø1”B と表記する。

 

(1) 関数 BitapMatch は,対象文字列を Text[] に,検索文字列を Pat[] に格納して呼び出す。 配列の要素番号は 1 から始まり,Text[] の i 番目の文字は Text[i] と表記する。 Pat[] についても同様に i 番目の文字は Pat[i] と表記する。対象文字列と検索文字列は, 英大文字で構成され,いずれも最長 16 文字とする。

 対象文字列 Text[] が“AACBBAACABABAB”,検索文字列 Pat[] が“ACABAB”の場合の格納例を, 図1に示す。

 

図1 対象文字列と検索文字列の格納例

 

(2) 関数 BitapMatch は,関数 GenerateBitMask を呼び出す。

 関数 GenerateBitMask は,文字“A”〜“Z”の文字ごとに,検索文字列に応じた ビット列(以下,ビットマスクという)を生成し,要素数 26 の 16 ビット論理型配列 Mask[] に格納する。 Mask[1] には文字“A”に対するビットマスクを,Mask[2] には文字“B”に対するビットマスクを格納する。 このように Mask[1] 〜 Mask[26] に文字“A”〜“Z”に対応するビットマスクを格納する。

 関数 GenerateBitMask は,Mask[] の全ての要素を“Ø”B に初期化した後, 1 以上で Pat[] の文字数以下の全ての i に対して,Pat[i] の文字に対応する Mask[] の要素で ある Mask[Index(Pat[i])] に格納されている値の,下位から数えて i 番目のビットの値を 1 にする。

 関数 Index は,引数にアルファベット順で n 番目の英大文字を設定して呼び出すと, 整数 n( 1 ≦ n ≦26 )を返す。

 

(3) 図1で示した,Pat[] が“ACABAB”の例の場合,関数 GenerateBitMask を実行すると, Mask[] は図2のとおりになる。

 

図2 図1で示した Pat[] に対する Mask[] の値

(4) 関数 GenerateBitMask の引数と返却値の仕様は,表1のとおりである。

 

表1 関数 GenerateBitMask の引数と返却値の仕様

 

〔プログラム1〕

 

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

 

a に関する解答群

 

b に関する解答群 “Ø”B

“1”B

“1”B を PatLen ビットだけ論理左シフトした値

“1”B を ( PatLen −1 )ビットだけ論理左シフトした値

“1111111111111111”B

 

c に関する解答群 “1”Bを( i − 1 )ビットだけ論理左シフトした値

“1”Bを i ビットだけ論理左シフトした値

“1”Bを( PatLen− 1 )ビットだけ論理左シフトした値

“1”Bを PatLen ビットだけ論理左シフトした値

“1”B

 

〔関数 BitapMatch の説明〕

(1) Text[] と Pat[] を受け取り,Text[] の要素番号の小さい方から Pat[] と一致する文字列を検索し, 見つかった場合は,一致した文字列の先頭の文字に対応する Text[] の要素の要素番号を返し,見つからなかった場合は,−1 を返す。

(2) 図1の例では,Text[7] 〜 Text[12] の文字列が Pat[] と一致するので,7 を返す。

(3) 関数 BitapMatch の引数と返却値の仕様は,表2のとおりである。

 

表2 関数 BitapMatch の引数と返却値の仕様

 

〔プログラム2〕

 

基本情報技術者試験


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

 

 図1で示したとおりに,Text[] と Pat[] に値を格納し,関数 BitapMatch を実行した。 プログラム2の行βを実行した直後の変数 i と配列要素 Mask[Index(Text[i])] と変数 Status の値の遷移は, 表3のとおりである。

 例えば,i が 1 のときに行βを実行した直後の Status の値は“1”B であることから, i が 2 のときに行αを実行した直後の Status の値は, “1”B を 1 ビットだけ論理左シフトした“1Ø”Bと“1”B とのビットごとの論理和を取った “11”B となる。次に,i が 2 のときに行βを実行した直後の Status の値は, Mask[Index(Text[2])] の値が“1Ø1Ø1”B であることを考慮すると,d となる。

 同様に,i が 8 のときに行βを実行した直後の Status の値が“1Ø”B であるということに留意すると, i が 9 のときに行αを実行した直後の行βで参照する Mask[Index(Text[9])] の値は e であるので, 行βを実行した直後の Status の値は f となる。

 

表3 図1の格納例に対してプログラム2の行βを実行した直後の
配列要素 Mask[Index(Text[i])] と変数 Status の値の遷移

 

d 〜 f に関する解答群 ア “Ø”B     イ “1”B     ウ “1Ø”B     エ “11”B

オ “1ØØ”B    カ “1Ø1”B    キ “1Ø1Ø1”B

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

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

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

 

基本情報技術者試験


設問3 関数 GenerateBitMask の拡張に関する, 次の記述中の    に入れる正しい答えを, 解答群の中から選べ。ここで,プログラム3中の d には, 設問1の b の正しい答えが 入っているものとする。

 

 表4に示すような正規表現を検索文字列に指定できるように,関数 GenerateBitMask を拡張し, 関数 GenerateBitMaskRegex を作成した。

 

表4 正規表現

 

〔プログラム3〕

 Pat[] に“AC[BA]A[ABC]A”を格納して,関数 GenerateBitMaskRegex を呼び出した場合を考える。 この場合,文字 “A”に対応するビットマスクである Mask[1] は g となり, 関数 GenerateBitMaskRegex の返却値は h となる。 また,Pat[] に格納する文字列中において [] を入れ子にすることはできないが, 誤って Pat[] に“AC[B[AB]AC]A”を格納して関数 GenerateBitMaskRegex を呼び出した場合, Mask[1] は i となる。

 

g,i に関する解答群

 

h に関する解答群 ア 4      イ 6      ウ 9      エ 13
解答 g ←クリックすると正解が表示されます

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

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


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