「厳選5題」過去問と解説 | 平成25年度 春期 の過去問やるならこれをやれ

矢沢 久雄
2020-07-08 更新

ここでは、平成 25 年度 春期 基本情報技術者試験の午前試験 の中から「やるべき問題」を5題に厳選し、ぶっちゃけた解説をさせていただきます。

やるべき問題とは、よく出る問題であり、かつ、練習すればできる問題（練習しないとできない問題）です。

厳選問題looks_oneアルゴリズムをしっかりと丁寧に覚えてください

問 6　(平成 25 年度 春期)

図は，逆ポーランド表記法で書かれた式 abcd+++ をスタックで処理するときのスタックの変化の一部を表している。 この場合，スタックの深さは最大で 4 となる。 最大のスタックの深さが最も少ない逆ポーランド表記法の式はどれか。

ア　ab+c+d+　イ　ab+cd++
ウ　abc++d+　エ　abc+d++

連載の 第 10 回（平成 26 年度秋期） で、通常の計算式を逆ポーランド表記法に変換する問題を取り上げました。

コンピュータで式の計算結果を求めるには、通常の表記法式より逆ポーランド表記法の方が、簡単なアルゴリズムで実現できます。 そのアルゴリズムを知ってますか？ というのが、この問題のテーマです。

市販教材では、滅多に紹介されていないアルゴリズムなので、この問題を通して覚えておきましょう。 以下に手順を示します。

逆ポーランド表記法の式の計算結果を求めるアルゴリズム

1. 式の先頭から 1 つずつ順番に要素を取り出す。
2. 要素が値なら、それをスタックにプッシュする（格納する）。
3. 要素が演算子なら、スタックから 2 つの要素をポップし（取り出し）、それらの演算結果をプッシュする。
4. 式の要素がなくなるまで、 1. ～ 3. を繰り返す。
5. 最後にスタックに残った値が式の計算結果なので、それをポップする。

何とも不思議な手順に思えるかもしれませんが、逆ポーランド表記法では
［値1］［値2］［演算子］
の順に要素が並んでいるので、これは当然の手順です。

式の先頭から 1 つずつ順番に要素を取り出すと、［値1］と［値2］まででは、まだ演算方法がわからないので、それらをスタックにプッシュして一時保存しておくのです。

そして、［演算子］を取り出したときに、その演算対象である［値1］と［値2］をスタックからポップして演算を行います。

演算結果をスタックにプッシュするのは、その先も式が続く場合があるからです。

こういうことは、中途半端に覚えられるものではありません。 具体例を示しますので、しっかりと丁寧に覚えてください。

たとえば、 3 + 4 × 5 という計算をするとします。

これを逆ポーランド表記法にすると
［3］［4］［5］［×］［+］
です。 先ほど示した手順で、計算結果を求めてみましょう。

以下のようになります。 この例では、スタックの最大の深さ（スタックに格納された最大の要素数）は、 3 です。

例　［3］［4］［5］［×］［+］の計算結果を求める

1. ［3］を取り出す。
2. ［3］は値なので、スタックにプッシュする。
   3
3. ［4］を取り出す。
4. ［4］は値なので、スタックにプッシュする。
   4
   3
5. ［5］を取り出す。
6. ［5］は値なので、スタックにプッシュする。
   5
   4
   3
7. ［×］を取り出す。
8. ［×］は演算子なので、スタックから 5 と 4 をポップし、4 × 5 の演算結果である 20 をプッシュする。
   20
   3
9. ［+］を取り出す。
10. ［+］は演算子なので、スタックから 20 と 3 をポップし、 3 + 20 の演算結果である 23 をプッシュする。
    23
11. 最後にスタックに残った 23 が式の計算結果なので、それをポップする。
12. 計算結果の 23 が得られる。

それでは、問題を見てみましょう。

選択肢に示された逆ポーランド表記法の式の中で、計算結果を求めたときに、スタックの最大の深さが、最も少ないものはどれか？ という問題です。

先ほど説明した手順で、スタックの絵を書いてみましょう。

