応用情報 アルゴリズムとプログラミング 1 — Questions and Answers
Question 1: バブルソートの平均時間計算量はどれか？
- O(n)
- O(n log n)
- O(n²) (Correct answer)
- O(log n)
Correct answer: O(n²)
バブルソートは隣接要素を比較・交換する操作をn回繰り返すため、平均時間計算量はO(n²)となる。
Question 2: スタックのデータ構造の特性として正しいものはどれか？
- FIFO（先入れ先出し）
- LIFO（後入れ先出し） (Correct answer)
- ランダムアクセス可能
- 優先順位付きアクセス
Correct answer: LIFO（後入れ先出し）
スタックはLIFO（Last In First Out：後入れ先出し）構造であり、最後に追加されたデータが最初に取り出される。
Question 3: 二分探索を適用するための前提条件はどれか？
- データがランダムに並んでいること
- データが昇順または降順に整列されていること (Correct answer)
- データに重複がないこと
- データ数が2の累乗であること
Correct answer: データが昇順または降順に整列されていること
二分探索はデータが整列されていることを前提とし、中央値との比較により探索範囲を半分ずつ絞り込む。
Question 4: 再帰アルゴリズムの実装において必須の要素はどれか？
- グローバル変数
- 基底条件（ベースケース） (Correct answer)
- ループ変数
- 配列の宣言
Correct answer: 基底条件（ベースケース）
再帰アルゴリズムには無限再帰を防ぐための基底条件（ベースケース）が必須であり、これがないとスタックオーバーフローが発生する。
Question 5: クイックソートの最悪時間計算量はどれか？
- O(n log n)
- O(n²) (Correct answer)
- O(n)
- O(log n)
Correct answer: O(n²)
クイックソートはピボットが常に最大値または最小値となる場合に分割が偏り、最悪時間計算量はO(n²)となる。
Question 6: ハッシュ法による探索の平均時間計算量はどれか？
- O(n)
- O(log n)
- O(1) (Correct answer)
- O(n²)
Correct answer: O(1)
ハッシュ法はハッシュ関数によりデータの格納位置を直接計算するため、衝突がなければ平均O(1)で探索できる。
Question 7: キューのデータ構造の特性として正しいものはどれか？
- LIFO（後入れ先出し）
- FIFO（先入れ先出し） (Correct answer)
- 優先順位付きアクセス
- ランダムアクセス可能
Correct answer: FIFO（先入れ先出し）
キューはFIFO（First In First Out：先入れ先出し）構造であり、最初に追加されたデータが最初に取り出される。
