基本情報技術者 基礎理論 択一式（応用） 第26問〜第30問｜アルゴリズムとプログラミング

正解：C

・A
小さい要素と大きい要素のグループが左右逆になっている。

・B
基準値5が小さい要素のグループへ含まれており、指定された三つの区分になっていない。

・C
正解。5より小さい要素は元の順に3、2、基準値は5、5より大きい要素は元の順に8、7である。

・D
値の大小順に各グループ内部まで整列しているが、この問題で求めているのは基準値による分割であり、グループ内の整列ではない。

正解：C

・A
3はデータ件数の比そのものであり、処理時間が件数に比例する場合の値である。

・B
6は件数の比3を2倍しただけの値であり、2乗に比例する関係が反映されていない。

・C
正解。件数が3倍になると、処理時間は3の2乗＝9倍になるため、1秒×9＝9秒となる。

・D
27は3の3乗であり、件数の3乗に比例する場合の値である。

正解：C

・A
4は再帰の展開を行わずに、引数nの値をそのまま返してしまった場合の値である。

・B
10は掛け算ではなく、4＋3＋2＋1と加算してしまった場合の値である。

・C
正解。F(4)＝4×F(3)＝4×3×F(2)＝4×3×2×F(1)＝4×3×2×1＝24となる。これは階乗を再帰で計算する定義である。

・D
256は4の4乗であり、再帰の展開を誤った値である。

正解：B

・A
添字を使って任意位置へ直接アクセスできるのは配列の特徴である。連結リストでは、通常は先頭などからリンクを順にたどって対象位置を探す。

・B
正解。連結リストでは、挿入・削除に必要な節への参照が得られていれば、配列のように後続要素を移動せず、リンクを付け替えて操作できる。単方向リストで節を削除する場合には、一般に直前の節など、更新すべきリンクをもつ節への参照が必要になる。対象位置の探索や節の確保・解放には別の処理が必要である。

・C
全要素を連続したメモリ領域へ格納するのは配列の特徴である。連結リストの節は離れた領域に配置される場合があり、キャッシュ効率が常に最も高いとはいえない。

・D
要素数が宣言時に固定されるのは静的配列の特徴である。連結リストは、利用可能なメモリなどの制約の範囲で、実行中に節を追加・削除できる。

正解：D

・A
ハッシュ法はキーから格納位置を直接計算する方法であり、整列は不要である。

・B
適切なハッシュ関数と負荷率の下では、平均的な探索時間はデータ件数にほぼ依存しない。一方、衝突が集中する最悪の場合には、探索時間がデータ件数に比例することがある。

・C
ハッシュ法は表（配列）を基本とした格納方法であり、木構造が必須なわけではない。

・D
正解。異なるキーから同じ格納位置が計算されることを衝突という。衝突が発生する可能性があるため、オープンアドレス法やチェイン法などによって対処する必要がある。