選択肢ア　［a］［b］［+］［c］［+］［d］［+］の計算結果を求める
1. ［a］を取り出す。
2. ［a］は値なので、スタックにプッシュする。
   a
3. ［b］を取り出す。
4. ［b］は値なので、スタックにプッシュする。
   b
   a
5. ［+］を取り出す。
6. ［+］は演算子なので、スタックから b と a をポップし、それらの演算結果である a + b をプッシュする。
   a + b
7. ［c］を取り出す。
8. ［c］は値なので、スタックにプッシュする。
   c
   a + b
9. ［+］を取り出す。
10. ［+］は演算子なので、スタックから c と a + b をポップし、それらの演算結果である a + b + c をプッシュする。
    a + b + c
11. ［d］を取り出す。
12. ［d］は値なので、スタックにプッシュする。
    d
    a + b + c
13. ［+］を取り出す。
14. ［+］は演算子なので、スタックから d と a + b + c をポップし、それらの演算結果である a + b + c + d をプッシュする。
    a + b + c + d
15. 最後にスタックに残った a + b + c + d が式の計算結果なので、それをポップする。
16. 計算結果の a + b + c + dが得られる。
17. 選択肢アのスタックの最大の深さは、 3 です。

選択肢イ　［a］［b］［+］［c］［d］［+］［+］の計算結果を求める
1. ［a］を取り出す。
2. ［a］は値なので、スタックにプッシュする。
   a
3. ［b］を取り出す。
4. ［b］は値なので、スタックにプッシュする。
   b
   a
5. ［+］を取り出す。
6. ［+］は演算子なので、スタックから b と a をポップし、それらの演算結果である a + b をプッシュする。
   a + b
7. ［c］を取り出す。
8. ［c］は値なので、スタックにプッシュする。
   c
   a + b
9. ［d］を取り出す。
10. ［d］は値なので、スタックにプッシュする。
    d
    c
    a + b
11. ［+］を取り出す。
12. ［+］は演算子なので、スタックから d と c をポップし、それらの演算結果である c + d をプッシュする。
    c + d
    a + b
13. ［+］を取り出す。
14. ［+］は演算子なので、スタックから c + d と a + b をポップし、それらの演算結果である a + b + c + d をプッシュする。
    a + b + c + d
15. 最後にスタックに残った a + b + c + dが式の計算結果なので、それをポップする。
16. 計算結果の a + b + c + dが得られる。
17. 選択肢イのスタックの最大の深さは、 3 です。

選択肢ウ　［a］［b］［c］［+］［+］［d］［+］の計算結果を求める
1. ［a］を取り出す。
2. ［a］は値なので、スタックにプッシュする。
   a
3. ［b］を取り出す。
4. ［b］は値なので、スタックにプッシュする。
   b
   a
5. ［c］を取り出す。
6. ［c］は値なので、スタックにプッシュする。
   c
   b
   a
7. ［+］を取り出す。
8. ［+］は演算子なので、スタックから c と b をポップし、それらの演算結果である b + c をプッシュする。
   b + c
   a
9. ［+］を取り出す。
10. ［+］は演算子なので、スタックから b + c と a をポップし、それらの演算結果である a + b + c をプッシュする。
    a + b + c
11. ［d］を取り出す。
12. ［d］は値なので、スタックにプッシュする。
    d
    a + b + c
13. ［+］を取り出す。
14. ［+］は演算子なので、スタックから d と a + b + c をポップし、それらの演算結果である a + b + c + d をプッシュする。
    a + b + c + d
15. 最後にスタックに残った a + b + c + dが式の計算結果なので、それをポップする。
16. 計算結果の a + b + c + dが得られる。
17. 選択肢ウのスタックの最大の深さは、 3 です。

選択肢エ　［a］［b］［c］［+］［d］［+］［+］の計算結果を求める
1. ［a］を取り出す。
2. ［a］は値なので、スタックにプッシュする。
   a
3. ［b］を取り出す。
4. ［b］は値なので、スタックにプッシュする。
   b
   a
5. ［c］を取り出す。
6. ［c］は値なので、スタックにプッシュする。
   c
   b
   a
