確認○×問題まとめ14

ITパスポート講座のテクノロジ系14(アルゴリズムとプログラミング)の確認○×問題だけを集めました。

データ構造

問14-1-1

情報を格納する表のことをテーブルと呼び、データを1行に並べたものをフィールド、表の列にあたるものをレコードという。

答え:×

フィールドとレコードの説明が逆になっています。正しくは以下の記述となります。

情報を格納する表のことをテーブルと呼び、データを1行に並べたものをレコード、表の列にあたるものをフィールドという。

問14-1-2

二つの変数xとyに対して、次の手続きを1から順に実行する。処理が終了したとき、xの値は”4”になる。

(手続き)

  1. xに2を代入し、yに3を代入する。
  2. yの値から1を引いたものをyに代入する。
  3. xの値とyの値を加えたものをxに代入する。
  4. y≠1なら手続き2に戻り、y=1なら終了する。

答え:×

変数xと変数yの値を表にすると次のようになります。

手続き変数x変数y
123
222(=3-1)
34(=2+2)2
44y≠1なので手続き2に戻る
241(=2-1)
35(=4+1)1
45y=1なので終了

以上より、処理が終了したときのxの値は”5”になります。

問14-1-3

変数AとBに格納されているデータを入れ替えたい。データを一時的に格納するための変数をTMPとすると、次の手順によってデータを正しく入れ替えることができる。ここで”x←y”は、yのデータでxの内容を置き換えることを表す。

  1. TMP←A
  2. A←B
  3. B←TMP

答え:〇

変数AとBに格納されているデータを入れ替えたい場合、いきなり「A←B」としてしまうと、AのデータがBのデータで上書きされ、Aの内容が消えてしまいます。そこで、いったん変数TMPにAのデータを逃がしてやる必要があります。

変数Aに格納されているデータを「a」、変数Bに格納されているデータを「b」として考えていきます。

手順変数A変数BTMP
1aba
2bba
3baa

問14-1-4

木構造では、ひとつの親要素がもつ子要素は常に2つでなければならない。

答え:×

ひとつの要素が複数の子要素を持ったデータ構造を木構造(ツリー構造)といいます。なお、要素が最大で2つの子を持つ木構造のことを2分木(バイナリツリー)といいます。

問14-1-5

下から上へ品物を積み上げて、上にある品物から順に取り出す装置がある。この装置に対する操作は、次の二つに限られる。

PUSH x:品物 xを1個積み上げる。
POP:一番上の品物を1個取り出す。

最初は何も積まれていない状態から開始して、a、b、cの順で三つの品物が到着する。一つの装置だけを使った場合、以下のPOP操作で取り出される品物の順番として不可能なものが2つある。

  1. a,b,c
  2. b,a,c
  3. c,a,b
  4. c,b,a

答え:×

スタックは、コンピュータにおける基本的なデータ構造の1つで、データを後入れ先出し(LIFO: Last In First Out)の構造で保持します。push(プッシュ)で指定したデータを追加し、pop(ポップ)でデータを1個取り出します。

1.の順番での取り出し(可能):a,b,c

①push a:[a]

②pop:[ ]→aを取り出す

③push b:[b]

④pop:[ ]→bを取り出す

⑤push c:[c]

⑥pop:[ ]→cを取り出す

2.の順番での取り出し(可能):b,a,c

①push a:[a]

②push b:[a,b]

③pop:[a,b]→bを取り出す

④pop:[a]→aを取り出す

⑤push c:[c]

⑥pop:[ ]→cを取り出す

3.の順番での取り出し(不可能):c,a,b

①push a:[a]

②push b:[a,b]

③push c:[a,b,c]

④pop:[a,b]→cを取り出す

⑤次にpop操作をするとbが取り出されます。したがって、スタックではcの次にaを取り出すことはできません。

4.の順番での取り出し(可能):c,b,a

①push a:[a]

②push b:[a,b]

③push c:[a,b,c]

④pop:[a,b]→cを取り出す

⑤pop:[a]→bを取り出す

⑥pop:[ ]→aを取り出す

以上より、POP操作で取り出される品物の順番として不可能なものは1つ(3.の順番)です。

