Programming to use computers and networks: Practice Questions

あるコンピュータにおいて、主記憶装置へのアクセス時間が 50 ns、キャッシュメモリへのアクセス時間が 10 ns であるとする。ヒット率（必要なデータがキャッシュメモリにある確率）が 0.9 のとき、平均アクセス時間は何 ns か計算せよ。

次のPythonコードを実行したとき、画面に出力される値は何か。
a = [1, 2, 3, 4, 5]
b = [x * 2 for x in a if x % 2 == 0]
print(sum(b))

Pythonなどのプログラミング言語において、再帰関数を用いて階乗を計算するアルゴリズムを考える。以下の関数 \(f(n)\) において、\(f(4)\) を呼び出した際に実行される加算や乗算の回数を考慮し、最終的な返り値を答えなさい。
関数定義:
\(f(n)\) :
  if \(n == 0\) return 1
  else return \(n \times f(n-1)\)

2分探索（バイナリサーチ）アルゴリズムを用いて、昇順にソートされた 100 個の要素を持つ配列から特定の値を探索する。ターゲットが存在しない場合も含め、最大で何回の比較が必要か。

スタック（Stack）とキュー（Queue）のデータ構造に関する問題である。空のスタック \(S\) と空のキュー \(Q\) に対して、以下の操作を順に行ったとき、最後にキュー \(Q\) から取り出される値はどれか。
1. \(S\) に 10, 20, 30 をこの順でプッシュする。
2. \(S\) から 1 つポップし、その値を \(Q\) に追加する。
3. \(S\) から 1 つポップし、その値を \(Q\) に追加する。
4. \(Q\) から 1 つデータを取り出し、破棄する。
5. \(Q\) から 1 つデータを取り出す。

要素数 \(n\) の未整列の配列に対して選択ソート（基本選択法）を適用する場合を考える。比較回数を \(C(n)\)、要素の入れ替え回数の最大値を \(S(n)\) とするとき、\(n=8\) の場合における \(C(8)\) と \(S(8)\) の値を求めよ。また、配列が最初から昇順に並んでいた場合、比較回数 \(C(8)\) はどのように変化するか説明せよ。

あるプログラミングの問題として、階段を上る方法の総数を求めるアルゴリズムについて考えます。一度に1段または2段上ることができるとき、\( n \) 段の階段を上る方法の総数を \( f(n) \) と定義します。以下の各問いに答えなさい。

(a) \( f(5) \) の値を求めなさい。
(b) この関数を再帰的に定義すると、\( f(n) = f(n-1) + f(n-2) \)（ただし \( f(1)=1, f(2)=2 \)）となります。この単純な再帰関数を用いて \( n \) が大きい場合の値を求める際、計算時間は \( n \) に対してどのように増加しますか。「指数関数的」または「線形的」のいずれかで答えなさい。
(c) 計算効率を劇的に改善するために、一度計算した値を配列などのデータ構造に保存しておき、同じ計算を繰り返さないようにする手法を何と呼びますか。また、その手法を用いた場合の計算量を \( O \) 記法を用いて答えなさい。