応用情報技術者試験 - Applied Information Technology Engineer Fundamental Theory and Algorithms Questions and Answers

Question 1

データ構造の一つであるキューに関する記述として、最も適切なものはどれか。

Accepted Answer

最初に追加したデータを最初に取り出す先入れ先出し（FIFO）の方式である。

Answer

キュー（Queue）は、データを待ち行列のように管理するデータ構造です。スーパーのレジ待ちのように、最初に列に並んだ人（データ）が最初にサービスを受ける（取り出される）方式で、これを先入れ先出し（FIFO: First-In, First-Out）と呼びます。したがって、選択肢イが正解です。選択肢アはスタック（Stack）、ウは配列（Array）、エはハッシュテーブルや連想配列（Associative Array）の説明です。

Question 2

n個のデータがソートされていない配列に格納されている。この配列から特定の値を探索する線形探索（リニアサーチ）の計算量（オーダ）として、最も適切なものはどれか。ここで、計算量は最悪の場合を考えるものとする。

Accepted Answer

O(n)

Answer

線形探索は、配列の先頭から末尾まで順番に要素を比較していく探索アルゴリズムです。最悪の場合、探索したい値が配列の末尾にあるか、または配列内に存在しない場合、n個すべての要素を比較する必要があります。したがって、計算時間はデータ数nに比例するため、計算量はO(n)となります。選択肢イのO(log n)は二分探索など、ウのO(n^2)は単純なソートアルゴリズムなどで見られます。アのO(1)はハッシュテーブルでの探索など、データ量によらず一定時間で処理が完了する場合の計算量です。

Question 3

次の擬似言語で記述されたプログラムを実行したとき、変数Xの値は最終的にいくつか。ここで、配列Aの要素は A[1]=5, A[2]=8, A[3]=3, A[4]=9, A[5]=4 である。

○整数型: X, i
○整数型の配列: A[1..5]

X ← A[1]
整数 i を 2 から 5 まで 1 ずつ増やしながら、以下を繰り返す：
  もし A[i] > X ならば
    X ← A[i]
  終わり
繰り返し終わり

Accepted Answer

9

Answer

このプログラムは、配列Aの中から最大値を探して変数Xに格納するアルゴリズムです。
1. Xは最初にA[1]の値である5で初期化されます。
2. i=2のとき、A[2] (8) > X (5) なので、Xは8になります。
3. i=3のとき、A[3] (3) > X (8) ではないので、Xは8のままです。
4. i=4のとき、A[4] (9) > X (8) なので、Xは9になります。
5. i=5のとき、A[5] (4) > X (9) ではないので、Xは9のままです。
ループが終了した時点で、Xの値は9となります。

Question 4

再帰呼び出し（Recursive Call）を伴うアルゴリズムの例として、最も適切なものはどれか。

Accepted Answer

ある問題の解を、同じ構造を持つより小さな問題の解を利用して求める。

Answer

再帰呼び出しとは、関数や手続きが自分自身を呼び出すことです。ある問題を解決するために、その問題と同じ構造を持つが規模がより小さい部分問題に分割し、その部分問題を同じアルゴリズムで解くという手法で用いられます。代表的な例として、階乗の計算、フィボナッチ数列、クイックソート、木構造の探索などがあります。したがって、選択肢ウが再帰の基本的な考え方を説明しており、正解です。ア、イ、エは再帰を必ずしも必要としないアルゴリズムです。

Question 5

様々なソートアルゴリズムのうち、対象とするデータ集合の中から基準となる要素（ピボット）を一つ選び、それより小さい要素のグループと大きい要素のグループにデータを分割する、という処理を繰り返すことで整列を行うアルゴリズムはどれか。

Accepted Answer

クイックソート

Answer

設問で説明されているアルゴリズムはクイックソートです。クイックソートは、基準値（ピボット）を選び、データ全体をピボットより小さいグループと大きいグループに分割します。そして、分割された各グループに対して再帰的に同じ処理を繰り返すことで、効率的にソートを行います。一般的に高速なソートアルゴリズムとして知られています。バブルソートは隣接要素の比較交換、マージソートは分割と併合、ヒープソートはヒープ構造を利用する手法です。

応用情報技術者練習テスト

応用情報技術者練習テスト

応用情報技術者試験 - Applied Information Technology Engineer Fundamental Theory and Algorithms Questions and Answers

応用情報技術者 練習テスト

応用情報技術者試験 - Applied Information Technology Engineer Fundamental Theory and Algorithms Questions and Answers

応用情報技術者練習テスト