問14-1-6

先入れ先出し(First-In First-Out, FIFO)処理を行うのに適したキューと呼ばれるデータ構造に対して「8」、「1」、「6」、「3」 の順に値を格納してから、取出しを続けて2回行った。2回目の取出しで得られる値は「1」である。

答え:〇

キューは、コンピュータにおける基本的なデータ構造の1つで、データを先入れ先出し(FIFO: First In First Out)の構造で保持します。enq(エンキュー)で指定したデータを追加し、deq(デキュー)でデータを1 個取り出します。

キューでは古いデータから先に取り出すため「8」、「1」、「6」、「3」の順に値を格納した場合、取り出しの順番も「8」、「1」、「6」、「3」の順になります。したがって、2回目の取出しで得られる値は「1」となります。

問14-1-7

スタックとキューの二つのデータ構造がある。次の手続を順に実行した場合、変数xに代入されるデータは「b」である。ここで、

データyをスタックに挿入することを push(y)、

スタックからデータを取り出すことを pop()、

データyをキューに挿入することを enq(y)、

キューからデータを取り出すことを deq()、

とそれぞれ表す。

①push(a)

②push(b)

③enq(pop())

④enq(c)

⑤push(d)

⑥push(deq())

⑦x ← pop()

答え:〇

少しややこしいのですが、図を描きながら考えるとわかりやすいと思います。

①push(a):スタックに「a」を追加する

②push(b):スタックに「b」を追加する

③enq(pop()):キューに「スタックから取り出した値(b)」を追加する

④enq(c):キューに「c」を追加する

⑤push(d):スタックに「d」を追加する

⑥push(deq()):スタックに「キューから取り出した値(b)」を追加する

⑦x ← pop():xに「スタックから取り出した値(b)」を代入する

よって、変数xに代入されるデータは「b」となります。

アルゴリズムとプログラミング1

問14-2-1

図1のように二つの正の整数A1、A2を入力すると、二つの数値B1、B2を出力するボックスがある。B1はA2と同じ値であり、B2はA1をA2で割った余りである。図2のように、このボックスを2個つないだ構成において、左側のボックスのA1として49、A2として11を入力したとき、右側のボックスから出力されるB2の値は「5」となる。

答え:×

・左側のボックス:入力A1=49、入力A2=11

出力B1は「11」(A2 → B1)となります。

出力B2は「5」(A1/A2の余り→ B2)となります。

・右側のボックス:入力A1=B1=11、入力A2=B2=5

出力B1は「5」(A2 → B1)となります。

出力B2は「1」(A1/A2の余り→ B2)となります。

以上より、右側のボックスから出力されるB2の値は「1」となります。

問14-2-2

9けたの数字に対して、次のルールでチェックディジットを最後尾につけることにした。チェックディジットを付加した10けたの数字として「6655333331」は正しい。

ルール1:各けたの数字を合計する。

ルール2:ルール1で得られた数が2けたになった場合は、得られた数の各けたの数字を合計する。この操作を、得られた数が1けたになるまで繰り返す。

ルール3:最終的に得られた1けたの数をチェックディジットとする。

答え:〇

チェックディジット(検査数字)とは、符号の入力誤りなどを検出するために元の符号に付加される数字のことです。チェックディジットを最後尾につける前の9桁の数字は「665533333」なので、これを使って検証していきます。

・ルール1:各けたの数字を合計。

6+6+5+5+3+3+3+3+3=37

・ルール2:ルール1で得られた数が2けたなので、各けたの数字を合計。

3+7=10

2けたなので、再度各けたの数字を合計。

1+0=1

・ルール3:最終的に得られた1けたの数「1」をチェックディジットとして最後尾につける。

「665533333」+「1」→「6655333331」

問14-2-3

大文字の英字から成る文字列の暗号化を考える。暗号化の手順と例は次のとおりである。この手順で暗号化した結果が “EGE” であるとき、元の文字列は”DEB”である。

答え:〇

手順にしたがって、元の文字列”DEB”を暗号化してみます。

・手順1:英字を文字番号に変換。

”D”→”3”

”E”→”4”

”B”→”1”

・手順2:n文字目にnを加算。

