情報処理試験(H20春) ソフトウェア開発技術者 午前問11～15

問11 データの整列方法に関する記述のうち、適切なものはどれか。
ア クイックソートでは、ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し、さらに間隔を詰めて同様の操作を行い、間隔が1になるまでこれを繰り返す。
イ シェルソートでは、隣り合う要素を比較して、代償の順が逆であれば、それらの要素を入れ替えるという操作を繰り返す。
ウ バブルソートでは、中間的な基準値を決めて、それよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分ける。次にそれぞれの区分の中で同様な処理を繰り返す。
エ ヒープソートでは、未整列の部分を順序木に構成し、そこから最大値または最小値を取り出して規制列の部分に移す。この操作を繰り返して、未整列部分を縮めていく。

解答
エ

解説
これも良く出るソートに関する問題ですねぇ。
個人的には、どうでもよいような問題ですが、まぁ、情報処理技術者なら知っているべき無いようなんでしょうねぇ。

それぞれのソート方法をウィキペディアなどで調べれば、解答は得られそうですねぇ。

・クイックソート
データの集合を基準値より大きいものと小さいものとのグループに分け、それぞれのグループの中でも新しい基準値を使って同様の作業を行う、という手順を再帰的に繰り返す方式。(IT用語辞典より引用)
と言うと、これは選択肢ウの内容になりますねぇ。

・シェルソート
要素を数個とびに拾い集めて挿入ソートをかけ、次第にソートする要素の間隔を詰めていき、最後に単純な挿入ソートで完全に整列させる。(IT用語辞典より引用)
これは、選択肢アの内容になりますねぇ。

・バブルソート
バブルソートは、配列の隣どうしの要素の大小を比較してそれらを交換しながら整列する方法です。ちなみに、泡(バブル；bubble)が浮かんで行くように見えることからこの名前がついています。
引用URL:http://www.miyagi-ct.ac.jp/ee/lecture/E3_01/Bubble_sort.html
これは、選択肢イの内容ですねぇ。

・ヒープソート
ヒープソートでは、未整列の部分を順序木に構成し、そこから最大値または最小値を取り出して規制列の部分に移す。この操作を繰り返して、未整列部分を縮めていく。(問題文から引用)

まぁ、正解はエに成ります。

問12 16進数で表される9個のデータ1A、35,3B、54,8E,A1,AF、B2,B3を順にハッシュ表に入れる。ハッシュ値をハッシュ関数f(データ)=mod(データ,8)で求めたとき、最初に衝突が起こるのはどのデータか。ここで、mod(a,b)はaをbで割った余りを表す。

ア 54
イ A1
ウ B2
エ B3

解答
ウ

解説
問題文の意味がわかりにくいですかねぇ。
私なりの文意はこんな感じです。
「9個のデータ1A、35,3B、54,8E,A1,AF、B2,B3を順にmod(データ,8)に入れて最初に同じ答えが出るデータはどれですか。」
です。
と言うことで各数字を8で割っていき余りが同じものが2回出てきたものが正解となります。

ここで、テクニックと言うほどのものではありませんが、各数字を10進数に変えるときに下1けただけ変換すればよいことに気がつきましょう。
今回の場合8で割った余りを求められればよいのです。
2けたの16進数(例えばXY)を10進数に変換すると以下のような変換式になります。
16*X+Y
この数字の8で割った余りは、Yを8で割ったのと同じになりますよねぇ。(2桁目は16*X=2*8*Xなので、8で割り切れるため)

よって、各数字の1桁目を10進数に変換すると以下のようになります。
10,5,11,4,14,1,15,2,3
これらの8で割った余りは以下のようになります。
2,5,3,4,6,1,7,2,3
となり、2が最初に2回目の余りとして出ます。つまり、B2が答えとなります。

よって、解答はウとなります。

問13 次の流れずにおいて、ステップS4でYesと判断したときまでの、ステップS1～S4の実行回数をそれぞれん1～n4とする。n1～n4の間に成立する式はどれか。

No
┌── ◇S1
│ │YES
│┌→ ↓
││ □S2
││ │
││No ↓←──┐
│└─ ◇S3 │
│ Yes│ │
└─→ ↓ No │
◇S4──┘
│YES
↓

ア n4=n1+n2+n3
イ n4=n1+n2-n3
ウ n4=n1-n2+n3
エ n4=-n1+n2+n3

解答
ウ

解説
これはどうやって解答を得ればよいか全然わからない問題ですねぇ。
また出題者の意図が私には見えない問題です。
とはいえ、出題されたので解かないわけにはいかないので解いてみましょう。

私の解法としては、条件が3つ(S1,S3,S4)とあるので、これらをYES/NOの全パターンを考えてみました。

S1 S3 S4 n1 n2 n3 n4 備考
(1) YES YES YES 1 1 1 1
(2) YES YES NO 1 1 2 2 最後にS4はYESと判定
(3) YES NO YES 1 2 2 1 最後にS3はYESと判定
(4) YES NO NO 1 2 3 2 最後にS3、S4はYESと判定
(5) NO YES YES 1 0 0 1
(6) NO YES NO 1 0 1 2 最後にS4はYESと判定
(7) NO NO YES 1 0 0 1
(8) NO NO NO 1 1 2 2 最後にS3、S4はYESと判定

この8パターンを各選択肢に代入してみます。
選択肢ア
n4=n1+n2+n3
(1) 1 = 1+1+1 = 3 (誤り)
(2) 2 = 1+1+2 = 4 (誤り)
(3) 1 = 1+2+2 = 5 (誤り)
(4) 2 = 1+2+3 = 6 (誤り)
(5) 1 = 1+0+0 = 1 (正)
(6) 2 = 1+0+1 = 2 (正)
(7) 1 = 1+0+0 = 1 (正)
(8) 2 = 1+1+2 = 4 (誤り)

