平成８年度 春期 第二種情報処理技術者試験 午後 ［更新日］1996.06.04 次の表に従って解答してください。 ┏━━━━┯━━━━━┯━━━━━┯━━━━━━┯━━━━━━━┯━━━━━━━┓ ┃問題番号│問１、問２│問３〜問６│問７〜問１０│問１１〜問１４│問１５〜問１７┃ ┠────┼─────┼─────┼──────┼───────┼───────┨ ┃選択方法│ 必須 │ ２問選択 │ １問選択 │ １問選択 │ １問選択 ┃ ┠────┼─────┴─────┴──────┴───────┴───────┨ ┃試験方法│ １３：００〜１５：３０ １５０分 ┃ ┗━━━━┷━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ 平成８年度 春期 第二種 午後 問1〜問2 ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃次の問１，問２は必須問題です。全問解答してください。 ┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ 問1 次の流れ図の説明及び流れ図を読んで，設問に答えよ。 〔流れ図の説明〕 配列Ａ(１)〜Ａ(ｎ)に格納されている正の整数データを，ハッシュ法を用いてテー ブルに登録する処理の流れ図である。 ハッシュ法は，表の探索及び表へのエントリの登録，更新を効率よく行う際などに 用いられる手法の一つである。この手法はハッシュ関数と呼ぶ計算式を用いて，対象 データを限定された範囲の値（ハッシュ値）に変換し，この値を利用してテーブル上 の格納位置を決定する。ここではハッシュ関数として，次の式を用いる。 ハッシュ値＝整数データ値を15で割った余り＋１ ハッシュ法の特徴は，異なるデータのハッシュ値が等しくなる場合がある（これを 衝突という）ことである。この流れ図では，衝突が生じた場合の解決方法として，ハッ シュ値が等しいデータ同士をチェーンでつなぐ方式を用いている。 テーブルは図に示すように，整数データ（data）とチェーン（chn）の二つの要素か らなるレコードの配列で構成されている。テーブルの先頭15レコード（添字の値が １から15まで）は，ハッシュ値が各添字の値に等しい最初の整数データを格納する ための領域である。添字が16以降のレコードは，ハッシュ値が等しい2個目以降の後 続データを発生した順に格納するための領域である。 テーブル（ data 及び chn ）の初期値として，すべての要素に0を格納しておく。 ハッシュ値の等しいデータがある場合には，後続データを格納した場所の添字の値を チェーンに格納する。 例えば，図は配列Aに格納されている四つの整数データ（75，100，253，355）を 順にテーブルへ登録した状態を示したものである。整数データ100及び355はハッシュ 値が11で同じ値となり，整数データ100のレコードのチェーンには整数データ355の レコードの添字の値16が格納されている。 設問 流れ図中の[ ]に入れる正しい答えを，解答群の中から選ベ。 aに関する解答群 a 答エ ア ０ イ １ ウ 15 エ 16 オ ｎ b，cに関する解答群 b 答アc 答カ ア data（hash） イ data（j） ウ data（k） エ chn（hash） オ chn（j） カ chn（k） キ k ク hash 問2 次の流れ図の説明及び流れ図を読んで，設問１，２に答えよ。 〔流れ図の説明〕 二つの駅名（駅名1，駅名2）を受け取り，それらの駅間の運賃と特急料金の合計 料金を求める。 (１) まず駅名1と駅名2を，図1の駅名表を検索して駅番号に変換する。駅名表のｉ 番目の要素（駅名表(i)）に入っている駅名の駅番号をiとする。 駅名1，駅名2及び駅名表の各要索は8文字の文字列で，駅名が8文字に満たな い場合は右端に空白文字が埋められている。 (２) 次に運賃及び特急料金を，図2の料金表を検索して求める。 料金表の要素は，上からi番目，左からj番目のものを，料金表(i,j)で参照す る。 図2に示すように，料金表の左下部分の各要素には対応する駅番号間の運賃が， 右上部分の各要素には特急料金が格納されている。例えば，駅番号2と3の間の運 賃は料金表（3，2）に，特急料金は料金表（2，3）に格納されている。 対角線上の要索の値は0とする。 設問1 駅名変換サブルーチンにおいて，駅名“ハカタ△△△△△”を駅番号に変換 するとき，流れ図の(c)の部分は何回実行されるか，解答群の中から選ベ。 解答群 答ウ ア ０ イ １ ウ Ｎ−１ エ Ｎ オ Ｎ＋１ 設問2 流れ図に次の2点の変更を加える。 変更1：流れ図は，駅名1又は駅名2が駅名表の中に存在しない場合のことが 考慮されていない。駅名1又は駅名2が駅名表の中に存在しない場合 はエラーメッセージを表示するように変更する。 変更2：合計料金ではなく，運賃と特急料金を別々に求めるように変更する。 この変更のために，流れ図の(a)と(b)の部分を書き換える。 (a)の部分は次のように書き換えた。 ┌------┐ (1) 流れ図の(b)の中の条件式（｜ ｜の部分）はどう書き換えたらよいか。 解答群の中から選ベ。 └------┘ 解答群 答カ ア （駅名表（x）＝駅名）かつ（x＜N） イ （駅名表（x）＝駅名）かつ（x＞N） ウ （駅名表（x）＝駅名）かつ（x≦N） エ （駅名表（x）＝駅名）かつ（x≧N） オ （駅名表（x）＝駅名）又は（x＜N） カ （駅名表（x）＝駅名）又は（x＞N） キ （駅名表（x）＝駅名）又は（x≦N） ク （駅名表（x）＝駅名）又は（x≧N） ┌────┐ （2）│ │に入れる正しい答えを，解答群の中から選ベ。 └────┘ 解答群 答エ ア ｉ＝ｊ イ ｉ≠ｊ ウ ｉ＜ｊ エ ｉ＞ｊ 戻る 次頁：問3〜問6