トップ > 学校・教育 > 資格 > のんびりやろう！情報処理試験！　～１問１問コツコツと～

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

J Question vol.1256

発行日： 2004/6/14

▲　━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ ┏┓
┃┃　　のんびりやろう！情報処理試験！　～１問１問コツコツと～　　┃┃
┃┃ 2004.6.14　vol.1256　22,484 部発行   http://www.shunzei.com/ ┃┃
┗┛ ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━　▼

━PR━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

◆◆◆◆ 2004秋試験対策　通信講座、e‐ＢＬ短期コース受付中！◆◆◆◆◆
    通信講座、e‐Based　Learning講座短期コース<7月開講>只今申込受付中
　　＊4月よりe‐Based　Learning講座は価格改定により受講料がお得に！＊
　　　　模擬テスト、オープンセミナー申込みは６月上旬より開始
  　　　　　　詳細とお申込は http://www.itec.co.jp/ から
◆◆◆《ＩＴ教育のリーディングカンパニー》アイテックの通信講座 ◆◆◆

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

　大阪市立大学大学院創造都市研究科の都市情報学専攻では、新卒者を主な
　対象とする2005年度入試（試験は９月上旬）の募集要項の配布を開始した。
　大阪市住吉区のキャンパスに平日１日/週、JR大阪駅徒歩５分の
　梅田サテライトに土曜日１日/週、通うことで必要単位の大半が取得できる。
　詳しくは http://www.gscc-ss.com/exam/a08.html

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━PR━

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
■今日の問題■☆☆（等幅フォントで見てね！）
----------------------------------------------------------------------
　スタックとキューの二つのデータ構造がある。次の手続きを
　順に実行した場合、変数 x に代入されるデータはどれか。ここで、

　　データ a をスタックに挿入することを、push(a)
　　スタックからデータを取り出すことを、pop()
　　データ a をキューに挿入することを、enq(a)
　　キューからデータを取り出すことを、deq()

　とそれぞれ表す。

　　push(a)
　　push(b)
　　enq(pop())
　　enq(c)
　　push(d)
　　push(deq())
　　x ← pop()

　ア　a

　イ　b

　ウ　c

　エ　d

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
■解答■（出典：H13.秋　基本情報　問13）
----------------------------------------------------------------------
　イ　b

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
■解説■
----------------------------------------------------------------------
　コンピュータサイエンスの特集を続けています。
　今日は、スタックとキューに関する問題でした。

　スタック(stack) とは、複数のデータを記録する方法の１つです。
　後入れ先出し法や LIFO(Last-In First-Out) とも言います。

　スタックには複数のデータを記録できますが、取り出すときには
　最後に入力されたデータから１つずつ取り出していきます。

　データを記録することをプッシュ(push)、取り出すことをポップ(pop)
　といいます。

　一方、キュー(queue) は、先入れ先出し法や待ち行列、
　FIFO(First-In First-Out) とも言います。

　スタック同様、キューにも複数のデータを記録することができますが
　データを取り出すときには一番古いデータから取り出していきます。

　今回は、スタックとキューでのデータの流れを以下のように表して
　実際にデータの流れを追っていきたいと思います。

　　　スタック　　　　　　　　キュー

　　──┐　┌─→　　　　　　
　　　　↓　│　　　　　　　　─────
　　　│　○　│　　　　　
　　　│　○　│　　　　　─→　○○○　─→
　　　│　○　│　　　　　
　　　└───┘　　　　　　　─────

　念のため、もう一度問題を載せておきますね。

> 　データ a をスタックに挿入することを、push(a)
> 　スタックからデータを取り出すことを、pop()
> 　データ a をキューに挿入することを、enq(a)
> 　キューからデータを取り出すことを、deq()
>
> 　　push(a)
> 　　push(b)
> 　　enq(pop())
> 　　enq(c)
> 　　push(d)
> 　　push(deq())
> 　　x ← pop()

　では、解いていきましょう。

> 　　push(a)：データ a をスタックに挿入

　　　　　スタック　　　　　　キュー

