１９９９／０１／０９
注意１：このページは、回線を切断した後でゆっくりご覧になってください（テキストを印刷する場合は、その取り扱いに注意してください）。
注意２：背景が白地の画面を長時間見つめていると頭が痛くなってしまいますので、ここは背景をグレーにしています。
問11 次の図のような記述法による構文図を考える。−１，２１．５，＋５．２３などの表現は、この構文図の規定に合致する。
この記述法に従うとき、次の構文図の規定に合致する数値表現はどれか。
ア −５２．３Ｅ０５ イ ．５８Ｅ２ ウ ＋．９０Ｅ１１
エ ３．４５Ｅ オ ２８．Ｅ−１
問12 次の二つのスタック操作を定義する。
ＰＵＳＨ ｎ ： スタックにデータ（整数ｎ）をプッシュする。
ＰＯＰ ｎ ： スタックからデータをポップする。
空のスタックに対して、次の順序で操作を行った結果はどれか。
ＰＵＳＨ １ → ＰＵＳＨ ５ → ＰＯＰ → ＰＵＳＨ ７ → ＰＵＳＨ ６ → ＰＵＳＨ ４ → ＰＯＰ → ＰＯＰ → ＰＵＳＨ ３
問13 次の２分木で表される算術式はどれか。
ア Ａ＋Ｂ×Ｃ＋（Ｄ＋Ｅ）÷Ｆ イ Ａ＋Ｂ×Ｃ−（Ｄ＋Ｅ）÷Ｆ
ウ Ａ＋Ｂ×Ｃ−Ｄ＋Ｅ÷Ｆ エ Ａ×Ｂ＋Ｃ＋（Ｄ−Ｅ）÷Ｆ
オ Ａ×Ｂ＋Ｃ−Ｄ＋Ｅ÷Ｆ
問14 データを降順に並べた線形リストを２分探索法で探索するとき、３回目までの比較で探索を終了することができる要素の最大個数はどれか。
ア ３ イ ４ ウ ５ エ ７ オ １５
問15 ｎ個の要素をもつ配列中の値と探索すべきデータＸを順次比較し、配列中の値にデータＸが存在した場合、”有”を表示する。このとき、添え字ｎ＋１の場所に探索すべきデータＸを入れておく。
| 添え字 | １ | ２ | ３ | ... | ｉ | ... | ｎ | ｎ＋１ |
| 値 | ａ1 | ａ2 | ａ3 | ... | ａi | ... | ａn | Ｘ |
この線形探索アルゴリズム中の（ ）に入れるべき適切な条件はどれか。
ステップ１ 添え字ｉに１を入れる。
ステップ２ （ ）であればステップ５へとぶ。
ステップ３ 添え字ｉに１を加算する。
ステップ４ ステップ２へとぶ。
ステップ５ 添え字ｉがｎ以下であれば”有”を表示する。
ステップ６ 終了
ア ｉ≧ｎ イ ｉ≠ｎ ウ ｉ＜ｎ エ Ｘ＝ａi オ Ｘ≠ａi
問16 整数値からなるｎ個（ただし、ｎ≧２）のデータが、配列Ｔに格納されている。次の流れ図は、それらのデータを交換法を用いて昇順に整列する処理を示す。流れ図中のａに入れるべき適切な条件はどれか。
ア Ｔ( ｊ )＜Ｔ( ｊ＋１ ) イ Ｔ( ｊ )＜Ｔ( ｊ−１ )
ウ Ｔ( ｊ )＝Ｔ( ｊ−１ ) エ Ｔ( ｊ )＞Ｔ( ｊ＋１ )
オ Ｔ( ｊ )＞Ｔ( ｊ−１ )
問17 ａ，ｂを整数とする。次の流れ図によって表されるアルゴリズムを実行した後、ａ，ｂの値に無関係に成り立つ条件はどれか。
ア ｘ＝０かつｙ＝ａ＋ｂ イ ｘ＝ａかつｙ＝ｂ
ウ ｘ＋ｙ＝ａ＋ｂ エ ｘ−ａ＝ｙ−ｂ
オ ｘ×ｂ＝ｙ×ａ
問18 ２５ＭＩＰＳの処理装置がある。この処理装置の平均命令実行時間はどれか。
ア ４０ナノ秒 イ ０．２５マイクロ秒 ウ ０．４マイクロ秒
エ ２．５マイクロ秒 オ ４マイクロ秒
問19 縦の画素数が４８０ドット，横の画素数が６４０ドットの画像を２５６種類の色で表示する。このデータを記憶媒体に保存するためには、約何ｋバイトの容量が必要か。ただし、圧縮等の処理は行わないものとする。
ア １７０ イ ３１０ ウ ４８０ エ ９，８４０ オ ７８，６５０
問20 毎秒３００ｋバイトのデータを伝送効率３０％のＬＡＮを使用して送る。このＬＡＮに必要な伝送速度は、最低何Ｍビット／秒か。
ア １．０ イ ２．４ ウ ８．０ エ １０ オ ２４
問11について
数字の箱が３箇所にありますよね。ここで、最初の数字の箱の前部をＡ，２番目の数字の箱の前部をＢ，最後の数字の箱の前部をＣとします。
Ａ部分に注目してください。
Ａ部分からは、求める数値表現の先頭１文字は、”＋”か”−”か”数字”のいずれかであることが分かります。したがって、イが消えます。
さらに、先頭１文字が”＋”か”−”の場合は、その次は必ず数字がこなければなりませんので、ウもここで消えます。
次にＢ部分に注目してください。
Ｂ部分からは、求める数値表現の中に”．”があった場合、その次の文字は必ず”数字”であることが分かります。したがってここでオが消えます。
最後にＣ部分に注目してください。
Ｃ部分からは、求める数値表現の中に”Ｅ”があった場合、その次の文字は”＋”か”−”か”数字”のいずれかであることが分かります。したがってここでエが消えます。
とういことで、残るアが正解です。
問12について
それぞれの操作を行った後のスタックの内容を確かめます。
スタックの先頭 ← → スタックの底
@ ＰＵＳＨ １ ： １
A ＰＵＳＨ ５ ： ５，１
B ＰＯＰ ： １
C ＰＵＳＨ ７ ： ７，１
D ＰＵＳＨ ６ ： ６，７，１
E ＰＵＳＨ ４ ： ４，６，７，１
F ＰＯＰ ： ６，７，１
G ＰＯＰ ： ７，１
H ＰＵＳＨ ３ ： ３，７，１
問13について
木の頂点が”−”なので、この木は、
（左部分木）−（右部分木）
となる式を表しています。
左部分木に注目すると、
左部分木＝（Ａ）＋（Ｂ×Ｃ） であることが分かり、
右部分木に注目すると、
右部分木＝（Ｄ＋Ｅ）÷（Ｆ） であることが分かります。
したがって、この木全体は、
（（Ａ）＋（Ｂ×Ｃ））−（（Ｄ＋Ｅ）÷（Ｆ）） であり、これを展開して求める答えは、
Ａ＋Ｂ×Ｃ−（Ｄ＋Ｅ）÷Ｆ です。
問14について
第４回講座（平成６年秋期午前）の問33を参照してください。
求める答えは、７回です（ｎ回の比較で探索を終了することができる要素の最大個数は、２n−１と覚えちゃってもいいです）。
問15について
この問題で行っているように、最後の要素に探索するデータ（この問題のＸ）を格納しておく方法を、”番兵”といいます。
番兵を用いることによって、添え字が要素数を超えたかどうかの判定が繰り返し処理の中で不要となり（線形探索を行うと、必ず求める値と一致する要素が見つかるから）、通常の線形探索よりも、ほんの少し高速な処理が期待できます。
ステップ２の空欄の解説は不要でしょう。求める答えは、Ｘ＝ａiです。ステップ５にとんだ後の判定で、もし番兵と一致したならばｉ＝ｎ＋１となっていますので、この時は”有”を表示しません。
（注）
問題の意味を取り違えないように。
探索するデータＸは、要素１〜要素ｎの中にあるかもしれないし、ないかもしれないのです。問題では、そのあるなし関わらず、ｎ＋１の位置にデータＸを格納しています。
問16について
交換法（基本交換法）による整列アルゴリズムの説明は、ここでは省略します。これはまた別の機会で説明しましょう。
ここでは、交換法による整列アルゴリズムが、（おぼろげながらでも）理解していることを前提に説明します。
ループ中の処理つまり、”Ｔ（ ｊ ）とＴ（ ｊ−１ ）の交換”に注目してください。
空欄ａの比較を行った後で、もし比較条件に合致していれば上記の交換処理を行うし、合致していなければこの交換処理を行いません。
比較処理と交換処理は非常に密接な関係にあります。もっと言えば、比較処理で対象とするデータと、交換処理で対象とするデータは、同じなのです。
つまり、比較の一方は Ｔ（ ｊ ）であり、もう一方は Ｔ（ ｊ−１ ）です。
また、この問題では昇順に整列しますので、最終的には、Ｔ（ ｊ−１ ）≦Ｔ（ ｊ ）であることが求められます。
ということは、交換処理を行う条件は”Ｔ（ ｊ ）＜Ｔ（ ｊ−１ ）”です。
問17について
ループに入る直前では、ａ＝ｘ，ｂ＝ｙです。その時点では、ｘ＋ｙ＝ａ＋ｂの関係が成り立つことは分かるでしょう。
一方ループの中で、ｘを１減算してｙを１加算していますが、新しいｘ＋ｙの値は、元のｘ＋ｙの値と変わりませんよね。
ということで、ループ中の処理を何回実行したとしても、常にｘ＋ｙ＝ａ＋ｂの関係が成り立ちます。
さらに、ループを脱出する時点でｘは常に０ですので、ｘ＝０かつｙ＝ａ＋ｂの関係も成り立ちます（ア，ウどちらでも正解ですが、アの方が条件が厳しいので、アと解答するのが無難です）。
問18について
２５ＭＩＰＳは、当該ＣＰＵが１秒間に平均して、２５×１０6回の命令を実行することを意味します。
すると１回の平均命令実行時間は、１÷（２５×１０6）秒であり、これは４０ナノ秒です。
（参考．．．とても重要）
テラ（Ｔ）は１０12
ギガ（Ｇ）は１０9
メガ（Ｍ）は１０6
キロ（ｋ）は１０3
ミリ（ｍ）は１０-3
マイクロ（μ）は１０-6
ナノ（ｎ）は１０-9
ピコ（ｐ）は１０-12
問19について
２５６種類の色を表現するために必要なビット数は８です。
なぜなら、２色を表現するのに必要なビット数は１であり、４色を表現するのに必要なビット数は２であり、８色を表現するのに必要なビット数は３であり、．．．２n色表現するのに必要なビット数はｎだからです（８ビットあれば０〜２５５までを区別できると言った方がよいでしょうか）。
１ドットに対して８ビット、つまり１バイト必要なのですから、４８０×６４０ドットの画像で必要なバイト数は、３０７２０（４８０×６４０）バイトです。
問20について
１秒間に３００ｋバイトのデータをやりとりするということは、もし伝送効率が１００％であれば、２．４Ｍビット／秒（３００ｋ×８）の伝送速度があればよいことになります。
ところが問題では伝送効率が３０％ですので（実際、１００％にはなりません）、最低でも、８Ｍビット／秒（２．４Ｍ÷０．３）の伝送速度が必要です。
問11 ア 問12 エ 問13 イ 問14 エ 問15 エ
問16 イ 問17 ア，ウ 問18 ア 問19 イ 問20 ウ