7. ［+］を取り出す。
8. ［+］は演算子なので、スタックから c と b をポップし、それらの演算結果である b + c をプッシュする。
   b + c
   a
9. ［d］を取り出す。
10. ［d］は値なので、スタックにプッシュする。
    d
    b + c
    a
11. ［+］を取り出す。
12. ［+］は演算子なので、スタックから d と b + c をポップし、それらの演算結果である b + c + d をプッシュする。
    b + c + d
    a
13. ［+］を取り出す。
14. ［+］は演算子なので、スタックから b + c + d と a をポップし、それらの演算結果である a + b + c + d をプッシュする。
    a + b + c + d
15. 最後にスタックに残った a + b + c + dが式の計算結果なので、それをポップする。
16. 計算結果の a + b + c + dが得られる。
17. 選択肢ウのスタックの最大の深さは、 3 です。

以上のことから、スタックの最大の深さが最も少ないのは、選択肢アの 2 です。

これで、逆ポーランド表記法の式の計算結果を求めるアルゴリズムを覚えられましたね。

解答ア

(補足) この問題では、選択肢に示された式の計算結果がすべて同じになっています。 それは、問題の例に合わせて、演算の優先順位を示すカッコを省略しているからです。

searchタグで関連記事をチェック逆ポーランド記法スタック

厳選問題looks_twoハッシュ法に関する用語をまとめて覚えよう

問 7　(平成 25 年度 春期)

10 進法で 5 桁の数 a₁ a₂ a₃ a₄ a₅ を，ハッシュ法を用いて配列に格納したい。 ハッシュ関数を mod(a₁ + a₂ + a₃ + a₄ + a₅, 13) とし、求めたハッシュ値に対応する位置の配 列要素に格納する場合， 54321 は配列のどの位置に入るか。 ここで， mod(x , 13) は、 x を 13 で割った余りとする。

ア　1　　イ　2　　ウ　7　　エ　11

「ハッシュ法」は、アルゴリズムの分野で、とてもよく出題されるテーマです。

ハッシュ法に関連して、「ハッシュ関数」と「ハッシュ値」という用語がありますので、この問題を通してまとめて覚えておきましょう。

ハッシュ法では、データの値から格納場所を決めます。 そのために使われる計算式を「ハッシュ関数」と呼び、ハッシュ関数で得られた値（格納場所）をハッシュ値と呼びます。

ここでは、
mod(a₁ + a₂ + a₃ + a₄ + a₅, 13)
という計算式が、ハッシュ関数です。

このハッシュ関数で、問題に示された 54321 というデータの格納場所を求めると、

mod(5 + 4 + 3 + 2 + 1, 13)
= mod(15, 13)
= 15 を 13 で割った余り
= 2

になります。

したがって、選択肢イが正解です。

ハッシュ（hash）は、「ごた混ぜ」という意味です。

ハッシュド・ビーフという料理のハッシュと同じ です。 ハッシュ法の考案者が、このアィディアにハッシュ法という名前を付けたのです。

たとえば、 11111 、 22222 、 33333 という値の格納場所を、先ほどのハッシュ関数で求めてみましょう。

11111 は 5 、
22222 は 10 、
33333 は 2

になります。 5 、 10 、 2 というあちこちに（ごた混ぜに）格納されるので、ハッシュなのです。

この問題には登場しませんが、ハッシュ法に関して、「シノニム」 という用語もあるので覚えておきましょう。

シノニムとは、ハッシュ値が同じになってしまうデータのことです。

たとえば、 12345 というデータと 54321 というデータは、どちらもハッシュ値が 2 になります。 シノニム（ synonym ）は、「同義語」という意味です。

ハッシュ値が同じになるデータは、ハッシュ法において同義語なのです。

もしも、シノニムが生じた場合は、ハッシュ値とは異なる場所に格納します。 そのためのアルゴリズムは、いくつか考えられますが、必ず問題に示されているので、どうぞご心配なく。

解答イ

厳選問題looks_3メモリのアドレス指定方式をまとめて覚えよう

問10　(平成 25 年度 春期)

