「厳選5題」過去問と解説 | 平成24年度 秋期 の過去問やるならこれをやれ
2020-03-04 更新
ここでは、平成24年度 秋期 基本情報技術者試験の午前試験 の中から「やるべき問題」を5題に厳選し、ぶっちゃけた解説をさせていただきます。
やるべき問題とは、よく出る問題であり、かつ、練習すればできる問題（練習しないとできない問題）です。
もくじ
厳選問題looks_one2 の補数表現と算術右シフトをマスターしよう
問 1 (平成 24 年度 秋期)
8 ビットの 2 進数 11010000 を右に 2 ビット算術シフトしたものを，00010100 から
減じた値はどれか。 ここで，負の数は 2 の補数表現によるものとする。
ア 00001000 イ 00011111 ウ 00100000 エ 11100000
この問題を解くには、「 2 の補数表現」および「算術右シフト」の知識が必要になります。
これらを「苦手です！」という人が多いようですが、それならばこそ、この問題を通して苦手を克服してください。 苦手を克服すれば、確実に得点アップにつながるからです。
2 の補数表現は、マイナス符号を使わずに 0 と 1 だけでマイナスの数を表す仕組み です。
2 の補数表現では、2 進数の最上位桁を「符号ビット」と呼び、符号ビットが 0 ならプラスの数を表し、 1 ならマイナスの数を表します。
問題に示された 11010000 は、最上位桁が 1 なので、マイナスの数を表しています。
ここまでは、OK でしょうか？
算術右シフトは、右方向つまり下位桁に桁をずらして、割り算を行うことです。
その際に、桁をずらしても符号ビットが変わらないように、符号ビットを除いた部分をシフトします。 そして、シフトして空いた上位桁には、符号ビットと同じ数を入れます。
ここでは、 11010000 を 2 ビット算術右シフトするのですから、
最上位桁の [ 1 ] 1010000 を除いた
1 [ 1010000 ] の部分を下位桁に 2 桁ずらして
1 [ xx10100 ] とし、
空いた上位桁の
1 [ xx ] 10100 の部分に符号ビットと同じ 1 を入れて、
1 [ 11 ] 10100
にします。
空いた桁に符号ビットと同じ値を入れることで、ちゃんと割り算の結果になるのです。
ここまでは、OK でしょうか？
もう少しで問題が解けますから、がんばってください。
11010000 を 2 ビット算術右シフトした結果は、
11110100 になりました。 符号ビットが 1 なので、 11110100 は、マイナスの数です。
これを 00010100 から引くのですから、 11110100 を同じ絶対値のままプラスの値にして足せばよいことになります。
マイナスの数を引くのは、同じ絶対値のプラスの数を足すことと同じだからです。
たとえば、 8 -（ -5 ）は、8 + 5 です。
ここまでは、OK でしょうか？
2 の補数表現では、「反転して 1 を足す」という操作を行うことで、同じ絶対値のまま、プラスの数をマイナスの数に、マイナスの数をプラスの数に変換できます。
11110100 を反転する（ 0 を 1 に、 1 を 0 にする）と、
00001011 です。
00001011 に 1 を足すと、
00001100 です。
したがって、結果は、
00010100 + 00001100 = 00100000
となり、ウが正解です。 いかがでしょう。
何となくわかったなら、実際に、手作業で計算を行ってみてください。 そうすれば、きっと 2 の補数表現と算術右シフトをマスターできるはずです！
解答 ウ
厳選問題looks_two探索アルゴリズムの計算量のオーダを覚えよう
探索方法とその実行時間のオーダの適切な組合せはどれか。 ここで，探索するデータの数を n とし，ハッシュ値が衝突する (同じ値になる) 確率は無視できるほど小さいものとする。 また，実行時間のオーダが n2 であるとは，n 個のデータを処理する時間が cn2 (c は定数) で抑えられることをいう。
| 2 分探索 | 線形探索 | ハッシュ探索 | |
|---|---|---|---|
| ア | log2n | n | 1 |
| イ | nlog2n | n | log2n |
| ウ | nlog2n | n2 | 1 |
| エ | n2 | 1 | n |
あれこれ難しそうなことが書かれていますが、この問題のテーマは「計算量のオーダ」です。
「計算量」とは、計算の量、つまり処理回数のことで、同じ目的のアルゴリズムを比較するために使われます。
基本情報技術者試験では、「データが n 個ある場合の最大の処理回数を n を使った式で示したもの」を 計算量 とします。
実際の処理回数は、
2n2 + 5n + 7
のように係数や定数を持つものとなりますが、それらを省略して、さらに最大の次数で示します。
2n2 + 5n + 7 という処理回数の場合は、係数と定数を省略して
n2 + n
とし、さらに最大の次数である
n2
で示します。 これが「オーダ」です。 オーダ（ order ）は、直訳すると「次数」や「規模」という意味です。
この問題は、探索という同じ目的を持った「二分探索」「線形探索」「ハッシュ探索」という 3 つのアルゴリズムのオーダを知っていますか？ という内容です。
線形探索のオーダが、最もわかりやすいので、まず、それでオーダのイメージをつかんでください。
線形探索は、「配列の先頭から順に 1 つずつ要素をチェックする」というアルゴリズムです。
要素が 10 個あれば、最大で 10 回の処理を行います。
要素が 100 個あれば、最大で 100 回の処理を行います。
要素が n 個あれば、最大で n 回の処理を行います。
したがって、線形探索のオーダは n です。
次は、ハッシュ探索です。
ハッシュ探索は、「データの値に計算式を適用して格納場所を決める」というアルゴリズムです。
たとえば、「データの値を 10 で割った余りを求める」という計算式を適用すれば、
58 というデータの格納場所は、
58 mod 10 = 8
になります（ mod は、割り算の余りを求める演算子だとします）。
この仕組みから、ハッシュ探索のオーダは、理想的には 1（ 1 回の処理で目的の値が見つかる）です。 データの値がわかれば、 1 回の処理で格納場所がわかるからです。
ここで「理想的」と断っているのは、後から同じ格納場所になってしまうデータが生じた場合は、別の場所に格納することになるので、 1 回の処理で格納場所がわからないからです。
そこで、問題文には、「ハッシュ値が衝突する（同じ値になる）確率は無視できるほど小さいものとする」と示されています。
「ハッシュ値」とは、計算式で得られた格納場所のことです。 これが同じ値になる確率が無視できるほど小さいのですから、ここでは、ハッシュ法のオーダは 1 で OK です。
最後に二分探索のオーダです。 これは、
log2n
という表現になります。
log は、高校で習ったはずですが、意味を覚えていますか？
もしも、忘れてしまったら、
「 log2n は、 n 個のものを 1 個にする分割回数である」
ということと、
具体例として
「 log28 = 3（ 8 個のものを 1 個にする分割回数は 3 である）」
を覚えてください。
要素数 8 個の配列は、
1 回目の分割で 8 個が 4 個になり、
2 回目の分割で 4 個が 2 個になり、
3 回目の分割で 2 個が 1 個になります。
この最後の 1 個までチェックするのが、最大の処理回数になります。
二分探索は、「探索対象の真ん中の値をチェックし、その結果から探索対象を二分割して絞り込むことを繰り返す」というアルゴリズムです。 だから、二分探索の計算量は、log2n なのです。
以上のことから、正解はアです。
解答 ア
厳選問題looks_3ビット数とコードのイメージをつなげよう
問 4 (平成 24 年度 秋期)
英字の大文字 ( A ~ Z ) と数字 ( 0 ~ 9 ) を同一のビット数で一意にコード化するには，少なくとも何ビットが必要か。
ア 5 イ 6 ウ 7 エ 8
「コード化（符号化）」とは、本来は数値でない情報を、数値に置き換えて表すことです。 置き換えられた数値を「コード」と呼びます。
この問題は、文字と数字を 2 進数のコードにするには、何ビット（ 2 進数で何桁）が必要になるかを答えるものです。
2 進数の 1 ビットは、 0 と 1 の 2 種類のコードを表せます。
- 2 ビットなら
- 00 、 01 、 10 、 11 の 4 種類
- 3 ビットなら
- 000 、 001 、 010 、 011 、 100 、 101 、 110 、 111 の 8 種類
つまり、 1 ビットで 2 種類のコードを表せ、その後はビット数が 1 桁増えるごとに表せるコードの種類が 2 倍になるのです。
選択肢に示された 5 ビット、6 ビット、7 ビット、8 ビットで表せるコードの種類は、以下のようになります。
- 5 ビット
- 2 × 2 × 2 × 2 × 2 = 32 種類
- 6 ビット
- 2 × 2 × 2 × 2 × 2 × 2 = 64 種類
- 7 ビット
- 2 × 2 × 2 × 2 × 2 × 2 × 2 = 128 種類
- 8 ビット
- 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 256 種類
A ～ Z の 26 文字と 0 ～ 9 の 10 文字を合わせると 36 文字なので、全部で 36 種類のコードが必要です。
5 ビットの 32 種類では足りません。 6 ビットの 64 種類あれば足りるので、イの 6 ビットが正解です。
解答 イ
以下に、36 文字を 6 ビットのコードに置き換えた例を示します。 これを見れば、ビット数とコードのイメージがつながるでしょう。
未使用のコードがあるので、もったいない感じがしますが、5 ビットでは足りないので、6 ビットにしなければなりません。
| コード | 文字 | コード | 文字 |
|---|---|---|---|
| 0 | A | 10000 | Q |
| 1 | B | 10001 | R |
| 10 | C | 10010 | S |
| 11 | D | 10011 | T |
| 100 | E | 10100 | U |
| 101 | F | 10101 | V |
| 110 | G | 10110 | W |
| 111 | H | 10111 | X |
| 1000 | I | 11000 | Y |
| 1001 | J | 11001 | Z |
| 1010 | K | 11010 | 0 |
| 1011 | L | 11011 | 1 |
| 1100 | M | 11100 | 2 |
| 1101 | N | 11101 | 3 |
| 1110 | O | 11110 | 4 |
| 1111 | P | 11111 | 5 |
| コード | 文字 | コード | 文字 |
|---|---|---|---|
| 100000 | 6 | 110000 | (未使用) |
| 100001 | 7 | 110001 | (未使用) |
| 100010 | 8 | 110010 | (未使用) |
| 100011 | 9 | 110011 | (未使用) |
| 100100 | (未使用) | 110100 | (未使用) |
| 100101 | (未使用) | 110101 | (未使用) |
| 100110 | (未使用) | 110110 | (未使用) |
| 100111 | (未使用) | 110111 | (未使用) |
| 101000 | (未使用) | 111000 | (未使用) |
| 101001 | (未使用) | 111001 | (未使用) |
| 101010 | (未使用) | 111010 | (未使用) |
| 101011 | (未使用) | 111011 | (未使用) |
| 101100 | (未使用) | 111100 | (未使用) |
| 101101 | (未使用) | 111101 | (未使用) |
| 101110 | (未使用) | 111110 | (未使用) |
| 101111 | (未使用) | 111111 | (未使用) |
厳選問題looks_4仮想記憶のページインとページアウトを手作業で練習しておこう
問 19 (平成 24 年度 秋期)
ページング方式の仮想記憶において，ページ置換えアルゴリズムに LRU 方式を採用する。 主記憶に割り当てられるページ枠が 4 のとき，ページ 1 , 2 , 3 , 4 , 5 , 2 , 1 , 3 , 2 , 6 の順にアクセスすると，ページ 6 をアクセスする時点で置き換えられるページはどれか。 ここで，初期状態では主記憶にどのページも存在しないものとする。
ア 1 イ 2 ウ 4 エ 5
「ページング方式の仮想記憶」とは、プログラムやデータを「ページ」と呼ばれる固定サイズで区切り、実メモリ（主記憶）と仮想メモリ（ハードディスク）の間で、ページの入れ換えをすること です。
実メモリの容量が足りなくなったときに、今度使われる可能性が低いページを仮想メモリに追い出し（ページアウト）、空いたページに必要なページを読み込む（ページイン）のです。
具体例が示されて「仮想記憶のページアウトとページインを手作業でやりなさい」という問題は、午前試験にも午後試験にもよく出題されます。
なかなか面倒な作業なので、事前に練習しておかないと戸惑うと思います。 ここでやっておきましょう。
この問題では、ページ枠（実メモリのページ数）が 4 個で、LRU 方式でページの入れ換えを行います。
LRU は、Least Recently Used の略で、直訳すると「最も～でない、最近、使われる」であり、わかりやすい言葉にすると「最後に使われてから最も時間が経過したページを入れ換える」です。
紙の上に 4 つの枠を書いてください。 これが、実メモリの 4 ページを表します。 最初は、どのページも未使用です。
ここに、 1 、2 、3 、4 、5 、2 、 1 、3 、2 、6 の順にアクセスして（利用して）いきます。
実メモリが空いていれば、そのままページインします。 実メモリが一杯のときは、LRU 方式でページアウトしてからページインします（これがページの入れ換えです）。
この問題では、最後の 6 をアクセスするときにページアウトされるページを答えます。
以下に手順を示しますので、やり方がわかったら、実際にやってみてください。 ★ マークは、LRU 方式におけるページアウトの対象となるページを意味しています。 このようなマークを付けるとわかりやすいはずです。
- 初期状態
- 1 をアクセスする（ 1 がページインされる）
- 2 をアクセスする（ 2 がページインされる）
- 3 をアクセスする（ 3 がページインされる）
- 4 をアクセスする（ 4 がページインされ、 1 がページアウトの対象になる）
- 5 をアクセスする（ 1 がページアウトされ、5 がページインされ、2 がページアウトの対象になる）
- 2 をアクセスする（ 3 がページアウトの対象になる）
- 1 をアクセスする（ 3 がページアウトされ、 1 がページインされ、4 がページアウトの対象になる）
- 3 をアクセスする（ 4 がページアウトされ、3 がページインされ、5 がページアウトの対象になる）
- 2 をアクセスする
- 6 をアクセスする（ 5 がページアウトされ、6 がページインされ、 1 がページアウトの対象になる）
| (空き) |
| (空き) |
| (空き) |
| (空き) |
| 1 |
| 1 |
| 2 |
| 1 |
| 2 |
| 3 |
| 1 grade |
| 2 |
| 3 |
| 4 |
| 5 |
| 2 grade |
| 3 |
| 4 |
| 5 |
| 2 |
| 3 grade |
| 4 |
| 5 |
| 2 |
| 1 |
| 4 grade |
| 5 grade |
| 2 |
| 1 |
| 3 |
| 5 grade |
| 2 |
| 1 |
| 3 |
| 6 |
| 2 |
| 1 grade |
| 3 |
6 をアクセスするときにページアウトされるのは、ページ 5 です。 したがって、エが正解です。
解答 エ
厳選問題looks_5 関係データベースの参照の整合性の意味を覚えよう
関係データベースの “注文” 表の “顧客番号” は，”顧客” 表の主キー “顧客番号” を参照する外部キーである。 このとき，参照の整合性を損なうデータ操作はどれか。 ここで，ア ~ エの記述におけるデータの並びは，それぞれの表の列の並びと同順とする。
| 伝票番号 | 顧客番号 |
|---|---|
| 0001 | C005 |
| 0002 | K001 |
| 0003 | C005 |
| 0004 | D010 |
| 顧客番号 | 顧客名 |
|---|---|
| C005 | 福島 |
| D010 | 千葉 |
| K001 | 長野 |
| L035 | 宮崎 |
この問題のテーマは、関係データベースの「参照の整合性」です。
関係データベースの DBMS（ Data Base Management System ）には、参照の整合性を保つ機能があり、それを損なう操作を受け付けません。
それがどういう意味なのか、この問題を通して覚えてください。
関係データベースでは、表に「主キー」を設定します。 主キーは、他と重複しないユニークな列 であり、それによってレコードを特定できます。 注文表では、伝票番号が主キーであり、顧客表では、顧客番号が主キーです。
注文表の列には、顧客表の主キーである顧客番号があります。 このような 他の表の主キーを「外部キー」 と呼びます。
「ある表の外部キー」→「他の表の主キー」で、表から表を参照できます。 参照とは、表から他の表をたどることであり、「リレーションシップ」とも呼びます。
参照の整合性とは、参照先のレコードが存在するように保つ機能です。
たとえば、先ほどの例で、顧客表の
［ C005 福島 ］
というレコードを削除する操作をすると、注文表の
［ 0001 C005 ］
というレコードからたどれなくなってしまうので（参照ができなくなってしまうので）、その操作を DBMS が受け付けません。
これで、参照の整合性の意味をおわかりいただけましたね。 それでは、選択肢を見てみましょう。
選択肢アは、顧客表の［ L035 宮崎 ］というレコードを削除しています。 注文表には［ L035 宮崎 ］を参照しているレコードはないので、参照の整合性は損なわれません。
選択肢イは、注文表に［ 0005 D010 ］というレコードを追加しています。 顧客表には［ D010 千葉 ］というレコードがあるので、参照の整合性は損なわれません。
選択肢ウは、注文表に［ 0006 F020 ］というレコードを追加しています。 顧客表には［ F020 ］という顧客番号のレコードはないので、この操作をすると参照の整合性が損なわれます。 したがって、ウが正解です。
念のため選択肢エも確認しておきましょう。 注文表から［ 0002 K001 ］を削除しても、参照の向きが注文表から顧客表なので、参照の整合性は損なわれません。
解答 ウ
記事をお読みいただきありがとうございます。
もしも、一度解いただけでは、よくわからない問題があったなら、わかるまで何度でも練習してください。 「やるべき問題」は「わかるまでやるべき問題」だからです。
この厳選問題大全集が、受験者の皆様のお役に立てば幸いです。
label 関連タグ
免除試験を受けた 74.9% の方が、科目A免除資格を得ています。
「厳選5題」過去問と解説｜令和元年度 秋期 の過去問やるならこれをやれ
update
「厳選5題」過去問と解説｜平成31年度 春期 の過去問やるならこれをやれ
update
「厳選5題」過去問と解説｜平成21年度 秋期 の過去問やるならこれをやれ
update
「厳選5題」過去問と解説 | 平成22年度 春期 の過去問やるならこれをやれ
update
「厳選5題」過去問と解説 | 平成22年度 秋期 の過去問やるならこれをやれ
update
「厳選5題」過去問と解説 | 平成23年度 春期 の過去問やるならこれをやれ
update
「厳選5題」過去問と解説 | 平成23年度 秋期 の過去問やるならこれをやれ
update
「厳選5題」過去問と解説 | 平成24年度 春期 の過去問やるならこれをやれ
update
「厳選5題」過去問と解説 | 平成24年度 秋期 の過去問やるならこれをやれ
update
「厳選5題」過去問と解説 | 平成25年度 春期 の過去問やるならこれをやれ
update『プログラムはなぜ動くのか』（日経BP）が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”
大手電気メーカーでＰＣの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識０ベースのＩＴエンジニアや一般書店フェアなどの一般的なＰＣユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。
主な著作物
- 「プログラムはなぜ動くのか」（日経BP）
- 「コンピュータはなぜ動くのか」（日経BP）
- 「出るとこだけ! 基本情報技術者」 (翔泳社)
- 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」（翔泳社）
- 「ｉｆとｅｌｓｅの思考術」（ソフトバンククリエイティブ） など多数
