のんびりやろう！情報処理試験！-１問１問コツコツと- 

J Question vol.1848

 ▲　━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ ┏┓
┃┃　　のんびりやろう！情報処理試験！　〜１問１問コツコツと〜　　┃┃
┃┃ 2008.6.16　vol.1848　19,526 部発行  http://www.shunzei.com/  ┃┃
┗┛ ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━　▼ 

--PR------------------------------------------------------------------

　【博多いち】〜九州・博多発人気グルメのお取り寄せショップ〜
▼楽天グルメ大賞入賞商品「黄金のプリン」、九州・博多発人気グルメ
辛子明太子・ラーメン・もつ鍋・辛子高菜・おふくろさん・日田天領水　ほか
人気のお取り寄せグルメが勢揃い♪
　只今、新規会員登録の方に100ポイント進呈中！
http://px.a8.net/svt/ejp?a8mat=1BZQAE+9U8XPU+1DII+5YRHF 

----------------------------------------------------------------------

◇◆　Ｃ言語対策の決定版！アルゴリズム力を身に付けるための１冊！　◆◇
◆◇　　　　　　　【基本情報技術者試験 C言語の切り札】　　　　　　◇◆
◇◆　　　　  http://www.shunzei.com/book/kirifuda_c.html 　　　　◆◇
◆◇◆　　　　　　　　　　　　　　　　　　　　　　　　　　　　　◆◇◆
◇◆◇　 　　Ｃ言語対策の定番として継続的に売れています(^^) 　　◇◆◇

------------------------------------------------------------------PR--

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
◆お知らせ◆　春試験の高度区分の合格発表について
----------------------------------------------------------------------

　おはようございます。しゅんぜいです。

　春試験の基本情報・初級シスアドの合格発表日は、
　6月16日(月)正午の予定です。今日ですね(^^)
　受験票の受験番号とパスワードで、採点結果の確認ができます。

　また、初級シスアドと基本情報の採点講評が 6/13 に掲載されています。

　JITEC ： http://www.jitec.jp/ 

　合格・未合格報告もお待ちしております！


━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
■今日の問題■☆☆☆（等幅フォントで見てね！）
----------------------------------------------------------------------
　データ構造に関する記述のうち、B 木の説明として適切なものはどれか。

　ア　ある特定のアルゴリズムに従って、レコードのキー値から
　　　物理的な格納アドレスを求めてレコードを格納する。

　イ　索引部の各ノードのキー値を中心にして、小さい側のレコード数と
　　　大きい側のレコード数の比率が、ある許容範囲内に収まるように
　　　動的に再配置する。

　ウ　レコードの物理的配置とは独立に、論理的にレコードをつなぐ
　　　ポインタによって、レコードを関係づけて格納する。

　エ　レコードをキー値の昇順にトラックなどのアクセス単位（ページ）
　　　ごとに格納し、各ページ内の最大キー値とそのページの番地をもつ
　　　索引を作る。




















━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
■解答■（出典：H15.　ソフトウェア　問9）
----------------------------------------------------------------------
　イ　索引部の各ノードのキー値を中心にして、小さい側のレコード数と
　　　大きい側のレコード数の比率が、ある許容範囲内に収まるように
　　　動的に再配置する。

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
■解説■
----------------------------------------------------------------------
　コンピュータサイエンスの特集に入っています。
　今日は、データ構造（Ｂ木）に関する問題でした。


　B 木(Balanced Tree, B-Tree) とは、木構造の一種で
　二分木(Binary Trees) を改善し、探索を高速化したデータ構造です。

　具体的には、ルートからそれぞれの葉(leaf)までの階層数を
　全て同じにした木構造で、Ｏ(log n)のオーダで探索を行うことができます。

　# B-Treeは削除や挿入を繰り返すと最大でＯ(log n)になってしまうので
　# アルゴリズムを改良した B*-Tree や B+-Tree があります。

　# ここで言う n は要素数のことです。

　アルゴリズムが作られたのは1970年代ですが、今でもファイルシステムや
　データベースで用いられています。

　B 木を構成するための条件は次の通りです。

　(1) 根以外の各ノードは、n 個以上 2n 個以下のレコードを持つ。
　(2) 各ノードは、そのノードが持つレコードの数 ＋1 の子を持つ。
　(3) 全ての葉までの深さは等しい。