1文字目に1を加算→3+1=”4”

2文字目に2を加算→4+2=”6”

3文字目に3を加算→1+3=”4”

・手順3:26で割った余りを新たな文字番号に。

4÷26=0・・・余り”4”

6÷26=0・・・余り”6”

4÷26=0・・・余り”4”

・手順4:文字番号を英字に変換。

”4”→”E”

”6”→”G”

”4”→”E”

以上より、暗号化した結果が “EGE” であるとき、元の文字列は”DEB”となります。

問14-2-4

流れ図で示す処理を終了したとき、xの値は28となる。

答え:×

トレース表を作っていきます。「x=y」になるまで条件に応じた処理を繰り返します。

処理xy
初期値9842
①(x>y)56(=98-42)42
②(x>y)14(=56-42)42
③(x≦y)1428(=42-14)
④(x≦y)1414(=28-14)
5(x=y)1414

以上より、処理を終了したときのxの値は14となります。

問14-2-5

表に示す構成のデータを、流れ図の手順で処理する場合について考える。流れ図中のx、y、zをそれぞれデータ区分A、B、Cと適切に対応させれば、比較(「xか?」、「yか?」、「zか?」)の回数の合計は、最低170回で済む。

答え:〇

もし分岐がYesの場合はその処理は終了となり、Noの場合は次の分岐に渡されます。つまり、件数の多いデータ区分を先の分岐で処理したほうが全体の比較回数を少なくすることができます。

したがって、もっとも件数の多いデータ区分Cをx、次に多いデータ区分Bをy、データ区分Aをzとして処理することで、分岐処理の回数を最も少なくすることができます。

分岐処理YesNo比較回数
x(データC)か?50(データC)50(C以外)100
y(データB)か?30(データB)20(BとC以外)50
z(データA)か?10(データA)10(その他)20

以上より、最も少ない比較回数の合計は、100+50+20=170回となります。

問14-2-6

配列に格納されているデータを探索するときの、探索アルゴリズムに関する以下の記述のうち、適切なものは2つある。

  1. 2分探索法は、探索対象となる配列の先頭の要素から順に探索する。
  2. 線形探索法で探索するのに必要な計算量は、探索対象となる配列の要素数に比例する。
  3. 線形探索法を用いるためには、探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。
  4. 探索対象となる配列が同一であれば、探索に必要な計算量は探索する値によらず、2分探索法が線形探索法よりも少ない。

答え:×

1の記述(誤り):探索対象となる配列の先頭の要素から順に探索するのは線形探索法(リニアサーチ)です。

2の記述(正しい):線形探索法は先頭の要素から順に探索する方法のため、探索対象となる配列の要素数が増えれば、比例的に探索するのに必要な計算量も増加します。

3の記述(誤り):要素の値が昇順又は降順にソート(整列)されている必要があるのは二分探索法(バイナリサーチ)です。

4の記述(誤り):探索対象となる配列が同一であれば、平均的な比較回数は2分探索法が線形探索法よりも少なくなります。ただし、配列の先頭のほうに探したいデータがあるような場合は、線形探索法のほうが比較回数が少なくなる場合もあります。

問14-2-7

隣り合う要素の大小を比較して、入れ替えを繰り返しながら整列させるソートアルゴリズムをクイックソートという。

答え:×

設問はバブルソートの説明となります。なおクイックソートとは、適当な値(ピボット)を境界値として選択し、ピボット未満の要素を先頭側に集め、ピボット未満の要素のみを含む区間とそれ以外に分割することを繰り返すことで整列を行うアルゴリズムです。

アルゴリズムとプログラミング2

問14-3-1

次のプログラムにおいて、手続 proc2 を呼び出すと、 “C”,“B”,“A”,“C” の順に出力される。

【プログラム】

〇proc1()

 ”A” を出力する

 proc3()

〇proc2()

 proc3()

 ”B” を出力する

 proc1()

〇proc3()

 ”C” を出力する

答え:〇

手続 proc2 を呼び出すと、まずproc3()が実行され、最初に“C” を出力し、2番目に“B”が出力されます。その次に、proc1()を実行します。

手続 proc1では、まず“A”を出力し、その次にproc3()が実行され、“C” を出力します。