主記憶のデータを図のように参照するアドレス指定方式はどれか。

ア　間接アドレス指定　　
イ　指標アドレス指定
ウ　相対アドレス指定　　
エ　直接アドレス指定

コンピュータの記憶装置であるメモリ（この問題では「主記憶」と呼んでいます）の内部には、データを格納する箱が並んでいます。

それぞれの箱には、識別のための番号が割り振られていて、それを「アドレス」と呼びます。 アドレス（ address ）を直訳すると「番地」なので、アドレスの数値は、 20 番地 や 25 番地 と呼びます。

プログラムの命令で、処理の対象となるデータが格納されたアドレスを指定する方式には、いくつかの種類があり、それぞれに名前が付けられています。

この問題は、アドレス指定方式の名前と意味がわかるかどうかを問うものです。

選択肢には、 4 つのアドレス指定方式が示されていますが、ウの「相対アドレス指定」は、やや特殊なものなので、その他の「直接アドレス指定」「間接アドレス指定」「指標アドレス指定」の3つの意味をしっかりと覚えてください。

直接アドレス指定

たとえば「 100 番地のデータを読み出して処理せよ」という方式です。

処理の対象となるデータが格納された 100 番地というアドレスを直接指定しています。 だから、直接アドレス指定 と呼ぶのです。

間接アドレス指定

たとえば「 100 番地のデータを読み出したら、その値が示すアドレスに処理の対象となるデータがあるので、それを読み出して処理せよ」という方式です。

もしも、 100 番地 に 200 という値が格納されていたら、 200 番地 に処理の対象となるデータがあります。 直接 200 番地 を指定せずに、 100 番地 を通して間接的に指定しているので、間接アドレス指定 と呼ぶのです。

指標アドレス指定

たとえば「 100 番地 を起点として、そこから 10 番地先にあるデータを読み出して処理せよ」という方式です。

この場合、起点からの距離を示す 10 を指標（インデックス）と呼びます。 指標を使うので、指標アドレス指定 と呼ぶのです。

それでは、問題を見てみましょう。

問題に示された図では、 20 番地 のデータを読み出し、そこに 25 という値が格納されていて、 25 番地 に処理の対象となるデータがあります。

これは、間接アドレス指定 です。 したがって、選択肢アが正解です。

解答ア

厳選問題looks_4こういう問題こそ練習しておくべきです

たっぷりと計算をさせられそうで、見るだけで嫌になってしまうような問題ですね。

しかし、こういう問題こそ練習しておくべきです。 なぜなら、事前に練習しておかないと、試験当日に、どこから手を付けてよいか悩んでしまうからです。

問題を解く手順を説明しますので、しっかりと練習しておきましょう。

まず、フルバックアップの 100 GB をとった日曜日から、磁気ディスクが故障した金曜日の増分バックアップ後までの、データ量を書き出してみましょう。

問題文に「増分バックアップは直前に行ったバックアップとの差分だけ」と示され、バックアップシステムの仕様に「変更されるデータ量」が「 5 G バイト / 日」とあるので、月曜日から金曜日の増分バックアップは、それぞれ 5 G バイトです。

次に、データを復元するために必要となる「磁気テープの取り替え」と「磁気テープからのリストア」の作業内容を書き出してみましょう。

次に、それぞれの作業の時間を書き出してみましょう。

磁気テープの取り換え作業は、データ量にかかわらず 100 秒 / 本 です。 磁気テープからのリストア作業は、 10 秒 / G バイト です。

最後に、すべての作業時間を合計します。
(100 + 1000) + (100 + 50) × 5 = 1850 秒
となるので、選択肢エが正解です。

もしも、この問題を難しいと感じたなら、「他にも似たような問題を探してやってみよう」とは思わずに、この問題を何度も繰り返し練習 してください。

試験では、同じ問題が何度も再利用されているからです。

解答エ

厳選問題looks_5ディジタル署名におけるハッシュ関数の意味も知っておこう

先ほどの厳選問題 2 でハッシュ法に関する用語を紹介しましたが、その中にあったハッシュ関数という用語は、ディジタル署名でも使われます。