　この B 木に要素の追加や削除を行った場合は、上の条件を満たすように
　木構造を再編成することで、バランスを取れるような構造に保ちます。

　数学が得意な方でアルゴリズムを知りたい方はこの辺でどうぞ。
　http://pfp7.cc.yamaguchi-u.ac.jp/~ichikawa/lecture/yamanashi-u/01/resume/node9.html 


　選択肢を順に見ていきましょう。

> ア　ある特定のアルゴリズムに従って、レコードのキー値から
> 　　物理的な格納アドレスを求めてレコードを格納する。

　　　B 木ではレコードのキー値から論理的な格納アドレスを求めて
　　　レコードに格納します。


> イ　索引部の各ノードのキー値を中心にして、小さい側のレコード数と
> 　　大きい側のレコード数の比率が、ある許容範囲内に収まるように
> 　　動的に再配置する。

　　　これが正解ですね。

　　　B 木では、効率良く探索を行う（探索速度のバラつきをなくす）ために
　　　追加や削除のたびに動的に再編成を行います。


> ウ　レコードの物理的配置とは独立に、論理的にレコードをつなぐ
> 　　ポインタによって、レコードを関係づけて格納する。

　　　これは、リスト構造の説明になります。


> エ　レコードをキー値の昇順にトラックなどのアクセス単位（ページ）
> 　　ごとに格納し、各ページ内の最大キー値とそのページの番地をもつ
> 　　索引を作る。

　　　これは、索引順編成(Indexed Sequential Access Method：ISAM) の
　　　構造です。直接アクセスとシーケンシャルアクセス（順アクセス）が
　　　可能な構造で、追加や削除を行うとムダな領域が増えるため、
　　　再編成が必要となる場合があります。