　　　　　│　　　│　　　　　│　　　│
　　　　　│　　　│　　　　　│　　　│
　　　　　│　a 　│　　　　　│　　　│
　　　　　└───┘

> 　　push(b)：データ b をスタックに挿入

　　　　　│　　　│　　　　　│　　　│
　　　　　│　b 　│　　　　　│　　　│
　　　　　│　a 　│　　　　　│　　　│
　　　　　└───┘

> 　　enq(pop())：スタックからデータを取り出して、キューに挿入

　　　　　│　　　│　　　　　│　　　│
　　　　　│　　　│　　　　　│　　　│
　　　　　│　a 　│　　　　　│　b 　│
　　　　　└───┘

　　　後からスタックに入った b が取り出され、b がキューに入ります。

> 　　enq(c)：データ c をキューに挿入

　　　　　│　　　│　　　　　│　　　│
　　　　　│　　　│　　　　　│　c 　│
　　　　　│　a 　│　　　　　│　b 　│
　　　　　└───┘

> 　　push(d)：データ d をスタックに挿入

　　　　　│　　　│　　　　　│　　　│
　　　　　│　d 　│　　　　　│　c 　│
　　　　　│　a 　│　　　　　│　b 　│
　　　　　└───┘

> 　　push(deq())：キューからデータを取り出して、スタックに挿入

　　　　　│　b 　│　　　　　│　　　│
　　　　　│　d 　│　　　　　│　　　│
　　　　　│　a 　│　　　　　│　c 　│
　　　　　└───┘

　　　先にキューに入った b が取り出され、b がスタックに入ります。

> 　　x ← pop()：スタックからデータを取り出して、x に代入

　　　　　│　　　│　　　　　│　　　│
　　　　　│　d 　│　　　　　│　　　│
　　　　　│　a 　│　　　　　│　c 　│
　　　　　└───┘

　　　　　　x ＝ b

　したがって、x には b が代入されます。

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
★これ、おしえてっ！（回答編）★vol.1253(2004.6.7) の質問に対する回答
----------------------------------------------------------------------

　vol.1253 の質問はこちらでした。（出典：H16.春　基本情報　問10）
----------------------------------------------------------------------

　2 種類の文字“A”，“B”を 1 個以上、最大 n 個並べた符号を作る。
　60 通りの符号を作るときの n の最小値は幾らか。

　ア　4

　イ　5

　ウ　6

　エ　7

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

　えるさんより

> 良く出る問題なのですがいつも間違えてしまいます。
> 正解は「イ」らしいのですが、何故でしょうか？
> ＡとＢを使うということは２進数と同じ要領で考え、
> 「イ」だと３２通りしかできないのでは？
> と常に思ってしまいます。

　というコメント付きでした。いかがだったでしょうか？

　○へけけくん

