最短合格！基本情報技術者試験 午前 過去問＆解説（２－１）

テクノロジ系－アルゴリズムとプログラミング（闇コウモリの森）

スタック（Lv2 闇コウモリ）

【問題】A，B，C，Dの順に到着するデータに対して，一つのスタックだけを用いて出力可能なデータ列はどれか。

（ア）A，D，B，C

（イ）B，D，A，C

（ウ）C，B，D，A

（エ）D，C，A，B

---

【解説】

スタックは後入れ先出し(LIFO)のデータ構造で、PUSH命令とPOP命令によってデータを操作します。

“後入れ先出し”ですので、スタックに先に入れたデータは、後から入れたデータよりも先に出力することができません。

（ア）不正解×

PUSH(A)　[A]
POP(A)　 []
PUSH(B)　[B]
PUSH(C)　[BC]
PUSH(D)　[BCD]
POP(D)　 [BC]
POP(B)　 NG

BはCより先にスタックに格納されたので、Cより先にBを出力することができません。

（イ）不正解×

PUSH(A)　[A]
PUSH(B)　[AB]
POP(B)　 [A]
PUSH(C)　[AC]
PUSH(D)　[ACD]
POP(D)　 [AC]
POP(A)　 NG

AはCより先にスタックに格納されたので、Cより先にAを出力することができません。

（ウ）正解〇

PUSH(A)　[A]
PUSH(B)　[AB]
PUSH(C)　[ABC]
POP(C)　 [AB]
POP(B)　 [A]
PUSH(D)　[AD]
POP(D) 　 [A]
POP(A) 　 []

（エ）不正解×

PUSH(A)　[A]
PUSH(B)　[AB]
PUSH(C)　[ABC]
PUSH(D)　[ABCD]
POP(D)　 [ABC]
POP(C)　 [AB]
POP(A)　 NG

AはBより先にスタックに格納されたので、Bより先にAを出力することができません。

---

答え：（ウ）

---

Java（Lv3 闇コウモリ）

【問題】JavaScriptの非同期通信の機能を使うことによって，動的なユーザインタフェースを画面遷移を伴わずに実現する技術はどれか。

（ア）Ajax

（イ）CSS

（ウ）RSS

（エ）SNS

---

【解説】

（ア）正解〇

Webブラウザ内で非同期通信とインターフェイスの構築などを行う技術の総称です。

（イ）不正解×

CSSは、HTMLやXMLの要素を、どのように修飾して表示させるかを定義する文書で、Webページのデザインを記述するために用いられます。

（ウ）不正解×

RSSは、ニュースやブログなど各種のウェブサイトの更新情報を簡単にまとめ、配信するための幾つかの文書フォーマットの総称です。

（エ）不正解×

SNSは、社会的ネットワークをインターネット上で構築するサービスです。

---

【答え】（ア）

---

ハッシュ関数（Lv2 闇コウモリ）

【問題】10進法で5桁のa1a2a3a4a5をハッシュ法を用いて配列に格納したい。ハッシュ関数を mod(a1＋a2＋a3＋a4＋a5，13) とし，求めたハッシュ値に対応する位置の配列要素に格納する場合，54321は次の配列のどの位置に入るか。ここで，mod(x，13) は，xを13で割った余りとする。

（ア）1

（イ）2

（ウ）7

（エ）11

---

【解説】

ハッシュ法とは、探索するデータのキー値からデータの格納アドレスを直接計算する方法で、この計算の際に使われる関数をハッシュ関数といいます。

問題文より、ハッシュ関数が mod(a1＋a2＋a3＋a4＋a5、13) なので、そのまま”54321″を代入します。

mod()は、第1引数を第2引数で割った余りを求めるので、

　mod(5＋4＋3＋2＋1，13)

＝ mod(15，13)

＝ 2

---

【答え】（イ）

---

スタック（Lv2 闇コウモリ）

【問題】次の二つのスタック操作を定義する。
PUSH n：スタックにデータ(整数値n)をプッシュする。
POP：スタックからデータをポップする。
空のスタックに対して、次の順序でスタック操作を行った結果はどれか。　
PUSH 1 → PUSH 5 → POP → PUSH 7 → PUSH 6 → PUSH 4 → POP → POP → PUSH 3

（ア）[1,7,3]

（イ）[3,4,6]

（ウ）[3,7,1]

（エ）[6,4,3]

---

【解説】

コンピュータの世界で使われるデータ構造のひとつに「スタック」があります。

スタックは、最後に格納したデータから先に取り出す後入れ先出し（Last-in First-out：LIFO）の構造をもちます。

スタックでは、データを挿入するPUSH命令、データを取り出すPOP命令を使用してデータ操作を行います。　

PUSH(1)　[1]
PUSH(5)　[1，5]
POP　　 [1]
PUSH(7)　[1，7]
PUSH(6)　[1，7，6]
PUSH(4)　[1，7，6，4]
POP　　　[1，7，6]
POP　　　[1，7]
PUSH(3)　[1，7，3]

---

【答え】（ア）

---

行列操作（Lv3 闇コウモリ）

【問題】待ち行列に対する操作を次のとおり定義する。
ENQ n:待ち行列にデータnを挿入する。
DEQ :待ち行列からデータを取り出す。
空の待ち行列に対し、ENQ1，ENQ2，ENQ3，DEQ，ENQ4，ENQ5，DEQ，ENQ6，DEQ，DEQの操作を行った。
次にDEQ操作を行ったとき、取り出されるデータはどれか。

（ア）1

（イ）2

（ウ）5

（エ）6

---

【解説】

待ち行列(キュー構造)は、先に入ったものから先に取り出す「先入れ先出し方式」のデータ構造です。

左を待ち行列の入口、右を出口として操作に伴う待ち行列の変化を追っておきます。

ENQ1　[1]
ENQ2　[2][1]
ENQ3　[3][2][1]
DEQ 　 [3][2]
ENQ4　[4][3][2]
ENQ5　[5][4][3][2]
DEQ 　 [5][4][3]
ENQ6　[6][5][4][3]
DEQ　 [6][5][4]
DEQ　 [6][5]

次に行われるDEQ操作＝答え

DEQ　 [6] →[5]

---

【答え】（ウ）

---