資格部

資格・検定の試験情報、対策方法、問題解説などをご紹介

AP 午前 アルゴリズムとプログラミング

応用情報技術者

データ構造｜アルゴリズム｜プログラミング｜プログラム言語｜その他の言語

データ構造

　リストには，配列で実現する場合とポインタで実現する場合とがある。リストを配列で実現した場合の特徴として，適切なものはどれか。ここで，配列を用いたリストは配列に要素を連続して格納することによってリストを構成し，ポインタを用いたリストは要素と次の要素へのポインタを用いることによってリストを構成するものとする。

  1. リストにある実際の要素数にかかわらず，リストに入れられる要素の最大個数に対応した領域を確保し，実際には使用されない領域が発生する可能性がある。
  2. リストの中間要素を参照するには，リストの先頭から順番に要素をたどっていくことから，要素数に比例した時間が必要となる。
  3. リストの要素を格納する領域の他に，次の要素を指し示すための領域が別途必要となる。
  4. リストへの挿入位置が分かる場合には，リストにある実際の要素数にかかわらず，要素の挿入を一定時間で行うことができる。

解答・解説

 

　A，B，Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合，データの出力順序は何通りあるか。

f:id:trhnmr:20210422192708j:plain

  1. 3
  2. 4
  3. 5
  4. 6

解答・解説

 

　配列A[1]，A[2]，…，A[n]で，A[1]を根とし，A[i]の左側の子をA[2i]，右側の子をA[2i+1]とみなすことによって，2分木を表現する。このとき，配列を先頭から順に調べていくことは，2分木の探索のどれに当たるか。

  1. 行きがけ順（先行順）深さ優先探索
  2. 帰りがけ順（後行順）深さ優先探索
  3. 通りがけ順（中間順）深さ優先探索
  4. 幅優先探索

解答・解説

 

　ポインタを用いた線形リストの特徴のうち，適切なものはどれか。

  1. 先頭の要素を根としたn分木で，先頭以外の要素は全て先頭の要素の子である。
  2. 配列を用いた場合と比較して，2分探索を効率的に行うことが可能である。
  3. ポインタから次の要素を求めるためにハッシュ関数を用いる。
  4. ポインタによって指定されている要素の後ろに，新たな要素を追加する計算量は，要素の個数や位置によらず一定である。

解答・解説

 

　先頭ポインタと末尾ポインタをもち，多くのデータがポインタでつながった単方向の線形リストの処理のうち，先頭ポインタ，末尾ポインタ又は各データのポインタをたどる回数が最も多いものはどれか。ここで，単方向のリストは先頭ポインタからつながっているものとし，追加するデータはポインタをたどらなくても参照できるものとする。

  1. 先頭にデータを追加する処理
  2. 先頭のデータを削除する処理
  3. 末尾にデータを追加する処理
  4. 末尾のデータを削除する処理

解答・解説

 

　要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合（best-fit）アルゴリズムを用いる場合，空き領域を管理するためのデータ構造として，メモリ割当て時の平均処理時間が最も短いものはどれか。

  1. 空き領域のアドレスをキーとする2分探索木
  2. 空き領域の大きさが小さい順の片方向連結リスト
  3. 空き領域の大きさをキーとする2分探索木
  4. アドレスに対応したビットマップ

解答・解説

 

　葉以外の節点はすべて二つの子をもち，根から葉までの深さがすべて等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，木の深さとは根から葉に至るまでの枝の個数を表す。また，節点には根及び葉も含まれる。

  1. 枝の個数がnならば，葉を含む節点の個数もnである。
  2. 木の深さがnならば，葉の個数は2n−1である。
  3. 節点の個数がnならば，深さはlog2nである。
  4. 葉の個数がnならば，葉以外の節点の個数はn−1である。

解答・解説

 

　2次元配列 A[i, j] （i，j はいずれも0～99の値をとる）の i>j である要素 A[i, j] は全部で幾つか。

  1. 4,851
  2. 4,950
  3. 4,999
  4. 5,050

解答・解説

 

　再帰的な処理を実現するためには，再帰的に呼び出したときのレジスタ及びメモリの内容を保存しておく必要がある。そのための記憶管理方式はどれか。

  1. FIFO
  2. LFU
  3. LIFO
  4. LRU

解答・解説

 

　ノード1～5をもつグラフを隣接行列で表したもののうち，木となるものはどれか。ここで，隣接行列のi行j列目の成分は，ノードiとノードjを結ぶエッジがある場合は1，ない場合は0とする。

  1. \begin{bmatrix} 0　1　0　0　1　　　 \\ 1　0　1　0　0　　　 \\ 0　1　0　1　0　　　 \\ 0　0　1　0　1　　　 \\ 1　0　0　1　0　　　 \end{bmatrix}
  2. \begin{bmatrix} 0　1　0　0　1　　　 \\ 1　0　1　1　0　　　 \\ 0　1　0　0　0　　　 \\ 0　1　0　0　0　　　 \\ 1　0　0　0　0　　　 \end{bmatrix}
  3. \begin{bmatrix} 0　1　0　1　0　　　 \\ 1　0　1　0　0　　　 \\ 0　1　0　1　1　　　 \\ 1　0　1　0　0　　　 \\ 0　0　1　0　0　　　 \end{bmatrix}
  4. \begin{bmatrix} 0　1　1　0　0　　　 \\ 1　0　1　0　0　　　 \\ 1　1　0　1　1　　　 \\ 0　0　1　0　1　　　 \\ 0　0　1　1　0　　　 \end{bmatrix}