IT 業界では、同じ事物を様々な用語で呼んだり、同じ用語を様々な場面で使うことがあります。 そのため「正式名称は何だろう？」とか「自分の知ってる意味と違う？」などと思うと、余計にわかりにくくなります。

「いろいろあるのだ！」と思えばよいのです。 それを知っていただくために、この問題を選びました。

問題に示された「メッセージ」とは、ネットワークで送る文書のことです。

ディジタル署名では、この文書を構成するすべての文字を使って計算を行うハッシュ関数を用意します。

そして、そのハッシュ関数で得られたハッシュ値（問題では「ダイジェスト」と呼んでいます）を、送信者 A しから知らない 秘密鍵（問題では「署名生成鍵」と呼んでいます）で暗号化 して、それをディジタル署名とします。

1. 送信者 A は、メッセージ と ディジタル署名 を受信者 B に送ります。
2. 受信者 B は、送信者 A と同じハッシュ関数（ハッシュ関数の計算方法は秘密ではありません）を使って、受け取った文書のハッシュ値を求めます。
3. さらに、送信者 A の 公開鍵（問題では「署名検証鍵」と呼んでいます）を使って、受け取ったディジタル署名を復号 してハッシュ値を得ます。

これら 2 つのハッシュ値が一致したら、文書に改ざんがないことと、送信者 A になりますましがないこと（メッセージが送信者 A からのものであること）を確認できます。

なぜなら、もしも 文書に改ざんがあれば、ハッシュ値が一致しない からです。

送信者 A の公開鍵でディジタル署名が復号できたのは、送信者が確かに送信者 A だからです。 したがって、正解は、選択肢アです。

この問題のテーマは、ディジタル署名の仕組みを知っているかどうかを問うものでしたが、 IT 業界では、同じ事物を様々な用語で呼んだり、同じ用語を様々な場面で使うことがある、ということにも注目してください。

解答ア

searchタグで関連記事をチェック公開鍵秘密鍵

記事をお読みいただきありがとうございます。

もしも、一度解いただけでは、よくわからない問題があったなら、わかるまで何度でも練習してください。 「やるべき問題」は「わかるまでやるべき問題」だからです。

この厳選問題大全集が、受験者の皆様のお役に立てば幸いです。

「厳選5題」過去問と解説｜令和元年度 秋期 の過去問やるならこれをやれ

update 2020-09-08

「厳選5題」過去問と解説｜平成31年度 春期 の過去問やるならこれをやれ

update 2020-09-08

「厳選5題」過去問と解説｜平成21年度 秋期 の過去問やるならこれをやれ

update 2020-12-09

「厳選5題」過去問と解説 | 平成22年度 春期 の過去問やるならこれをやれ

update 2020-09-08

「厳選5題」過去問と解説 | 平成22年度 秋期 の過去問やるならこれをやれ

update 2022-08-17

「厳選5題」過去問と解説 | 平成23年度 春期 の過去問やるならこれをやれ

update 2020-03-04

「厳選5題」過去問と解説 | 平成23年度 秋期 の過去問やるならこれをやれ

update 2020-09-08

「厳選5題」過去問と解説 | 平成24年度 春期 の過去問やるならこれをやれ

update 2020-03-04

「厳選5題」過去問と解説 | 平成24年度 秋期 の過去問やるならこれをやれ

update 2020-03-04

「厳選5題」過去問と解説 | 平成25年度 春期 の過去問やるならこれをやれ

update 2020-07-08

矢沢 久雄

『プログラムはなぜ動くのか』（日経BP）が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”

大手電気メーカーでＰＣの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識０ベースのＩＴエンジニアや一般書店フェアなどの一般的なＰＣユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。

主な著作物

• 「プログラムはなぜ動くのか」（日経BP）
• 「コンピュータはなぜ動くのか」（日経BP）
• 「出るとこだけ! 基本情報技術者」 (翔泳社)
• 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」（翔泳社）
• 「ｉｆとｅｌｓｅの思考術」（ソフトバンククリエイティブ）　など多数