東京理科大学 infoserv[更新日]2001.4.20


問4

 次のプログラムの説明,擬似言語の記述形式の説明及びプログラムを読んで, 設問 1 〜 3 に答えよ。

〔プログラムの説明〕

インデックス(索引)を用いて英和辞書を検索する副プログラムである。

(1) インデックスは,一次インデックスと二次インデックスで構成する。

(2) 二次インデックスは,辞書に登録されているすべての英単語, 及びその英単語が記載されているページ番号と行番号を, 英単語の昇順に格納したものである。 一次インデックスは,二次インデックスからある間隔で英単語を抜粋し, その二次インデックスへのポインタとともに格納したものである。 まず一次インデックスを検索し,その結果に従って二次インデックスを検索する。

(3) 図 1 のように,一次インデックスはキーポインタ からなるレコードの配列である。 二次インデックスはキー,ページ及びからなるレコードの配列である。 キーには英単語が,ポインタには二次インデックスの配列の要素番号が, ページにはページ番号が,には行番号がそれぞれ格納される。 配列の要素番号は 0 から始まる。

(4) 一次インデックスの要素数は変数一次要素数に, 二次インデックスの要素数は変数二次要素数に格納されている。

(5) 一次インデックスの要素番号 0 の要素のキーには空白が, ポインタには−1 が格納されている。


図1 一次インデックスと二次インデックスの例

(6) この副プログラムの引数を表に示す。

表 引数の仕様

変数名

入力/出力

意味

検索語

入力

検索したい英単語(空白は除く)。

返却値[ ]

出力

返却値 [ ] は配列である。
英単語が見つかった場合:
返却値 [0] にページ番号を,返却値 [1] に行番号を格納する。
英単語が見つからなかった場合:
返却値 [0] に−1 を格納する。

〔擬似言語の記述形式の説明〕

〔検索プログラム〕


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

解答群

ア 一致フラグ ← 1

イ 一致フラグ ← 2

ウ 添字 2 ← 一次[添字 1 ].ポインタ + 1

エ 添字 2 ← 一次[添字 1 + 1 ].ポインタ + 1

オ 添字 2 ← 一次[添字 1 − 1 ].ポインタ + 1

カ 添字 2 ← 二次要素数

キ 添字 2 ← 添字 2 + 1

ク 添字 2 ← 添字 2 − 1


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

各インデックスが図 2 の場合,“decided”を検索すると, プログラム中のαとβの処理は併せて 回実行される。 また,“decibel”を検索すると, 併せて 回実行される。


図2 一次インデックスと二次インデックスの一部

解答群

ア 4     イ 5     ウ 6     エ 198    オ 199

カ 200    キ 203    ク 204    ケ 205


設問3  二次インデックスから一次インデックスを作成するプログラムの処理部である。 プログラム中の に入れる正しい答えを, 解答群の中から選べ。
 ここで,二次要素数 > 一次要素数 > 1 とする。

〔一次インデックス作成プログラム〕

解答群

ア 一次要素数    イ 一次要素数 + 1    ウ 一次要素数 − 1

エ 二次要素数    オ 二次要素数 + 1    カ 二次要素数 − 1


東京理科大学 infoserv 戻る 次頁:問05