> 2進数を理解していると、逆にはまりそうな問題ですね(^^;
>
> 2進数の場合（というか何進数でもそうですが）　0、00、000、0000・・・
> は全て同じくゼロですよね。けれども、今回の問題は数字ではなく、
> 符号の組み合わせ方を考えるので、0と00と000は違う符合になります。
>
> 問題に即して、0をA、1をBと置き換えてみましょう。
> 符号は文字を一個以上使わなければならないので、最も短い符号はAとBです。
> 次に短い符号はAAとABとBAとBBです。
> 2進数の場合、2桁の組み合わせの数は4通りですが、さっきも書いた通り
> AとAAは別の符号と考えるため、最大n=2個の場合の組み合わせは
> 4通りではなく、A,B,AA,AB,BA,BB、の6通りになります。
>
> 同様にn=3の場合、2進数で考えると8通りですが、
> 組み合わせではn=2までの数が足されるので、8+6で14通りになります。
> あとは同じ考え方です。
> n=4なら16+14=30通り。n=5なら32+30=62通りです。
>
> よってn=5であれば60通りの符号を作れることになります。

　どうもありがとうございました。正解は「イ」ですね。
　ＡとＢの２進数って思ってしまい、引っかかった人がけっこういるのでは？

　○ヨシオさん

> 答えは、イ　5　です。
> 文字を1個並べたとき、符号は2通り出来ます。
> 文字を2個並べたとき、符号は4通り出来ます。
> 同様に、
> 3個、4個、5個並べたとき符号は
> 8通り、16通り、32通り出来ます。
>
> ここで、この問題のポイントは作成する符号は1文字でも2文字でも可。
> 最大ｎ個の文字でで符号を作成する、ということです。
>
> よって、
> 2＋4＋8＋16＋32≧60ですので、最小のｎは5文字です。

　どうもありがとうございました。
　おっしゃる通り、ポイントは作成する符号は何文字でもかまわない
　というところでしょうね。

　○もんさん

> 最初にえるさんの誤解を解消しましょう。
> まず２進数の場合は、
> 1 も 01 も 001 も 0001 ・・・も、全て 1 で同じものです。
> 対して、この問題の場合、
> A と BA と BBA と BBBA ・・・とは、異なる符合になります。
> 従って、6ビット(=64) で表せられる2進数より少ない桁数で処理できることが
> 納得できるでしょう。
>
> それでは、問題に戻ります。
>
> ＜単純解法＞
> 1桁から順に足していきましょう。
> (1桁の場合)
> 　A,B の２種類
>
> (2桁の場合)
> 　AA,AB,BA,BB (2*2=4)の４種類　→　2桁までで、2+4=6
>
> (3桁の場合)
> 　AAA,AAB,ABA,ABB,・・・ (2*2*2=8)の８種類　→　3桁までで、6+8=14
>
> (4桁の場合)
> 　AAAA,AAAB,AABA,AABB,・・・ (2*2*2*2=16)の１６種類
> 　　　　　　　　　　　　　　　　　　　　　　→　4桁までで、14+16=30
>
> (5桁の場合)
> 　AAAAA,AAAAB,AAABA,AAABB,・・・ (2*2*2*2*2=32)の３２種類
> 　　　　　　　　　　　　　　　　　　　　　　→　5桁までで、30+32=62
>
> 従って、答えは　イ。
>
> 【補足】
> ＜数式による解法＞
> 数値が大きくなったときの為に、数式による解法も考えておきましょう。
>
> A(n) = 2 + 2^2 + 2^3 + ・・・ + 2^n　とします。
>
> A(n) = 2(1 + 2 + 2^2 + ・・・ + 2^(n-1))
> 　　 = 2(1 + A(n) - 2^n)
>
> 上記を解いて、
> A(n) = 2^(n+1) - 2
>
> A(n) = 2^(n+1) - 2 >= 60 を解いて、
>
> 2^(n+1) >= 62
> n+1 >= log2(62) = log10(62)/log10(2) = 5.954196・・・
> n >= 4.954196・・・
>
> 従って、最小のnは、5。

　どうもありがとうございました。
　数式で解く場合は、底を10に直すよりも 2^n ではさみ込む不等式に
　持っていった方が良いかもしれませんね。

　○だんぼさん

> そっか、こういうのは２進数として考えればいいのですね。。
> えるさんのコメントがなかったら、きっと回りくどく、
> 変な風に考え始めていたでしょう(^^;;
>
> 仮に A を「０」、B を「１」と置いた場合。
>
> 10進数　０　１　２　３　４　５　……
> ２進数　０　１　10　11　100　101 ……
>  文字　Ａ　Ｂ　BA　BB　BAA　BAB ……
>
> と、こんな感じになりますよね。
>  60 通りの符号を作る…ということは、59 までの値を作るということと
> 同じです（0～59までの 60個）。
>
> ２進数で 60 個、値を作ろうと思ったら、
> 　2^5＝32 …×
> 　2^6＝64 …○
> ということで、６桁必要になります。ここまでだと、イの５桁だと
> 32通りしか出来ないと思ってしまうことでしょう。
>
> しかし！
> 上記で仮に置いたのを A を「１」、B を「０」とも置くことが出来るので、
> １つの数値について、文字の場合は「数値×２」通りが存在することに
> なります。
>
> なので、５桁 32 個までしか出来ませんが、通りとしてはその倍の 64 個
> 存在することになります。
>
> ただし、「０」を表記する場合、
>
>  A を０とするとき　A
>  B を０とするとき　B
>
> となり
>
>  A を０とするとき → B は１　
>  B を０とするとき → A は１　なので、
>
> 「１」を表記する場合も文字 A、B が存在し、
> 何通りかと問われた場合は、同じ並びのものが存在することになるので、
>
> 　64 － 2＝62（通り）
>
> となります。
>
> それでも５桁表記で 62通りと、問題文の 60通りを越えているので、
> 答えは５桁のままでＯＫです。
> よって、答えはイとなります。

　どうもありがとうございました。
　全然関係ないですが、"64－2" なんていう式を見ていると
　サブネットマスクの計算を思い出しますね。

　○pagipagiさん

> この問題の場合は、１桁から最大ｎ桁まで表すことのできる符号
> ということですので、１桁で表すことのできる数からｎ桁で表すことの
> できる数までの総和をとればよいことになります。
> したがって、表すことのできる数をI通りとおくと
>
> I = 2^1 + 2^2 + ,,,, + 2^n
>   = 2^(n+1) - 2 通り表すことができます。
>
> n = 4 のとき、
> I = 30
> n = 5 のとき
> I = 62 となり、これが正解になります。

　どうもありがとうございました。
　こちらは数式で解いたやり方ですね。
　数学が得意な方はこれがしっくりくるかも？

　○オケマツさん

> 記号は2通りなので，
>
> 1 個並べたとき，2^1＝2 通り (A，B)
> 2 個並べたとき，2^2＝4 通り (AA，AB，BA，BB)
> 3 個並べたとき，2^3＝8 通り (AAA，AAB，ABA，BAA，ABB，BAB，BBA，BBB)
>  ・・・
>
> この調子だと，5個並べたときには 2^5 ＝ 32 通りしかないじゃないか。
> と思うかもしれません。
>
> 私もだまされました。
>
> しかし，良ーく見ると，問題にはこうあります。
> 「1 個以上、最大 n 個」つまり，n＝5 なら 1 個から 5 個の合計です。
> 　￣￣￣￣　￣￣￣￣￣
> 1 個並べたとき，2^1＝2 通り　→ n＝1 の時，2通り
> 2 個並べたとき，2^2＝4 通り　→ n＝2 の時，2＋4＝6 通り
> 3 個並べたとき，2^3＝8 通り　→ n＝3 の時，6＋8＝14 通り
> 4 個並べたとき，2^4＝16 通り　→ n＝4 の時，14＋16＝30 通り
> 5 個並べたとき，2^5＝32 通り　→ n＝5 の時，30＋32＝62 通り
>  ・・・
>
> という訳で，n＝5 で 60 通りの符号を十分に表せます。

　どうもありがとうございました。
　ここにも引っかかってしまった方がいましたね(^^;;
　本番でやってしまった方も多かったはず。

　○ひでじぃさん

> おそらくここでポイントとなる表現は「 1 個以上、最大 n 個」だと思います。
> つまり常に最大数ではなくても良いということです。
> 候補を列挙していくと、
>
> （１個）A,B　→２通り
> （２個）AA,AB,BA,BB　→４通り
> （３個）AAA,AAB,・・,BBA,BBB　→８通り
> （４個）AAAA,AAAB,・・,BBBA,BBBB　→１６通り
> （５個）AAAAA,AAAAB,・・,BBBBA,BBBBB　→３２通り
> （６個）AAAAAA,AAAAAB・・,BBBBBA,BBBBBB　→６４通り
> 以下続く
>
> ということになるかと思います。
> ですから、符号の数は最大個数が増えるに従って、
> 2+4+8+16+32+64+・・・
> となります。32まで足したところで62ですから、最大５個が正解となります。
>
> 式で書くと、
>  n
> Σ 2^i >= 60
> i=1
> を満たす最小の整数 n を求める問題でしょうか。

　どうもありがとうございました。
　シグマを使って表せば、その式で良いでしょう。

　○オ～ッ君

> さてこの問題、わたしは「イ」と答えたのですが、試験直後の
> 某社の答え合わせでは不正解になっていたような気がしますが
> どうなのでしょうか？

　おそらく、回答例の作成者の方が引っかかってしまったんでしょう(^^;;
　どうもありがとうございました。

　○トレッキーさん

> ところで、　ｎ＝６が正解となるように問題を作るには
> どこを変えたらよいでしょうか？
>
> （何度やっても、順列、組み合わせは苦手です・・。＾＾；）

　逆に質問をしてしまいますが、どうなるでしょうか？(^^;;
　どうもありがとうございました。

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

　今回の質問はこちらです。（出典：H16.　ソフトウェア　問41）
----------------------------------------------------------------------

　再入可能（リエントラント）プログラムの説明として、
　最も適切なものはどれか。

　ア　一度実行した後、ロードし直さずに再び実行を繰り返しても、
　　　正しい結果が得られる。

　イ　実記憶上のどこのアドレスに配置しても実行することが可能である。

　ウ　複数のセグメントに分割されており、セグメント単位にロードして
　　　実行することが可能である。

　エ　複数のタスクで並行して実行しても、正しい結果が得られる。

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

　これに対する回答（解説）を６月１９日（土）の夜までにお願いします。
　このコーナーで取り上げてほしい問題のリクエストも募集中です。

　回答＆お便りはこちらからでもＯＫですよ。
　もちろん、このメールマガジンに返信していただいてもかまいません。
　http://www.shunzei.com/about/mail.html

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

> タブレット(tablet) って？

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

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

　ハンドル名を添えて mail@shunzei.com まで送ってください！
　WebからでもＯＫ！　http://www.shunzei.com/about/mail.html

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

　編集・発行：しゅんぜい　mail@shunzei.com 　　　　─ 発行部数 ─
  　　　発送：melma!　　　http://www.melma.com/ 　　　 4,823 部
　　　　　　：まぐまぐ　　http://www.mag2.com/ 　　　 12,538 部
　　　　　　：めろんぱん　http://www.melonpan.net/ 　  5,123 部
　　　　　　　　　　　　　　　　　　　　　　　　　　───────
　登録・解除：http://www.shunzei.com/mm/ 　　　　　　22,484 部(total)

　○本の購入：http://books.rakuten.co.jp/itexam/

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

　転載について： http://www.shunzei.com/about/disclaimer.html
　広告掲載に関しては mail@shunzei.com まで、直接お願いします。

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

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

　（基本情報平成１６年春問２８）の問題文より

> 入力装置の中で、ポインティングデバイスに分類され、
> CAD システムの図形入力などに使用されるもの。

　タブレット(tablet) とは、マウスなどと並ぶ
　ポインティングデバイスの１つです。

　タブレットは、板状の機器とペン型の機器がセットになっていて
　板状の機器の上でペンを動かすことで、入力を行います。

　簡単に言えば、ペンで文字や絵を描くように、パソコンへ
　文字や絵を入力できる装置です。

　タブレットの機能としては製品ごとにいろいろありますが、
　代表的なものとして、筆圧感知機能があります。

　例えば、紙に鉛筆で文字を書くときに、弱く書けば薄くなり、
　強く書けば濃くなるのと同じように、タブレットでは
　弱く書くと細い線が書けたり、強く書くと太い線が書けたりします。

　最近は、ディスプレイに直接ペンでなぞることで、簡単に入力ができる
　タブレットPCというのもありますね。

　＃タブレットの例として適当に商品を検索してみました。
　http://tablet.wacom.co.jp/products/favo3/index.html

　======

　だいぶ忙しい日々が続いています。
　先週は夜を通り越し、明るくなってからタクシーで家に帰り
　またすぐ会社に・・・という生活をしていました。

　それにも関わらず、土日は車を飛ばして長野へ。
　またしても、たっぷりと遊んでしまいました。。。

　まぁ、ごはんはしっかり食べるようにしまーす(^^;;

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
◆◆◆◆◆◆　　今週のブックスニュース（６月９日更新）　　◆◆◆◆◆◆
　　　  http://books.rakuten.co.jp/itexam/news/plf/index.html
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━