解答・解説

 

アルゴリズム

　自然数をキーとするデータを，ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を
　　h(x) = x mod n
とすると，任意のキーaとbが衝突する条件はどれか。ここで，nはハッシュ表の大きさであり，x mod nはxをnで割った余りを表す。

  1. a+bがnの倍数
  2. a−bがnの倍数
  3. nがa+bの倍数
  4. nがa−bの倍数

解答・解説

 

　未整列の配列A[i] (i=1, 2, …, n) を，次の流れ図によって整列する。ここで用いられる整列アルゴリズムはどれか。

  1. クイックソート
  2. 選択ソート
  3. 挿入ソート
  4. バブルソート

解答・解説

 

　バブルソートの説明として，適切なものはどれか。

  1. ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し，更に間隔を詰めて同様の操作を行い，間隔が1になるまでこれを繰り返す。
  2. 中間的な基準値を決めて，それよりも大きな値を集めた区分と，小さな値を集めた区分に要素を振り分ける。次に，それぞれの区分の中で同様の操作を繰り返す。
  3. 隣り合う要素を比較して，大小の順が逆であれば，それらの要素を入れ替えるという操作を繰り返す。
  4. 未整列の部分を順序木にし，そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して，未整列の部分を縮めていく。

解答・解説

 

　アルゴリズム設計としての分割統治法に関する記述として，適切なものはどれか。

  1. 与えられた問題を直接解くことが難しいときに，幾つかに分割した一部分に注目し，とりあえず粗い解を出し，それを逐次改良して精度の良い解を得る方法である。
  2. 起こり得る全てのデータを組み合わせ，それぞれの解を調べることによって，データの組合せのうち無駄なものを除き，実際に調べる組合せ数を減らす方法である。
  3. 全体を幾つかの小さな問題に分割して，それぞれの小さな問題を独立に処理した結果をつなぎ合わせて，最終的に元の問題を解決する方法である。
  4. まずは問題全体のことは考えずに，問題をある尺度に沿って分解し，各時点で最良の解を選択し，これを繰り返すことによって，全体の最適解を得る方法である。

解答・解説

 

　円周率πの値を近似的に求める方法のうち，モンテカルロ法を応用したものはどれか。

  1. 正方形の中に一様乱数を用いて多数の点をとったとき，その点の個数と正方形に内接する円の中にある点の個数の比が，点の個数を多くすると両者の面積比である4 : πに近づくことを用いて求める。
  2. 正方形の中に等間隔に多数の格子点をとったとき，その格子点の個数と正方形に内接する円の中にある格子点の個数の比が，格子点の間隔を細かくすると両者の面積比である4 : πに近づくことを用いて求める。
  3. 直径1の円に内接する正n角形の周の長さと円の直径の比が，nを大きくするとπ : 1に近づくことを用いて求める。
  4. 直径1の円に内接する正n角形の面積と円に内接する正方形の面積の比が，nを大きくするとπ : 2に近づくことを用いて求める。

解答・解説

 

　分割統治を利用した整列法はどれか。

  1. 基数ソート
  2. クイックソート
  3. 選択ソート
  4. 挿入ソート

解答・解説

 

　次の手順はシェルソートによる整列を示している。データ列 7，2，8，3，1，9，4，5，6 を手順（1）～（4）に従って整列するとき，手順（3）を何回繰り返して完了するか。ここで，[ ]は小数点以下を切り捨てた結果を表す。

  1. 2
  2. 3
  3. 4
  4. 5

解答・解説

 

　探索表の構成法を例とともに a～c に示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す。

f:id:trhnmr:20210412111104p:plain

  a b c
ア 2分探索 線形探索 ハッシュ表探索
イ 2分探索 ハッシュ表探索 線形探索
ウ 線形探索 2分探索 ハッシュ表探索
エ 線形探索 ハッシュ表探索 2分探索

解答・解説

 

　非負の整数m，nに対して次のとおりに定義された関数 Ack(m, n) がある。Ack(1, 3) の値はどれか。

　　 \begin{eqnarray} Ack(m, n) = \begin{cases} Ack(m-1, Ack(m, n-1))　（m\gt0 かつ n\gt0 のとき） \\ Ack(m-1, 1)　（m\gt0 かつ n=0 のとき） \\ n+1　（m=0のとき） \end{cases} \end{eqnarray}

  1. 3
  2. 4
  3. 5
  4. 6

