このページでは、しゅんぜい氏の発行されているメルマガのうち「データベース」について
編集して掲載しています。
数値データが格納された配列Ｘがある。配列の先頭のデータＸ[０] は 最小であること、Ｘ[０] からＸ[Ｋ−１] までは昇順に並んでいることは 分かっているものとする（ただし、Ｋ＞０）。これをＸ[０] からＸ[Ｋ] まで昇順に並ぶようにしたい。次のようなアルゴリズムを考えた。 図中の【１】,【２】の部分に当てはまる記号の組合せとして、最も適切な ものはどれか。 ＿＿＿＿＿ （ 開 始 ） ￣￣│￣￣ ┌───┴───┐ │ Ｘ[Ｋ] → Ａ │ └───┬───┘ ┌───┴───┐ │ Ｋ−１ → Ｉ │ └───┬───┘ ┌────→│ │ │ │ ／ ＼ │ ／ ＼ │ ／Ｘ[Ｉ]：Ａ＼【２】 │ ＼ ／──────────┐ │ ＼ ／ │ │ ＼ ／ │ │ │【１】 │ │┌────┴─────┐ ┌────┴────┐ ││Ｘ[Ｉ] → Ｘ[Ｉ＋１]│ │Ａ → Ｘ[Ｉ＋１] │ │└────┬─────┘ └────┬────┘ │ ┌───┴───┐ │ │ │ Ｉ−１ → Ｉ │ │ │ └───┬───┘ │ │ │ ──┴── └─────┘ （ 終 了 ） ￣￣￣￣￣ ┌───────┬───────┐ │ 【１】 │ 【２】 │ ┌─┼───────┼───────┤ │ア│ ＞ │ ≦ │ ├─┼───────┼───────┤ │イ│ ≧ │ ＜ │ ├─┼───────┼───────┤ │ウ│ ＜ │ ≧ │ ├─┼───────┼───────┤ │エ│ ≦ │ ＞ │ ├─┼───────┼───────┤ │オ│ ≠ │ ＝ │ └─┴───────┴───────┘ ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ ■解答■（出典：H8. プロダクション 問7） ---------------------------------------------------------------------- ┌───────┬───────┐ │ 【１】 │ 【２】 │ ┌─┼───────┼───────┤ │ア│ ＞ │ ≦ │ └─┴───────┴───────┘ ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ ■解説■ ---------------------------------------------------------------------- 今週は、フローチャート特集をやっています。 今日は挿入ソートに関する問題でした。ちょっと古めの問題ですが、手元に 問題がなかったので、これになりました。選択肢が５コのころです。 さっそく考えていきましょう。 問題文から配列Ｘは、Ｘ[０] からＸ[Ｋ] までの（ｋ＋１）コの要素から 成る配列です。また、Ｘ[０] からＸ[Ｋ−１] まではソート済みです。 つまり、Ｘ[Ｋ] の値のみソートされていません。このＸ[Ｋ] の要素を 「どこに入れれば良いのか？」を順に探していくのが挿入ソートです。 つまり、 Ｘ[Ｋ] （これをどこかに入れる） ↓ │１│２│ ・・・ │７│９│★│ └─┴─┴ ┴─┴─┴─┘ ↑ ↑ Ｘ[０] Ｘ[Ｋ−１] （これらの値は、ソート済み） となります。 今日は、フロチャートを区切って見ていきたいと思います。 まずは、最初の部分です。 > ＿＿＿＿＿ > （ 開 始 ） > ￣￣│￣￣ > ┌───┴───┐ > │ Ｘ[Ｋ] → Ａ │ > └───┬───┘ > ┌───┴───┐ > │ Ｋ−１ → Ｉ │ > └───┬───┘ ここは、並び替える前の準備段階です。これから挿入するＸ[Ｋ] を変数Ａ に入れておき、ループの添え字のＩに（ｋ−１）を代入します。 > （続 き） > │ > ┌────→│ > │ │ > │ ／ ＼ > │ ／ ＼ > │ ／Ｘ[Ｉ]：Ａ＼【２】 > │ ＼ ／──────────┐ > │ ＼ ／ │ > │ ＼ ／ │ > │ │【１】 │ > │┌────┴─────┐ ┌────┴────┐ > ││Ｘ[Ｉ] → Ｘ[Ｉ＋１]│ │Ａ → Ｘ[Ｉ＋１] │ > │└────┬─────┘ └────┬────┘ > │ ┌───┴───┐ │ > │ │ Ｉ−１ → Ｉ │ │ > │ └───┬───┘ │ > │ │ ──┴── > └─────┘ （ 終 了 ） ￣￣￣￣￣ さて、メインの部分です。 まず、Ｘ[Ｉ]とＡを比較しています。Ｉは（ｋ−１）という値を入れたこと と、【１】の方を見ればわかりますが、値はだんだん減っていきます。 つまり、下の図で言えば、Ａに入っている値と「９」の値を比較します。 わかりやすくするために、Ａに入っている値（★）を７にしてみます。 Ｉの位置 ↓ │１│２│ ・・・ │６│９│★│ │７│ └─┴─┴ ┴─┴─┴─┘ └─┘ ↑ ↑ ↑ Ｘ[０] Ｘ[Ｋ−１] Ａ 「７」と「９」を比べた場合、「７」の方が小さいです。・・・（＊） そうなると、次は「７」と「６」を比べることになりますね。 つまり、Ｉが１減らなくてはいけません。 Ｉの位置 ↓ │１│２│ ・・・ │６│９│★│ │７│ └─┴─┴ ┴─┴─┴─┘ └─┘ ↑ ↑ ↑ Ｘ[０] Ｘ[Ｋ−１] Ａ よって、【１】の方に進むには（＊）から「Ｘ[Ｉ] ＞ Ａ」である 必要があります。（【１】の答えは ＞ と予想できる） 【１】の方の流れとして、Ｘ[Ｉ] → Ｘ[Ｉ＋１] というのは、 比較し終わった要素をずらしている作業になります。 （この場合は、９が右にずれる） ↓ │１│２│ ・・・ │６│ │９│ │７│ └─┴─┴ ┴─┴─┴─┘ └─┘ ↑ ↑ ↑ Ｘ[０] Ｘ[Ｋ−１] Ａ 話を続けましょう。同じことを繰り返します。今度は「７」と「６」を 比べると、「６」の方が小さいですね。・・・（＊＊） つまり、「Ｘ[Ｉ] ＜ Ａ」になっています。 したがって、【２】は ＜ と予想できます。 さらに、そのまま【２】に進むと Ａ → Ｘ[Ｉ＋１] とあるので 下の図のように、空白部分に「７」が入り、ソートが完了します。 Ｉの位置 Ｉ＋１の位置 ↓ ↓ │１│２│ ・・・ │６│ │９│ │７│ └─┴─┴ ┴─┴─┴─┘ └─┘ ↑ ↑ ↑ Ｘ[０] Ｘ[Ｋ−１] Ａ この時点で、考えられる答えは「ア」or「イ」ですね。 この判断は、Ａに入っている値とＸ[０] の値が同じ場合を考えます。 Ａに入っている値とＸ[０] の値が同じ場合、上の例を用いれば、 最終的な状態は下のようになっているはずです。 Ｉの位置 ↓ │１│ │ ・・・ │６│９│ │１│ └─┴─┴ ┴─┴─┴─┘ └─┘ ↑ ↑ ↑ Ｘ[０] Ｘ[Ｋ−１] Ａ この場合、Ａの値をＩ＋１に該当する部分に挿入しないとソートが完了 しません。つまり、Ａに入っている値とＸ[０] の値が同じ場合でも、 ソートを完了させるには、Ｘ[Ｉ] ≦ Ａである必要があるのです。 したがって、「ア」が正解になります。
ＤＭＡ（H9. プロダクション 問17） DMA（直接アクセス）制御方式による入出力処理の記述として、最も適切な ものはどれか。 ア CPU が入出力装置を直接制御してデータ転送を行う。 イ CPU を介さずに入出力装置と主記憶装置の間のデータ転送を行う。 ウ チャネル接続によって入出力装置と主記憶装置の間のデータ転送を行う。 エ 入出力制御専用のプロセッサによってデータ転送を制御する。 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ ■解答■（出典：H9. プロダクション 問17） ---------------------------------------------------------------------- イ CPU を介さずに入出力装置と主記憶装置の間のデータ転送を行う。 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ ■解説■ ---------------------------------------------------------------------- 引き続き、アーキテクチャの特集です。 今日は、DMA(Direct Memory Access) 制御方式に関する問題でした。 昨日、DMA について少し出てきたのですが、質問があったので もう１問取り上げました。ちょっと古めの問題です。 選択肢を順に見ていきましょう。 > ア CPU が入出力装置を直接制御してデータ転送を行う。 これは、直接制御（プログラムコントロール）方式のことです。 CPU が入出力動作を直接制御します。 よって、その間は CPU が他の制御ができなくなるので、CPU の利用 効率が落ちてしまいます。 イメージとしては、こんなカンジです。 細線がバス、太線がデータの流れを表していると思ってください(^^; ┌─────┐ ┏━━┿ 主記憶 │ ┌────┐┃┌─┤（メモリ）│ │ ┏┿┛│ └─────┘ │ＣＰＵ┃├─┤ │ ┗┿┓│ ┌────────┐ ┌────┐ └────┘┃└─┤ 入出力 ├─┤周辺装置│ ┗━━┿ コントローラ ┿━┿ │ └────────┘ └────┘ > イ CPU を介さずに入出力装置と主記憶装置の間のデータ転送を行う。 これが、正解です。 DMA(Direct Memory Access) 制御方式とは、CPU を介さずに 入出力装置と主記憶装置の間のデータ転送を行う方式です。 と言っても、データ転送が行われるまでは CPU が入出力制御を行う のですが、CPU からの入出力命令があると CPU は DMA コントローラ という入出力制御専用のチップにその情報を送ります。 その後は、DMA コントローラが入出力を制御します。ただ、入出力 データの転送が開始されるまでと、入出力動作中にバスで競合が起きた 場合には CPU が待たされることになります。 イメージは、こんなカンジです。 ┌─────┐ ┏━┿ 主記憶 │ ┌───┐┃┌┤（メモリ）│ │ │┃│└─────┘ │ＣＰＵ├╂┤ │ │┃│┌────────┐┌────────┐┌────┐ └───┘┃└┤ ＤＭＡ ├┤ 入出力 ├┤周辺装置│ ┗━┿ コントローラ ┿┿ コントローラ ┿┿ │ └────────┘└────────┘└────┘ > ウ チャネル接続によって入出力装置と主記憶装置の間のデータ転送を行う。 これは、チャネル制御方式のことです。 チャネルがデータ転送制御のためのプログラムを主記憶から自律的に 読み出して入出力装置を制御することによって、DMA 制御方式よりも 並行処理の度合いを高めた方式です。 DMA 制御方式は、CPU に頼まれてから仕事をすると言うイメージで、 チャネル制御方式は、CPU と無関係に仕事をすると言うイメージです。 イメージは、こんなカンジです。 ┌─────┐ │ 主記憶 │ ┌───┐ ┌┤（メモリ）│ │ │ │└┬╂───┘ │ＣＰＵ├─┤ │┃ │ │ │┌┴╂────┐┌────────┐┌────┐ └───┘ └┤ チャネル ├┤ 入出力 ├┤周辺装置│ │ ┿┿ コントローラ ┿┿ │ └──────┘└────────┘└────┘ > エ 入出力制御専用のプロセッサによってデータ転送を制御する。 これは、入出力制御専用プロセッサ方式のことでしょう（？） 入出力制御専用プロセッサでデータを制御します。 ＃うーん、最後があやしい・・・。