平成22年度秋季解答

問題1

後置表記法(逆ポーランド表記法)では、例えば、式Y＝(A－B)×CをYAB－C×＝と表現する。次の式を後置表記法で表現したものはどれか。

Y＝(A＋B)×(C－(D÷E))

ア	YAB＋C－DE÷×＝
イ	YAB＋CDE÷－×＝
ウ	YAB＋EDC÷－×＝
エ	YBA＋CD－E÷×＝

解答：イ

＜解説＞

1. Y＝(A＋B)×(C－(D÷E))の(A＋B)と(D÷E)を変換する。
   Y＝(AB＋)×(C－(DE)÷)
2. Y＝(AB＋)×(C－(DE)÷)のC－(DE)を変換する。
   Y＝(AB＋)×(C(DE)÷－)
3. Y＝(AB＋)×(C(DE)÷－)の×を変換する。
   Y＝(AB＋)(C(DE)÷－)×
   
4. Y＝(AB＋)(C(DE)÷－)×の＝を変換する。
   Y(AB＋)(C(DE)÷－)×＝
5. したがって、(イ)YAB＋CDE÷－×＝が正解である。
   

問題へ

問題2

a，b，c，dの4文字からなるメッセージを符号化してビット列にする方法として表のア～エの4通りを考えた。この表はa，b，c，dの各1文字を符号化するときのビット列を表している。メッセージ中でのa，b，c，dの出現頻度は、それぞれ50%，30%，10%，10%であること が分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって、ビット列の長さが最も短くなるものはどれか。

解答：ウ

＜解説＞

ア	×	「00」が"aa"なのか"c"なのか判別できないので誤りである。
イ	×	「010」が"ba"なのか"ac"なのか判別できないので誤りである。
ウ	○	符号化されたビット列から元のメッセージが一意に復号可能である。 (1×0.5) + (2×0.3) + (3×0.1) + (3×0.1)＝1.7⇒ビット列の長さは1.7ビット/文字
エ	×	符号化されたビット列から元のメッセージが一意に復号可能である。 全ての文字に2ビットの符号を割当てているのでビット列の長さは2ビット/文字である。

したがって、符号化されたビット列から元のメッセージが一意に復号可能であり、ビット列の長さが一番短いウが正解である。

問題へ

問題3

探索表の構成法を例とともにa～cに示す。探索の平均計算量が最も小さい探索手法の組合せはどれか。ここで、探索表のコードの空欄は表の空きを示す。

解答：ア

＜解説＞

[a コード順に格納した探索表：2分探索]

2分探索は、予めソートされたデータ列を二つに分けて、そのどちらに検索対象が含まれているか判断するという手順を再帰的に繰り返していく検索方法。
⇒aは、 コード順に格納されているので、2分探索法が適している。

[b コードの使用頻度順に格納した探索表：線形探索]

線形探索は、対象データを検索範囲のデータと先頭から順に1つずつ比較し、一致するものを検索する方法。
⇒bは、使用頻度順にならんでいるので先頭から順番に検索すると早く見つけることができるので、線形探索が適している。

[c コードから一意に決まる場所に格納した探索表：ハッシュ探索]

ハッシュ探索は、キーの値を基に格納先（記録媒体上）のアドレスを算出し、そのアドレス位置にあるデータを検索する方法。
⇒cは、コードから格納場所を探索するのでハッシュ探索が適している。

したがって、アが正解である。

問題へ

問題4

容量がa M バイトでアクセス時間がxナノ秒のキャッシュメモリと、容量がb Mバイトでアクセス時間がyナノ秒の主記憶をもつシステム において、CPUからみた、主記憶とキャッシュメモリとを合わせた平均アクセス時間を表す式はどれか。ここで、読み込みたいデータがキャッシュメモリに存在しない確率をrとし、キャッシュメモリ管理に関するオーバヘッドは無視できるものとする。

解答：イ

＜解説＞

1. キャッシュメモリを使ったアクセス時間は、以下の式で求めることができる。
   

   キャッシュメモリのアクセス時間 × キャッシュメモリに存在する確率

   ＋

   主記憶のアクセス時間 × キャッシュメモリに存在しない確率

2. 次の条件を1に代入する。
   ※キャッシュメモリのアクセス時間 がx，主記憶のアクセス時間 = y ，キャッシュメモリに存在する確率が1 - r，キャッシュメモリに存在しない確率がrである。

   x × (1 - r)

   ＋

   y × r

したがって、イが正解である。

問題へ

問題5

システムの信頼性向上技術に関する記述のうち、適切なものはどれか。

ア	故障が発生したときに、あらかじめ指定された安全な状態にシステムを保つことをフェールソフトという。
イ	故障が発生したときに、あらかじめ指定されている縮小した範囲のサービスを提供することをフォールトマスキングという。
ウ	故障が発生したときに、その影響が誤りとなって外部にでないように訂正することをフェールセーフという。
エ	故障が発生したときに対処するのではなく、品質管理などを通じてシステム構成要素の信頼性を高めることをフォールトアボイダンスという。

解答：エ

＜解説＞

ア	×	故障が発生したときに、あらかじめ指定された安全な状態にシステムを保つことをフェールセーフという。
イ	×	故障が発生したときに、あらかじめ指定されている縮小した範囲のサービスを提供することをフェールソフトという。
ウ	×	故障が発生したときに、その影響が誤りとなって外部にでないように訂正することをフォールトマスキングという。
エ	○	故障が発生したときに対処するのではなく、品質管理などを通じてシステム構成要素の信頼性を高めることをフォールトアボイダンスという。

問題へ