解答・解説

 

　異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，mは十分大きく，nはmの倍数とし，目的のデータは必ず表の中に存在するものとする。

  1. m + n/m
  2. m/2 + n/2m
  3. n/m
  4. n/2m

解答・解説

 

　fact(n) は，非負の整数nに対してnの階乗を返す。fact(n) の再帰的な定義はどれか。

  1. if n=0 then 0 else return n×fact(n−1)
  2. if n=0 then 0 else return n×fact(n+1)
  3. if n=0 then 1 else return n×fact(n−1)
  4. if n=0 then 1 else return n×fact(n+1)

解答・解説

 

　次の流れ図の処理で，終了時のxに格納されているものはどれか。ここで，与えられたa，bは正の整数であり，mod(x, y)はxをyで割った余りを返す。

f:id:trhnmr:20210412112616p:plain

  1. aとbの最小公倍数
  2. aとbの最大公約数
  3. aとbの小さい方に最も近い素数
  4. aをbで割った商

解答・解説

 

プログラミング

　再入可能プログラムの特徴はどれか。

  1. 主記憶上のどのアドレスから配置しても，実行することができる。
  2. 手続の内部から自分自身を呼び出すことができる。
  3. 必要な部分を補助記憶装置から読み込みながら動作する。主記憶領域の大きさに制限があるときに，有効な手法である。
  4. 複数のタスクからの呼出しに対して，並行して実行されても，それぞれのタスクに正しい結果を返す。

解答・解説

 

　プログラム特性に関する記述のうち，適切なものはどれか。

  1. 再帰的プログラムは再入可能な特性をもち，呼び出されたプログラムの全てがデータを共用する。
  2. 再使用可能プログラムは実行の始めに変数を初期化する，又は変数を初期状態に戻した後にプログラムを終了する。
  3. 再入可能プログラムは，データとコードの領域を明確に分離して，両方を各タスクで共用する。
  4. 再配置可能なプログラムは，実行の都度，主記憶装置上の定まった領域で実行される。

解答・解説

 

　JavaScriptの言語仕様のうち，オブジェクトの表記法などの一部の仕様を基にして規定したものであって，“名前と値の組みの集まり”と“値の順序付きリスト”の二つの構造に基づいてオブジェクトを表現する，データ記述の仕様はどれか。

  1. DOM
  2. JSON
  3. SOAP
  4. XML

解答・解説

 

　プログラムの特性に関する記述のうち，適切なものはどれか。

  1. 再帰的プログラムは，手続の中でそれ自体を呼び出すプログラムであり，再入可能である。
  2. 再使用可能プログラムは，一度実行したプログラムを主記憶装置上にロードし直さずに再度実行できるプログラムであり，再入可能である。
  3. 再入可能プログラムは，複数のタスクから同時に呼び出されたときに，並列に実行できるプログラムであるが，再配置可能ではない。
  4. 再配置可能プログラムは，主記憶装置上のどの領域にロードされても実行可能なプログラムであるが，再使用可能ではない。

解答・解説

 

プログラム言語

　プログラム言語のうち，ブロックの範囲を指定する方法として特定の記号や予約語を用いず，等しい文字数の字下げを用いるという特徴をもつものはどれか。

  1. C
  2. Java
  3. PHP
  4. Python

解答・解説

 

　静的型付けを行うプログラム言語では，コンパイル時に変数名の誤り，誤った値の代入などが発見できる。Webプログラミングで用いられるスクリプト言語のうち，変数の静的型付けができるものはどれか。

  1. ECMAScript
  2. JavaScript
  3. TypeScript
  4. VBScript

解答・解説

 

　次の特徴をもつプログラム言語及び実行環境であって，オープンソースソフトウェアとして提供されているものはどれか。
〔特徴〕
・統計解析や機械学習の分野に適している。
・データ分析，グラフ描画などの，多数のソフトウェアパッケージが提供されている。
・変数自体には型がなく，変数に代入されるオブジェクトの型は実行時に決まる。

  1. Go
  2. Kotlin
  3. R
  4. Scala

解答・解説

 

　オブジェクト指向のプログラム言語であり，クラスや関数，条件文などのコードブロックの範囲はインデントの深さによって指定する仕様であるものはどれか。

  1. JavaScript
  2. Perl
  3. Python
  4. Ruby

解答・解説

 

　オブジェクト指向プログラミングにおいて，同一クラス内に，メソッド名が同一であって，引数の型，個数又は並び順が異なる複数のメソッドを定義することを何と呼ぶか。

  1. オーバーライド
  2. オーバーロード
  3. カプセル化
  4. 汎化

解答・解説

 

その他の言語

　XMLにおいて，XML宣言中で符号化宣言を省略できる文字コードはどれか。

  1. EUC-JP
  2. ISO-2022-JP
  3. Shift-JIS
  4. UTF-16

解答・解説