以上より、出力順は”C”,”B”,”A”,”C”となります。

問14-3-2

次のプログラムを実行すると、”3,2″と出力される。

〔プログラム〕

整数型:x ← 1

整数型:y ← 2

整数型:z ← 3

x ← y

y ← z

z ← x

yの値とzの値をこの順にコンマ区切りで出力する

答え:〇

トレース表を作成して変数の値を確認します。

手順xyz
初期値123
①x ← y223
②y ← z233
③z ← x232

以上より、yの値とzの値をこの順にコンマ区切りで出力すると、”3,2″となります。

問14-3-3

ある施設の入場料は、0 歳から 3 歳までは 100 円、4 歳から 9 歳までは 300 円、10 歳以上は 500 円である。関数 fee は、年齢を表す 0 以上の整数を引数として受け取り、入場料を返す。プログラム中の( ? )に入る適切な字句は「age が 9 以下」である。

〔プログラム〕

〇整数型: fee(整数型: age)

 整数型: ret

 if (age が 3 以下)

  ret ← 100

 elseif ( ? )

  ret ← 300

 else

  ret ← 500

 endif

 return ret

答え:〇

if文による条件分岐で、年齢ごとの入場料を返すプログラムですが、プログラムを見ると、関数feeの結果として返される変数retが入場料を表しているということがわかります。

elseif (?)の処理では、ret(入場料)に300を代入していることから、(?)には「4 歳から 9 歳まで」という条件を入れる必要がありますが、ここで注意したいのは、if文は上から優先的に実行されるため、その上の「if~」の条件(つまり3歳以下という条件)は「elseif~」に当てはまる条件に含む必要がないということです。

要するに、3歳以下の場合は「ret←100」という処理が優先されるため、あえて「4歳以上でかつ9歳以下」と書く必要はないという意味です(もちろん書いてもいいですけど)。

したがって、(?)に入る適切な字句は「age が 9 以下」となります。

問14-3-4

関数checkDigitは、10進9桁の整数の各桁の数字が上位の桁から順に格納された整数型の配列originalDigitを引数として、次の手順で計算したチェックデジットを戻り値とする。プログラム中の[ ? ]に入る適切な字句は「j ← k+( j-10×k )」である。ここで、配列の要素番号は1から始まる。

〔手順〕
(1) 配列originalDigitの要素番号1〜9の要素の値を合計する。
(2) 合計した値が9より大きい場合は、合計した値を10進の整数で表現したときの各桁の数字を合計する。この操作を、合計した値が9以下になるまで繰り返す。
(3) (2)で得られた値をチェックデジットとする。

〔プログラム〕
〇整数型:checkDigit(整数型の配列:originalDigit)
 整数型:i, j, k
 j ← 0
 for(iを1からoriginalDigitの要素数まで1ずつ増やす)
  j ← j + originalDigit[i]
 endfor
 while(jが9より大きい)
  k ← j ÷ 10 の商 /*10進9桁の数の場合、jが2桁を超えることはない*/
  [ ? ]
 endwhile
 return j

答え:〇

まず、前半のfor文から説明していきます。「iを1からoriginalDigitの要素数まで1ずつ増やす」とありますが、iは配列originalDigitの添字(要素番号)になっているため、手順(1)の「配列originalDigitの要素番号1〜9の要素の値を合計する」を処理していることが分かります。

次のwhile文では、jが9より大きい場合に繰り返す処理であることから、手順(2)の処理を行っていることが分かります。つまり、「合計した値を10進の整数で表現したときの各桁の数字(10の位の数字と1の位の数字)を合計する」という処理を

k ← j ÷ 10 の商
[ ? ]

の2行で行っているということになります。

「k ← j ÷ 10 の商」は、10の位の数字をkに代入する処理となります。

例えば、9桁の数字の各桁の合計(j)が”58″という数字であった場合、「58÷10=5 余り8」なので商”5″は10の位の数字を表すことになります。

あとはこれに1の位の数字を足したいわけですが、どのように処理すればいいでしょうか?

9桁の数字の各桁の合計(j)が”58″の場合であれば、58(j)から50を引いてやれば1の位の数字”8″を表すことができます。

