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

Question 1

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

Accepted Answer

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

Answer

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

Answer

任意の位置のデータに直接アクセスできるが、データの挿入や削除には時間がかかる。

Answer

データをキーと値のペアで格納し、キーを用いて高速にデータを検索できる。

Question 2

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

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

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

3

Answer

5

Answer

8

Question 4

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

Accepted Answer

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

Answer

キューを用いて、幅優先探索（Breadth-First Search）を実装する。

Answer

ハッシュ関数を用いて、データ格納位置を決定する。

Answer

配列の先頭から順に値を比較し、最小値を探し出す。

Question 5

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

Accepted Answer

クイックソート

Answer

バブルソート

Answer

マージソート

Answer

ヒープソート

Question 6

オートマトンに関する記述として、最も適切なものはどれか。

Accepted Answer

ある状態と入力によって、次に遷移する状態が一意に定まるシステムモデルである。

Answer

与えられた有限個の命令からなる手続きで、問題を解決するための計算手順を定義したものである。

Answer

データ圧縮方式の一つで、出現頻度の高いデータには短い符号を、低いデータには長い符号を割り当てる。

Answer

公開鍵と秘密鍵という対になる鍵を使用して、データの暗号化と復号を行う方式である。