　選択肢は、データベースに詳しくない人の説明になってしまいましたが(^^;;
　試験対策としては、

　　○B 木とは、Balanced Tree（平衡木）である。
　　○木構造が平衡を保つように動的に再配置する。

　これぐらいを押さえておけば良いでしょう。



━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
★これ、おしえてっ！（質問編）★　回答期限：６月１６日（月）の夜まで
----------------------------------------------------------------------
　「この問題がわからないっ！！」という、
　読者からの質問をみなさんに回答してもらおう！というコーナーです。


　今回の質問はこちらです。（出典：H19.　上級シスアド　問4）
----------------------------------------------------------------------

　複数のクライアントから呼び出されるあるサーバのタスク処理時間は、
　タスクの多重度が 2 以下の場合、常に 4 秒である。
　このタスクへ 1 秒ずつずれて 4 件の処理要求が到着した場合、すべての
　処理が終わるまでの時間はタスクの多重度が 1 のときと 2 のときで、
　何秒の差があるか。


　ア　6

　イ　7

　ウ　8

　エ　9


--[回答のめやす（横幅：全角３４文字）]--------------------------------
> １２３４５６７８９０１２３４５６７８９０１２３４５６７８９０１２３４
----------------------------------------------------------------------

　この問題、ソフトウェア平成19年秋の問32でも出題されています。

　これに対する回答（解説）を６月１６日（月）の夜までにお願いします。

　このコーナーで取り上げてほしい問題のリクエストも募集中です。
　回答＆お便りはこちらからでもＯＫです。
　http://www.shunzei.com/about/mail.html 


━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
▼選択肢で勉強しよっ！▼（答えはこのメールの一番下にあります）
----------------------------------------------------------------------

> デッドロック(dead lock) って？



━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
> *********************** 投稿募集中のテーマ *********************** <
----------------------------------------------------------------------

　●「これ、おしえてっ！」で扱ってほしい問題のリクエストやその回答
　●「選択肢で勉強しよっ！」で扱ってほしい用語のリクエスト
　●「その他、試験などに関するお便り（テーマフリー）」

　ハンドル名を添えて、このメールマガジンに返信して頂ければ届きます。
　WebからでもＯＫ！　http://www.shunzei.com/about/mail.html 

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
　のんびりやろう！情報処理試験！　〜１問１問コツコツと〜（週３日発行）
----------------------------------------------------------------------

　編集・発行：しゅんぜい　mail_at_shunzei.com (_at_は @ に)
  　　　発送：melma!　　　http://www.melma.com/ 　（ID：189)
　　　　　　：まぐまぐ　　http://www.mag2.com/ 　　(ID：24856)
　　　　　　：めろんぱん　http://www.melonpan.net/ (ID：78)

　登録・解除：http://www.shunzei.com/mm/ 

　○バックナンバー
　立ち読み　　： http://www.melma.com/backnumber_189/ 
　ダウンロード： http://www.shunzei.com/mm/backnumber.html 

　転載について： http://www.shunzei.com/about/disclaimer.html 
　広告掲載は mail_at_shunzei.com (_at_は @ に)までお願いします。

----------------------------------------------------------------------
　○メールマガジンの購読の登録・解除は個人の責任で行ってください。
　　しゅんぜいは一切代行しません！

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
▼選択肢で勉強しよっ！の答え▼
----------------------------------------------------------------------

　（セキュリティ平成２０年問２８）より

> デッドロックが発生する可能性のある排他制御の方式はどれか。
> 
> ア　2 相ロックプロトコルに従ってロックする方式

　（ソフトウェア平成１８年春問２６）の問題文より

> 資源獲得の順序を両方のタスクで同じにする。

　（基本情報平成１６年春問６９エ）の選択肢より

> 複数のトランザクションが、互いに相手のロックしている資源を要求して
> 待ち状態となり、実行できなくなること

　（ソフトウェア平成１４年問２８）より

> 資源Ｘ，Ｙ，Ｚを占有して処理を行うプロセスＡ〜Ｄがある。
> 各プロセスは処理の進行に伴い、表中の数値の順に資源を占有し、
> 実行終了時に三つの資源を一括して解放する。
> プロセスＡとデッドロックを起こす可能性のあるプロセスはどれか。
> 
> ┌─────┬─────────────────┐
> │　　　　　│　　　　　資源の占有順序　　　　　│
> │プロセス名├─────┬─────┬─────┤
> │　　　　　│　資源Ｘ　│　資源Ｙ　│　資源Ｚ　│
> ├─────┼─────┼─────┼─────┤
> │プロセスＡ│　　１　　│　　２　　│　　３　　│
> │プロセスＢ│　　３　　│　　２　　│　　１　　│
> │プロセスＣ│　　２　　│　　３　　│　　１　　│
> │プロセスＤ│　　１　　│　　２　　│　　３　　│
> └─────┴─────┴─────┴─────┘
> 
> 
> ア　プロセスＢ，Ｃ

　（１種平成１１年問２１イ）の選択肢より

> タスクＸが資源Ａを確保し、タスクＹが資源Ｂを確保した後に、
> タスクＹが資源Ａを要求し、タスクＸが資源Ｂを要求した。

　データベースでは、複数のユーザがデータの更新をすることができます。

　しかし、あるユーザが更新中のデータを別のユーザが同時に
　更新してしまった場合、データベースは整合性が保てなくなってしまいます。

　これを防ぐには、データベースの排他制御を行います。

　排他制御とは、あるユーザが更新中のデータはその更新が終わるまで
　ロックをかけて、別のユーザが更新できないようにする仕組みです。
　ユーザの更新が終わればロックは解除されます。

　一連の流れでロックが解除されれば良いのですが、これが何らかの原因で
　ロックの解除ができなくなり、そのまま止まってしまうこともあります。
　これをデッドロックと言います。

　デッドロック(dead lock)とは、DBMS(DataBase Management System)に
　おいて、データを共有する複数のタスクが実行されているときに、
　トランザクションの実行の順番によって、複数のタスクが
　相手の確保しているものを待ち続けてしまう状態になり、
　いつまでたっても待ち状態が続いてしまう（固まってしまう）ことを
　言います。


=-=[あとがき]=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

　気が付けば、６月ももう半分終わってるんですね。
　ってことは、今年も半分が終わるってことですね。早い！！

　さて、今日は春の高度区分の合格発表ですね。
　合否結果はもちろん、点数の方もチェックしてみてくださいね。
　そして、秋試験に向けての準備も始めましょう！
　僕も今年の秋は何を受けようかな。。。


----------------------------------------------------------------------
◆のんびりやろう！情報処理試験！はこちらから http://www.shunzei.com/ 
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

• 前の記事
• 最新の記事
• 次の記事

規約に同意して

登録した方には、まぐまぐの公式メルマガ（無料）をお届けします。