先ほど計算した10の位の数字k(= j ÷ 10 の商)を10倍したもの(k×10)が例で言うところの”50″に当たるので、これをjから引いてやれば1の位の数字を表すことができます。

最後に、変数jの10の位の数字と1の位の数字の合計をjに代入します(jが1桁になるまでこれを繰り返します)。

変数jの10の位の数字= j ÷ 10 の商=k

変数jの1の位の数字=j-k×10

変数jの10の位の数字と1の位の数字の合計= k+( j-10×k )

まとめると、[ ? ]に入るのは「j ← k+( j-10×k )」となります。

問14-3-5

関数calcXと関数calcYは、引数inDataを用いて計算を行い、その結果を戻り値とする。関数calcXをcalcX(1)として呼び出すと、関数calcXの変数numの値が、1 → 3 → 7 → 13 と変化し、戻り値は13となった。関数calcYをcalcY(1)として呼び出すと、関数calcYの変数numの値が、1 → 5 → 13 → 25 と変化し、戻り値は25となった。

プログラム中のa, bに入れる字句の適切な組合せは次のようになる。

ab
num + 2 × iiを2から6まで2ずつ増やす

答え:〇

[プログラム1]

関数calcXをcalcX(1)として呼び出し、変数 i が1→2→3と増えたとき、変数 num の値がどう変わるかをトレースしていきます。なお、初期値では「num ← inData」から、numに1が格納されます。

空欄aが「num+2×i」とすると、変数 num の値は次のように変わります。

i=1のとき:num=1+2×1=3

i=2のとき:num=3+2×2=7

i=3のとき:num=7+2×3=13

以上より、変数numの値が1 → 3 → 7 → 13 と変化するため、正しいことが分かります。

[プログラム2]

関数calcYをcalcY(1)として呼び出し、iを2から6まで2ずつ増やしたとき、変数 num の値がどう変わるかをトレースしていきます。なお、初期値では「num ← inData」から、numに1が格納されます。空欄aは「num+2×i」です。

i=2のとき:num=1+2×2=5

i=4のとき:num=5+2×4=13

i=6のとき:num=13+2×6=25

以上より、変数numの値が1 → 5 → 13 → 25 と変化するため、正しいことが分かります。

問14-3-6


関数 makeNewArray は、要素数2以上の整数型の配列を引数にとり、整数型の配列を返す関数である。関数 makeNewArray を makeNewArray({3,2,1,6,5,4})として呼び出したとき、戻り値の配列は{3,5,6,12,17,21}となる。ここで、配列の要素番号は1から始まる。

〔プログラム〕

◯整数型の配列:makeNewArray(整数型の配列: in)

 整数型の配列:out ← { } // 要素数0の配列

 整数型: i, tail

 outの末尾にin[1]の値を追加する

 for (iを2からinの要素数まで1ずつ増やす)

  tail ← out[outの要素数]

  outの末尾に(tail + in[i])の結果を追加する

 endfor

 return out

答え:〇

プログラムを順番に見ていきましょう。

①outの末尾にin[1]の値を追加する

配列inは{3,2,1,6,5,4}なので、in[1](1番目の要素)の値は”3″です。これを配列outの末尾に追加します。