選択肢イ
n4=n1+n2+n3
(1) 1 = 1+1-1 = 1 (正)
(2) 2 = 1+1-2 = 0 (誤り)
(3) 1 = 1+2-2 = 1 (正)
(4) 2 = 1+2-3 = 0 (誤り)
(5) 1 = 1+0-0 = 1 (正)
(6) 2 = 1+0-1 = 0 (誤り)
(7) 1 = 1+0-0 = 1 (正)
(8) 2 = 1+1-2 = 0 (誤り)

選択肢ウ
n4=n1+n2+n3
(1) 1 = 1-1+1 = 1 (正)
(2) 2 = 1-1+2 = 2 (正)
(3) 1 = 1-2+2 = 1 (正)
(4) 2 = 1-2+3 = 2 (正)
(5) 1 = 1-0+0 = 1 (正)
(6) 2 = 1-0+1 = 2 (正)
(7) 1 = 1-0+0 = 1 (正)
(8) 2 = 1-1+2 = 2 (正)

選択肢エ
n4=n1+n2+n3
(1) 1 = -1+1+1 = 1 (正)
(2) 2 = -1+1+2 = 2 (正)
(3) 1 = -1+2+2 = 3 (誤り)
(4) 2 = -1+2+3 = 4 (誤り)
(5) 1 = -1+0+0 = -1(誤り)
(6) 2 = -1+0+1 = 0 (誤り)
(7) 1 = -1+0+0 = -1(誤り)
(8) 2 = -1+1+2 = 2 (正)

と言うことで、ウが正解になります。
あまり数式にこだわりすぎると、はまってしまう問題ですねぇ。
ちょっと数式変換が難しそうであれば、直接代入する方法を選択した方が、簡単に解答が得られるかもしれません。
情報処理技術者試験の午前は、1問あたりにかけられる時間は、2分程度です。(正確には、1分52秒程度)
なので、このような問題に時間を割けるように他の問題は素早く解けるようにしておいた方がよいでしょう。

難易度(1(易)～5(難))
4 ちょっとやっかいな問題ですが、愚直な解法で解けるのでこの難易度にしました。

問14 流れずに示す処理の動作の記述として、適切なものはどれか。ここで、二重線は並列処理の同期を表す。

○S
│
↓
□A
│
────┴──────
──┬─────┬──
┌──→│ │←──┐
│ ↓ ↓ │
│ □B □C │
│ │ │ │
│ │ ↓ │
│ ──┴──────── │
│ ──┬─────┬─→ │
└───┘ └───┘

ア Aの後にBC又はCB、BC又はCB、・・・と繰り返して実行する。
イ Aの後にBの無限ループ又はCの無限ループになる。
ウ ABC又はACBを実行してデッドロックになる。
エ AB又はACを実行してデッドロックになる。

解答
ア

解説
解説しづらい問題ですねぇ。
私はこの流れ図を以下のように解釈しました。
(1) まずAが実行される。
(2) 次に同期する。(と言っても処理は並列になっていないので、そのまま下に抜ける)
(3) BとCが順番はわからないが並列処理なので共に実行される。
(4) 同期を待つ。
(5) (3)につながる

と言うことで、解答はアになりました。

ちなみに他の選択肢を「違う」と判断する消去法の場合は以下のように考えました。

選択肢イ
Aの後にBの無限ループ又はCの無限ループになる。
BとCの処理は「並列処理」されるので、どちらか一方の無限ループになるのはおかしいと判断しました。

選択肢ウ
ABC又はACBを実行してデッドロックになる。
選択肢エ
AB又はACを実行してデッドロックになる。
選択肢ウ、エについては、「デッドロック」と言う言葉がこの流れ図では出てこないと判断しました。
確かに、「同期」と言う言葉はありますが、「デッドロック」は「排他制御」の時に起きる言葉だと思います。
データベースなどで良くあると思いますが、処理Bが更新中のテーブルを処理Cが参照してしまうとテーブルの内容が保証されないので、処理Bの更新が完了するまで処理Cが処理を中断するような処理です。
まぁ、デッドロックについては、別で出てくればそのとき説明します。


難易度(1(易)～5(難))
1

問15 DDR-SDRAMの特徴として、適切なものはどれか。

ア クロック信号の立ち上がりと立ち下がりの両方に同期して、データを読み出す。
イ 高速ページモードDRAMのページアクセスのサイクル時間を短くして、より高速にデータ転送する。
ウ メモリセルからデータを読み出すとき、一度だけ行アドレスを指定した後、列アドレスを変えながら複数のデータを行バッファから高速に読み出す。
エ メモリバスクロックに同期して、1クロックにつき一つのデータを読み出す。

解答
ア

解説
ハード系の用語問題です。
私の嫌いな分野の一つですねぇ。
まぁ、用語についてはインターネットで調べれば何とかなるので、覚えていきましょう。

DDR-SDRAMは以下のようなものです。(IT用語辞典引用)
ダブルデータレート(DDR)モードという高速なデータ転送機能を持ったSDRAM。コンピュータ内で各回路間の同期を取るためのクロック信号の立ち上がり時と立ち下がり時の両方でデータの読み書きが行なえるようにしたもの。

よって解答はアに成ります。

また、選択肢イは「FPM DRAM」のことらしいです。ちなみにFPMとは、Fast Page Modeのことです。
選択肢ウ、エも調べてみましたが、何に該当するのかわかりませんでした。