応用情報技術者試験 - Applied Information Technology Engineer Fundamental Theory and Algorithms Questions and Answers — Questions and Answers
Question 1: データ構造の一つであるキューに関する記述として、最も適切なものはどれか。
- 最後に追加したデータを最初に取り出す後入れ先出し（LIFO）の方式である。
- 最初に追加したデータを最初に取り出す先入れ先出し（FIFO）の方式である。 (Correct answer)
- 任意の位置のデータに直接アクセスできるが、データの挿入や削除には時間がかかる。
- データをキーと値のペアで格納し、キーを用いて高速にデータを検索できる。
Correct answer: 最初に追加したデータを最初に取り出す先入れ先出し（FIFO）の方式である。
キュー（Queue）は、データを待ち行列のように管理するデータ構造です。スーパーのレジ待ちのように、最初に列に並んだ人（データ）が最初にサービスを受ける（取り出される）方式で、これを先入れ先出し（FIFO: First-In, First-Out）と呼びます。したがって、選択肢イが正解です。選択肢アはスタック（Stack）、ウは配列（Array）、エはハッシュテーブルや連想配列（Associative Array）の説明です。
Question 2: n個のデータがソートされていない配列に格納されている。この配列から特定の値を探索する線形探索（リニアサーチ）の計算量（オーダ）として、最も適切なものはどれか。ここで、計算量は最悪の場合を考えるものとする。
- O(1)
- O(log n)
- O(n) (Correct answer)
- O(n^2)
Correct answer: O(n)
線形探索は、配列の先頭から末尾まで順番に要素を比較していく探索アルゴリズムです。最悪の場合、探索したい値が配列の末尾にあるか、または配列内に存在しない場合、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] 終わり 繰り返し終わり
- 3
- 5
- 8
- 9 (Correct answer)
Correct answer: 9
このプログラムは、配列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）を伴うアルゴリズムの例として、最も適切なものはどれか。
- キューを用いて、幅優先探索（Breadth-First Search）を実装する。
- ハッシュ関数を用いて、データ格納位置を決定する。
- ある問題の解を、同じ構造を持つより小さな問題の解を利用して求める。 (Correct answer)
- 配列の先頭から順に値を比較し、最小値を探し出す。
Correct answer: ある問題の解を、同じ構造を持つより小さな問題の解を利用して求める。
再帰呼び出しとは、関数や手続きが自分自身を呼び出すことです。ある問題を解決するために、その問題と同じ構造を持つが規模がより小さい部分問題に分割し、その部分問題を同じアルゴリズムで解くという手法で用いられます。代表的な例として、階乗の計算、フィボナッチ数列、クイックソート、木構造の探索などがあります。したがって、選択肢ウが再帰の基本的な考え方を説明しており、正解です。ア、イ、エは再帰を必ずしも必要としないアルゴリズムです。
Question 5: 様々なソートアルゴリズムのうち、対象とするデータ集合の中から基準となる要素（ピボット）を一つ選び、それより小さい要素のグループと大きい要素のグループにデータを分割する、という処理を繰り返すことで整列を行うアルゴリズムはどれか。
- バブルソート
- クイックソート (Correct answer)
- マージソート
- ヒープソート
Correct answer: クイックソート
設問で説明されているアルゴリズムはクイックソートです。クイックソートは、基準値（ピボット）を選び、データ全体をピボットより小さいグループと大きいグループに分割します。そして、分割された各グループに対して再帰的に同じ処理を繰り返すことで、効率的にソートを行います。一般的に高速なソートアルゴリズムとして知られています。バブルソートは隣接要素の比較交換、マージソートは分割と併合、ヒープソートはヒープ構造を利用する手法です。
Question 6: オートマトンに関する記述として、最も適切なものはどれか。
- 与えられた有限個の命令からなる手続きで、問題を解決するための計算手順を定義したものである。
- ある状態と入力によって、次に遷移する状態が一意に定まるシステムモデルである。 (Correct answer)
- データ圧縮方式の一つで、出現頻度の高いデータには短い符号を、低いデータには長い符号を割り当てる。
- 公開鍵と秘密鍵という対になる鍵を使用して、データの暗号化と復号を行う方式である。
Correct answer: ある状態と入力によって、次に遷移する状態が一意に定まるシステムモデルである。
オートマトンは、システムの状態がどのように変化するかをモデル化したものです。特に「有限オートマトン」は、有限個の状態を持ち、入力記号に応じて状態が遷移します。ある状態のときに特定の入力を受け取ると、次にどの状態に遷移するかが一意に決まるものを「決定的有限オートマトン（DFA）」と呼びます。選択肢イはこのオートマトンの概念を説明しています。選択肢アはアルゴリズム、ウはハフマン符号、エは公開鍵暗号方式の説明です。
応用情報技術者試験 - Applied Information Technology Engineer Fundamental Theory and Algorithms Questions and Answers
データ構造の一つであるキューに関する記述として、最も適切なものはどれか。