最初outは要素数0の配列(空っぽの配列)なので、この時点でout={3になります。

②for (iを2からinの要素数まで1ずつ増やす)

inの要素数は6つあるので、iを2から6まで1ずつ増やしていきながら処理を繰り返します。

・i=2のとき

処理:tail ← out[outの要素数]

この時点でのoutの要素数は1つだけなので、out[1]=3となり、これをtailに代入します(tail=3)。

処理:outの末尾に(tail + in[i])の結果を追加する

tail=3、in[i]=in[2](配列inの2番目の要素)=2なので、

outの末尾に”5″(=3+2)を追加します。

この時点で、out={3,5になります。

・i=3のとき

処理:tail ← out[outの要素数]

この時点でのoutの要素数は2つなので、out[2]=5となり、これをtailに代入します(tail=5)。

処理:outの末尾に(tail + in[i])の結果を追加する

tail=5、in[i]=in[3](配列inの3番目の要素)=1なので、

outの末尾に”6″(=5+1)を追加します。

この時点で、out={3,5,6になります。

・i=4のとき

処理:tail ← out[outの要素数]

この時点でのoutの要素数は3つなので、out[3]=6となり、これをtailに代入します(tail=6)。

ここまで来ると皆さんお気づきの通り、tailは配列outの末尾の要素の値を格納するための変数です。

処理:outの末尾に(tail + in[i])の結果を追加する

tail=6、in[i]=in[4](配列inの4番目の要素)=6なので、

outの末尾に”12″(=6+6)を追加します。

この時点で、out={3,5,6,12になります。

・i=5のとき

処理:tail ← out[outの要素数]

この時点でのoutの要素数は4つなので、out[4]=12となり、これをtailに代入します(tail=12)。

処理:outの末尾に(tail + in[i])の結果を追加する

tail=12、in[i]=in[5](配列inの5番目の要素)=5なので、

outの末尾に”17″(=12+5)を追加します。

この時点で、out={3,5,6,12,17になります。

・i=6のとき

処理:tail ← out[outの要素数]

この時点でのoutの要素数は5つなので、out[5]=17となり、これをtailに代入します(tail=17)。

処理:outの末尾に(tail + in[i])の結果を追加する

tail=17、in[i]=in[6](配列inの6番目の要素)=4なので、

outの末尾に”21″(=17+4)を追加します。

この時点で、out={3,5,6,12,17,21になります。

以上より、戻り値の配列は{3,5,6,12,17,21}となります。

プログラム言語

問14-4-1

プログラム言語の役割は、コンピューターに対して処理手続を記述することである。

答え:〇

コンピュータでアルゴリズムを実行できるようにするには、プログラム言語を用いてアルゴリズム(処理手順)を記述する必要があります。

問14-4-2

コンピュータに対する命令を、プログラム言語を用いて記述したものを機械語と呼ぶ。

答え:×

設問はソースコードの説明となります。なお、機械語(マシン語、バイナリコード)とは、コンピュータが解析できるように2進数に変換されたプログラムのことです。

問14-4-3

Java言語で作成したプログラムであり、Webサーバからダウンロードして、Webブラウザ上で実行するものはJavaアプリケーションである。

答え:×

設問はJavaアプレットの説明となります。

Javaで作成したプログラムは実行形態によって、Javaアプリケーション(OS上から起動されるプログラム)、Javaアプレット(Webブラウザ上で実行されるプログラム)、Javaサーブレット(Webサーバ上で実行されるプログラム)に区別されます。

問14-4-4

JavaScriptは、Webブラウザ上に動的な振る舞いなどを組み込むことができる。

答え:〇

JavaScriptは、主に動きのあるWebページを開発する際に使われるプログラミング言語です。

問14-4-5

Pythonは、科学技術計算向けに開発されたプログラム言語である。

答え:×

科学技術計算向けに開発されたプログラム言語はFortran(フォートラン)です。

Python(パイソン)は、オープンソースのプログラミング言語で、多くのプラットフォームで動作し、読みやすく書きやすいという特徴があります。また、利便性の高い大規模な標準ライブラリを備えており、データ分析やAI(人工知能)の分野で注目されています。

その他の言語

問14-5-1

HTMLとは、タグを使ってWebページの論理構造やレイアウトが指定できるマークアップ言語である。

答え:〇

HTMLは、主にWebページを表現するためのマークアップ言語で、Webブラウザなどでの表現に利用されます。

問14-5-2

文書の構造などに関する指定を記述する、”<”と”>”に囲まれるタグを、利用者が目的に応じて定義して使うことができる言語をHTMLという。

答え:×

設問はXMLの説明となります。あらかじめ決められたタグしか使用できないHTMLに対して、XMLは独自にタグを定義することができるマークアップ言語です。

問14-5-3

JSONは、インターネット上で公開されるWebページを作成するときに使用される言語である。

答え:×

インターネット上で公開されるWebページを作成するときに使用される言語はHTMLです。JSONは、異なるプログラム言語で書かれたプログラム間でのデータのやり取りなどに用いられるデータの記述形式です。