Ｈ２３_ａｋｉ_ＡＰ_ＰＭ Ｑ０２ Ａｎｓ．
平成２３年 秋期 応用情報技術者 午後 問 ２
解答と解説
解答例・解答の要点
設問 １
ア ｃｏｕｎｔ は Ｎ より小さい
イ ｉｄｘ は Ｎ より大きい
ウ Ｈａｓｈ（ｋｅｙ）
エ ａｒｒａｙ［ｉｄｘ］．ｋｅｙ は ｋｅｙ と等しくない
設問 ２
（１）
シノニムの発生を考慮せずに配列要素を削除するから
または
データ取得の検索時に削除した要素で
終了していまい順次探しにいかないから
（２）
ア
関数Ｄｅｌｅｔｅ（）中の”ａｒｒａｙ［ｉｄｘ］．ｋｅｙ ← ０”の０を－１に変更する。
ウ
関数Ｇｅｔ（）中のｗｈｉｌｅ文の条件”（ａｒｒａｙ［ｉｄｘ］．ｋｅｙ は １ 以上）”かつ
（ａｒｒａｙ［ｉｄｘ］．ｋｅｙ は ９９９９９９９９９ 以下）”を
”（ａｒｒａｙ［ｉｄｘ］．ｋｅｙ は ０ 以外）”に変更する。
設問 ３
データの取得後に排他制御を開始するから
または
関数Ｇｅｔの排他制御が行われていないから
解説
設問 １
ア
上から１１行目のｅｎｄｗｈｉｌｅの前と後ろで、処理が分かれている。
上部はｃｏｕｎｔ や ｉｄｘ をインクリメントしているので
シノニム発生後の後続の空き位置を探しているもの推測
また、
１２行目の ｉｆ ～ は、関数の引数である ｉｎｆｏ を ａｒｒａｙ にセット
１４行目の ｅｌｓｅ で、オーバーフローの処理
４行目の ｗｈｉｌｅ のループ処理は
計算したハッシュ値の位置に有効値が入っている間は、
後続の空き位置を探している。
ハッシュ関数で算出した位置に有効なキー値が入っているか
かつ
Ｎ個の要素を全てチェック
５行目に ｃｏｕｎｔ ← ｃｏｕｎｔ＋１ があるので
ｃｏｕｎｔ が Ｎ まで処理されることになる。
したがって
ア
ｃｏｕｎｔ は Ｎ より小さい
イ
配列ａｒｒａｙの最後に到達しても未使用の配列要素がない場合には、
配列ａｒｒａｙの先頭に戻り、未使用の配列要素の検索を続ける。
配列の要素は Ｎ まで。
ｉｆ ～ の前に、ｉｄｘ ← ｉｄｘ＋１ があるので
ｉｄｘ が Ｎ より大きくなったら、ｉｄｘ ← １ にしなければならないので
イ ｉｄｘ は Ｎ より大きい
ウ
ｉｄｘ に 空欄 ウ を、設定している。
以降、配列の位置をさがしている。
空欄 ウ は、ハッシュ関数を取り扱っている場所になるので
ウ Ｈａｓｈ（ｋｅｙ）
エ
データを取得する関数なので、
探したい ｋｅｙ と、格納している ｋｅｙ が一致していない場合は
後続の位置をさがしているので
エ ａｒｒａｙ［ｉｄｘ］．ｋｅｙ は ｋｅｙ と等しくない
設問 ２
（１）
①あるデータを削除すると、別のデータの取得に失敗した。
削除するデータと取得できなくなるデータには関連があり、
再現方法を容易に分かった。
図３のデータ削除関数で、削除した要素の ｋｅｙ に ０ を格納している。
図２のデータ取得関数で、ｉｄｘ ← ０ は、データ取得失敗としている。
↓
ｋｅｙ は、１～９９９９９９９９９ の間で使用していて
０ は、データ取得失敗
したがって
（１）
シノニムの発生を考慮せずに配列要素を削除するから
または
データ取得の検索時に削除した要素で
終了していまい順次探しにいかないから
（２）
図３のデータ削除関数で、削除した要素の ｋｅｙ に ０ を格納している。
これでは、データがないのか、削除したのか、わからない。
そこで、０以外の数字を入れればいい。
よって
ア
関数Ｄｅｌｅｔｅ（）中の”ａｒｒａｙ［ｉｄｘ］．ｋｅｙ ← ０”の０を－１に変更する。
さらに
図２のデータ取得関数の ｗｈｉｌｅ の条件を変える必要がでてくる。
後続を検索したいので「０以外」に変更することで、対応できる。
したがって
ウ
関数Ｇｅｔ（）中のｗｈｉｌｅ文の条件”（ａｒｒａｙ［ｉｄｘ］．ｋｅｙ は １ 以上）”かつ
（ａｒｒａｙ［ｉｄｘ］．ｋｅｙ は ９９９９９９９９９ 以下）”を
”（ａｒｒａｙ［ｉｄｘ］．ｋｅｙ は ０ 以外）”に変更する。
設問 ３
図４では、ハッシュ関数で ｋｅｙ を加工したあとにロックをかけ
データを格納し、その後アンロックしている。
これでは
１行目でデータが格納済か確認するタイミングが、複数クライアントで
同じタイミングで発生した場合に問題が生じてしまう。
例えば
Ａ→Ｂの順番で処理するタイミングが近い場合
①データが確認済かを確認
②なければ格納
という順番なので、Ｂは重複して書き込まないはずになるが
Ａが書き込む前に、Ｂが空き確認すると、
Ｂから見ると空いている状態になり、
Ｂも書込みを行う流れになる。
この結果
ＡもＢも配列に重複して格納されてしまう。
よって
データの取得後に排他制御を開始するから
または
関数Ｇｅｔの排他制御が行われていないから
一覧に戻る
解答と解説
解答例・解答の要点
設問 １
ア ｃｏｕｎｔ は Ｎ より小さい
イ ｉｄｘ は Ｎ より大きい
ウ Ｈａｓｈ（ｋｅｙ）
エ ａｒｒａｙ［ｉｄｘ］．ｋｅｙ は ｋｅｙ と等しくない
設問 ２
（１）
シノニムの発生を考慮せずに配列要素を削除するから
または
データ取得の検索時に削除した要素で
終了していまい順次探しにいかないから
（２）
ア
関数Ｄｅｌｅｔｅ（）中の”ａｒｒａｙ［ｉｄｘ］．ｋｅｙ ← ０”の０を－１に変更する。
ウ
関数Ｇｅｔ（）中のｗｈｉｌｅ文の条件”（ａｒｒａｙ［ｉｄｘ］．ｋｅｙ は １ 以上）”かつ
（ａｒｒａｙ［ｉｄｘ］．ｋｅｙ は ９９９９９９９９９ 以下）”を
”（ａｒｒａｙ［ｉｄｘ］．ｋｅｙ は ０ 以外）”に変更する。
設問 ３
データの取得後に排他制御を開始するから
または
関数Ｇｅｔの排他制御が行われていないから
解説
設問 １
ア
上から１１行目のｅｎｄｗｈｉｌｅの前と後ろで、処理が分かれている。
上部はｃｏｕｎｔ や ｉｄｘ をインクリメントしているので
シノニム発生後の後続の空き位置を探しているもの推測
また、
１２行目の ｉｆ ～ は、関数の引数である ｉｎｆｏ を ａｒｒａｙ にセット
１４行目の ｅｌｓｅ で、オーバーフローの処理
４行目の ｗｈｉｌｅ のループ処理は
計算したハッシュ値の位置に有効値が入っている間は、
後続の空き位置を探している。
ハッシュ関数で算出した位置に有効なキー値が入っているか
かつ
Ｎ個の要素を全てチェック
５行目に ｃｏｕｎｔ ← ｃｏｕｎｔ＋１ があるので
ｃｏｕｎｔ が Ｎ まで処理されることになる。
したがって
ア
ｃｏｕｎｔ は Ｎ より小さい
イ
配列ａｒｒａｙの最後に到達しても未使用の配列要素がない場合には、
配列ａｒｒａｙの先頭に戻り、未使用の配列要素の検索を続ける。
配列の要素は Ｎ まで。
ｉｆ ～ の前に、ｉｄｘ ← ｉｄｘ＋１ があるので
ｉｄｘ が Ｎ より大きくなったら、ｉｄｘ ← １ にしなければならないので
イ ｉｄｘ は Ｎ より大きい
ウ
ｉｄｘ に 空欄 ウ を、設定している。
以降、配列の位置をさがしている。
空欄 ウ は、ハッシュ関数を取り扱っている場所になるので
ウ Ｈａｓｈ（ｋｅｙ）
エ
データを取得する関数なので、
探したい ｋｅｙ と、格納している ｋｅｙ が一致していない場合は
後続の位置をさがしているので
エ ａｒｒａｙ［ｉｄｘ］．ｋｅｙ は ｋｅｙ と等しくない
設問 ２
（１）
①あるデータを削除すると、別のデータの取得に失敗した。
削除するデータと取得できなくなるデータには関連があり、
再現方法を容易に分かった。
図３のデータ削除関数で、削除した要素の ｋｅｙ に ０ を格納している。
図２のデータ取得関数で、ｉｄｘ ← ０ は、データ取得失敗としている。
↓
ｋｅｙ は、１～９９９９９９９９９ の間で使用していて
０ は、データ取得失敗
したがって
（１）
シノニムの発生を考慮せずに配列要素を削除するから
または
データ取得の検索時に削除した要素で
終了していまい順次探しにいかないから
（２）
図３のデータ削除関数で、削除した要素の ｋｅｙ に ０ を格納している。
これでは、データがないのか、削除したのか、わからない。
そこで、０以外の数字を入れればいい。
よって
ア
関数Ｄｅｌｅｔｅ（）中の”ａｒｒａｙ［ｉｄｘ］．ｋｅｙ ← ０”の０を－１に変更する。
さらに
図２のデータ取得関数の ｗｈｉｌｅ の条件を変える必要がでてくる。
後続を検索したいので「０以外」に変更することで、対応できる。
したがって
ウ
関数Ｇｅｔ（）中のｗｈｉｌｅ文の条件”（ａｒｒａｙ［ｉｄｘ］．ｋｅｙ は １ 以上）”かつ
（ａｒｒａｙ［ｉｄｘ］．ｋｅｙ は ９９９９９９９９９ 以下）”を
”（ａｒｒａｙ［ｉｄｘ］．ｋｅｙ は ０ 以外）”に変更する。
設問 ３
図４では、ハッシュ関数で ｋｅｙ を加工したあとにロックをかけ
データを格納し、その後アンロックしている。
これでは
１行目でデータが格納済か確認するタイミングが、複数クライアントで
同じタイミングで発生した場合に問題が生じてしまう。
例えば
Ａ→Ｂの順番で処理するタイミングが近い場合
①データが確認済かを確認
②なければ格納
という順番なので、Ｂは重複して書き込まないはずになるが
Ａが書き込む前に、Ｂが空き確認すると、
Ｂから見ると空いている状態になり、
Ｂも書込みを行う流れになる。
この結果
ＡもＢも配列に重複して格納されてしまう。
よって
データの取得後に排他制御を開始するから
または
関数Ｇｅｔの排他制御が行われていないから
一覧に戻る
この記事へのコメント