重要度：A 論点：アルゴリズムとプログラミング
問11：計算量がデータ件数nの2乗に比例するアルゴリズムでは、データ量が10倍になると処理時間はおよそ100倍になる。
解答を見る
○ nの2乗に比例する場合、nが10倍になれば処理時間は10の2乗＝100倍になる。計算量の違いは、データ量が大きくなるほど実行時間の差として顕著に現れる。
重要度：B 論点：アルゴリズムとプログラミング
問12：重複するキーを許さない標準的な2分探索木では、どの節においても、左部分木の値はその節の値より大きくなるように構成される。
解答を見る
× 大小関係が逆である。重複するキーを許さない標準的な2分探索木では、左部分木にその節より小さい値、右部分木にその節より大きい値を配置する。重複キーを許す場合の配置規則は実装によって異なる。
重要度：B 論点：アルゴリズムとプログラミング
問13：一般的なプログラムの関数呼出しでは、呼出し元へ戻るための情報や局所変数の管理にスタックが使われる。
解答を見る
○ 一般的な実装では、関数を呼び出すたびに戻り先や局所変数などをスタックフレームへ格納し、処理が終わると後入れ先出しの順に取り出す。ただし、インライン展開や末尾呼出し最適化などによって、通常のスタックフレームを作らない場合もある。
重要度：B 論点：アルゴリズムとプログラミング
問14：整列されていないn件のデータに目的データが1件あり、その位置が各要素で同じ確率であるとき、線形探索の平均比較回数はnに比例して増える。
解答を見る
○ 先頭から順に比較するため整列は不要である。目的データが各位置に同じ確率で存在すると仮定すると、平均比較回数は（n＋1）÷2であり、データ件数nに比例して増える。
重要度：C 論点：アルゴリズムとプログラミング
問15：再帰呼出しを用いた関数は、終了条件を定義していなくても、呼出しがいつかは必ず自然に停止する。
解答を見る
× 終了条件が無い、又は終了条件に到達しない再帰は停止せず、呼出しのたびにスタックを消費し続けて異常終了の原因になる。再帰の設計では終了条件の定義が必須である。
コメント