平成23年春目次 平成23年秋目次 平成24年春目次 平成24年秋目次
平成23年春 午前問
にほんブログ村
2013年12月31日火曜日
2013年12月30日月曜日
＝＝＝ 目次 23年秋 ＝＝＝
平成23年春目次 平成23年秋目次 平成24年春目次 平成24年秋目次
平成23年秋 午前問
にほんブログ村
2013年12月29日日曜日
＝＝＝ 目次 24年春 ＝＝＝
平成23年春目次 平成23年秋目次 平成24年春目次 平成24年秋目次
平成24年春 午前問
にほんブログ村
2013年12月28日土曜日
2012年12月23日日曜日
＝＝＝ 平成24年秋 問3 ＝＝＝
平成24年秋目次 前の問題 次の問題
問３
探索方法とその実行時間のオーダの適切な組み合わせはどれか。ここで、検索するデータの数をnとし、ハッシュ値が衝突する（同じ値になる）確率は無視できるほど小さいものとする。また、実行時間のオーダがｎ2であるとは、ｎ個のデータを処理する時間がｃｎ2（ｃは定数）で抑えられていることをいう。
解説
■2分探索の場合たとえば1024個のデータがあったとすると、真ん中の値を1回比較することで半分に絞られるとすると、2回目で1/4、3回目で1/8・・・10回目で1/1024となるはず。
log21024=10となるので、log2nが正解
■線形探索の場合
最初からすべて見ていくため、n個のデータがあればn回比較すればよいことになるため、nが正解
■ハッシュ探索の場合
ハッシュ値とは、データから計算した値であり、それによりデータの置き場所を決めることになる。
同じ値になる確率は無視できるほど小さいといっているので、データからハッシュ値を1回計算すれば、その場所にそのデータがあるため、1回の探索で済む。
答
アにほんブログ村
2012年11月5日月曜日
＝＝＝ 平成24年秋 問2 ＝＝＝
平成24年秋目次 前の問題 次の問題
問２
与えられた正の整数Ｘ0,Ｘ1(Ｘ0＞Ｘ1)の最大公約数を、次の手順で求める。Ｘ0＝175、Ｘ1＝77の場合、手順(2)は何回実行するか。ここで、"A→B"は、AをBに代入することを表す。[手順]
(1)2→i
(2)Ｘi-2をＸi-1で割った剰余→Ｘi
(3)Ｘi＝０ならばＸi-1を最大公約数として終了する
(4)i+1→iとして(2)に戻る
ア ３ イ ４ ウ ６ エ ７
解説
1回目i=2、Ｘ0＝175、Ｘ1＝77
175を77で割った余り21をＸ2とする
i=3とする
2回目
i=3、Ｘ1＝77、Ｘ2＝21
77を21で割った余り14をＸ3とする
i=4とする
3回目
i=4、Ｘ2＝21、Ｘ3＝14
21を14で割った余り7をＸ4とする
i=5とする
4回目
i=5、Ｘ3＝14、Ｘ4＝7
14を7で割った余り0をＸ4とする
Ｘ4=0なので終了
結局(2)を4回通った
答
イにほんブログ村
2012年10月24日水曜日
＝＝＝ 平成24年秋 問1 ＝＝＝
平成24年秋目次 次の問題
問１
8ビットの2進数11010000を右の2ビット算術シフトしたものを、00010100から減じた値はどれか。ここで、負の数は２の補数表現によるものとする。ア 00001000 イ 00011111 ウ 00100000 エ 11100000
解説
算術シフトの場合、右にシフトする時、最上位ビットで埋める。つまり、10001000を右に2ビット算術シフトすると、11100010 となる。
実際に計算すると
11010000を2ビット算術シフトすると 11110100
この値は最上位ビットが１なので、負の数
これを引くということは符号を逆転して足し算しても同じ。
符号を逆転するということは２の補数をとるということなので
00010100－11110100
＝00010100＋（－11110100）
＝00010100＋00001100
＝00100000
よって、答えはウ
また、10進数に変換してから計算してもよい。 11010000は最上位ビットが１なので、負の値であることがわかる。
とりあえず正の値に直して（2の補数をとる）みると00110000。
これは10進数の48なので、元の11010000は－48であることがわかる。
これを2ビット右にシフトするということは、２で2回割るということなので、－12となる
00010100は10進数の20であるので、
20-(-12)=32 これは2進数で表現すると、00100000になるので、答えはウ
答
ウにほんブログ村
登録:
投稿 (Atom)