アルゴリズムとデータ構造テスト解説

1. 正誤問題 [1]

(a) アクセス頻度の高いデータセットは予め整列した方が探索効率が上がる。

正 [1]
アクセス頻度の高いデータセットを事前に整列しておくことで、二分探索などの効率的な探索アルゴリズムを利用できるようになり、探索時間を大幅に短縮できます。

(b) 挿入ソートなどの単純なソート方法はワーストケースでO(n²)の計算量が必要である。

正 [1]
挿入ソートは、最悪の場合（逆順に並んでいる場合など）に、比較と挿入の回数がデータの数nに対して二乗のオーダーで増加するため、O(n²)の計算量が必要になります。

(c) クイックソートが要素を選択して2つの部分列に分割するのに対して、マージソートは整列された2つの部分列を併合して1つの整列したデータ列を作る。

正 [1]
クイックソートは、ピボット（基準値）を選び、それより小さい要素と大きい要素に分割する操作を繰り返します。
マージソートは、データを分割し、ソート済みの部分列をマージ（併合）することで、全体のソートを行います。

(d) 二分探索木における探索の計算量は木の高さに依存する。

正 [1]
二分探索木では、探索は根から葉に向かって行われ、比較の回数が木の高さに比例するため、計算量は木の高さに依存します。

(e) 二分探索木は木のバランスを考慮しなくてもよい。

誤 [1]
二分探索木が偏った形（例えば、片側にだけノードが連なっている状態）になると、木の高さが大きくなり、探索の計算量が悪化します。そのため、バランスを考慮する必要があります。

(f) ハッシュ法では広いキーの空間を有限な値域に対応させるため衝突処理が必要となる。

正 [1]
ハッシュ法では、異なるキーが同じハッシュ値になる衝突が起こり得ます。そのため、衝突を回避または解決する衝突処理が必要です。

(g) 有向グラフのノードを繋げる辺はループを形成する場合もある。

正 [1]
有向グラフでは、あるノードから自分自身に戻る辺（ループ）が存在することがあります。

(h) 無向グラフは隣接リスト法で表現できない。

誤 [1]
無向グラフも隣接リスト法で表現できます。各ノードに対して、隣接するノードのリストを持つことで表現可能です。

(i) グラフの探索は、すでに訪れたことのあるノードの情報を保持しておく必要がある。

正 [1]
グラフ探索では、無限ループに陥るのを防ぎ、効率的に探索を行うために、すでに訪れたノードを記録しておく必要があります。

(j) 動的計画法では計算回数を減らすために途中の小さい問題の解を保存する必要がない。

誤 [1]
動的計画法では、部分問題の解を再利用することで計算量を削減するため、途中の解を保存する必要があります。

2. アルゴリズムの時間計算量 [2-4]

アルゴリズム	時間計算量
要素数nの配列に対するマージソート	O(n log n)
要素数nの配列に対する線形探索	O(n)
整列済み要素数nの配列に対する線形探索	O(n)
整列済み要素数nの配列に対する二分探索	O(log n)
要素数nのハッシュ表に対する探索(衝突なし)	O(1)
要素数nのスタックから1つの要素を取り出すpop操作	O(1)
要素数nのキューから1つの要素を取り出すDequeue操作	O(1)
要素数nの連結リストの先頭に新たな要素を追加する挿入操作	O(1)
要素数nの連結リストに対し特定のキーを持つ要素の存在を確かめる検索	O(n)
要素数nの二分木の全てのノードを体系的に訪問するPre-order巡回	O(n)

3. アルゴリズムとデータ構造の選択 [4-6]

(a) 連鎖行列積（行列チェーン乗算）を効率的に求める手法

動的計画法 [4, 6]
- 動的計画法は、連鎖行列積の最適解を効率的に求めるために用いられます。

(b) 逆ポーランド記法で記述された数式を評価するために応用できるデータ構造

スタック [4, 6]
- スタックは、逆ポーランド記法の数式を評価する際に、オペランド（数値）を一時的に保存し、演算子が現れたときにオペランドを取り出して計算するために利用できます。

(c) 最長共通部分列を効率的に求める手法

動的計画法 [4, 6]
- 動的計画法は、最長共通部分列問題を効率的に解くために用いられます。

(d) クイックソートを実装するための手法

分割統治法 [4, 6]
- クイックソートは、分割統治法に基づいて実装されます。

(e) 深さ優先探索において、探索途中のノードを一時的に退避（記憶）しておくために有効なデータ構造

スタック [4, 6]
深さ優先探索では、次に訪問するノードをスタックに保存します。

(f) 幅優先探索において、始点により近いノードから訪問するようにノードを管理するためのデータ構造

キュー [5, 6]
- 幅優先探索では、訪問するノードをキューに格納し、FIFO（先入れ先出し）の順で取り出すことで、始点に近いノードから順に訪問します。

(g) 添え字に数値以外のデータ型（文字列等）も使用できる連想配列（辞書）を実装するために有効なデータ構造

ハッシュ [5, 6]
- ハッシュテーブルは、キー（文字列など）をハッシュ関数を用いてインデックスに変換し、値を格納するため、連想配列の実装に適しています。

(h) 二分探索木が満たす条件（binary-search-tree property）とは何か

二分探索木では、左部分木のすべてのノードのキーは、親ノードのキーよりも小さく、右部分木のすべてのノードのキーは、親ノードのキーよりも大きいという条件を満たす必要があります [5] 。

(i) クイックソートの欠点をキーワード「入力データ」「時間計算量」を用いて述べよ。

クイックソートの欠点として、入力データが最悪のケース（例えば、既にソートされている場合）の場合には、時間計算量がO(n^2)となってしまうことが挙げられます [5]。

(j) 安定なソートとはどのようなアルゴリズムか、説明せよ。

安定なソートとは、同じ値の要素が複数存在する場合に、ソート後もそれらの要素の相対的な順序が変化しないソートアルゴリズムです [6].

(k) 連結リストの長所と短所を述べよ。

長所:
- データの挿入や削除が**O(1)**で効率的に行える [6].
- メモリを動的に確保できるため、可変長のデータを扱うのに適している。
短所:
- ランダムアクセス（特定のインデックスの要素に直接アクセス）が**O(n)**で効率が悪い [6].
- ポインタのための追加のメモリが必要となる.

4. アルゴリズムの実装

この問題では、再帰型マージソート、クイックソート、二分探索の関数を完成させる必要があります [1, 2]。

(a) 再帰型マージソート関数の完成

マージソートは、分割統治法に基づくアルゴリズムで、配列を再帰的に半分に分割し、ソートされた部分配列をマージすることで全体をソートします。 merge(A, l, m, r) 関数は、すでにソート済みの2つの部分配列をマージする関数です [1]。

void mergeSort(int A[], int l, int r) {
    int m;
    if (l < r) {
        m = (l + r) / 2; // 配列の中央のインデックスを計算
        mergeSort(A, l, m); // 左半分を再帰的にソート
        mergeSort(A, m + 1, r); // 右半分を再帰的にソート
        merge(A, l, m, r);   // ソートされた2つの部分配列をマージ
    }
}

m = (l + r) / 2;: 配列を分割する中央のインデックスを計算します。
mergeSort(A, l, m);: 左側の部分配列を再帰的にソートします。
mergeSort(A, m + 1, r);: 右側の部分配列を再帰的にソートします。
merge(A, l, m, r);: ソートされた左右の部分配列をマージします。

(b) 再帰型クイックソート関数の完成

クイックソートも分割統治法に基づくアルゴリズムですが、ピボットと呼ばれる要素を選択し、それより小さい要素と大きい要素に分割します。partition(A, l, r) 関数は、分割を行い、ピボットのインデックスを返します。

void quickSort(int A[], int l, int r) {
    int q;
    if (l < r) {
        q = partition(A, l, r); // 配列を分割し、ピボットの位置を取得
        quickSort(A, l, q - 1);   // 左側の部分配列を再帰的にソート
        quickSort(A, q + 1, r);   // 右側の部分配列を再帰的にソート
    }
}

q = partition(A, l, r);: 配列をピボットを基準に分割し、ピボットの位置qを取得します。
quickSort(A, l, q - 1);: 左側の部分配列を再帰的にソートします。
quickSort(A, q + 1, r);: 右側の部分配列を再帰的にソートします。

(c) 二分探索関数の完成

二分探索は、ソート済みの配列から特定の値を効率的に検索するアルゴリズムです。配列の中央の値と比較することで、検索範囲を半分ずつ絞っていきます。

int binarySearch(int A[], int n, int key) {
    int l = 0;
    int r = n - 1;
    int m;
    while (l <= r) {
        m = (l + r) / 2;
        if (key == A[m]) return m;   // キーが見つかったらインデックスを返す
        else if (key < A[m]) r = m - 1; // キーが中央値より小さければ、右側の検索範囲を狭める
        else l = m + 1; // キーが中央値より大きければ、左側の検索範囲を狭める
    }
    return -1;  // キーが見つからなかったら-1を返す (NIL)
}

while (l <= r): 検索範囲がある間繰り返します。
m = (l + r) / 2;: 中央のインデックスを計算します。
if (key == A[m]) return m;: キーが見つかったら、そのインデックスを返します。
else if (key < A[m]) r = m - 1;: キーが中央の値より小さければ、検索範囲の右端を中央のインデックスの1つ前に移動します。
else l = m + 1;: キーが中央の値より大きければ、検索範囲の左端を中央のインデックスの1つ後に移動します。
return -1;: ループが終了した場合（キーが見つからなかった場合）-1を返します。

5. データ構造の操作

この問題では、キューとスタックの基本的な操作（pushとpop）の結果を理解する必要があります。

(a) キューの場合

キューはFIFO (First-In, First-Out) のデータ構造で、最初に入れたものが最初に出てきます。操作は次の順序で行われます。

1. 62, 59, 71, 31 を順番にpush
1. pop() -> 62 が取り出される
1. 99 をpush
1. pop() -> 59 が取り出される
1. pop() -> 71 が取り出される
1. 80をpush
1. pop() -> 31が取り出される
1. 100 をpush
1. pop() -> 99 が取り出される
1. pop() -> 80 が取り出されるしたがって、キューのpop操作で得られる要素の順序は 62, 59, 71, 31, 99, 80, 100 です。

(b) スタックの場合

スタックはLIFO (Last-In, First-Out) のデータ構造で、最後に入れたものが最初に出てきます。操作は次の順序で行われます。

1. 62, 59, 71, 31 を順番にpush
1. pop() -> 31 が取り出される
1. 99 をpush
1. pop() -> 99 が取り出される
1. pop() -> 71 が取り出される
1. 80をpush
1. pop() -> 80が取り出される
1. 100 をpush
1. pop() -> 100が取り出される
1. pop() -> 59が取り出される
1. pop() -> 62が取り出されるしたがって、スタックのpop操作で得られる要素の順序は 31, 99, 71, 80, 100, 59, 62 です。

6. ハッシュ表の詳細解説

この問題では、ハッシュ関数を用いてハッシュ表にキーを挿入し、衝突が発生した場合の対処法を理解する必要があります [1, 2].

ハッシュテーブルのサイズ (m) は7 [1].
挿入するキーは {11, 4, 6, 10, 2, 24, 22} [1].
ハッシュ関数は開番地法（オープンアドレス法）を用いており、具体的には h(k, i) = (ha(k) + i * hb(k)) mod m で、 ha(k) = k mod m, hb(k) = 1 + k mod (m-1) で定義されています [2]. ここで、 i は衝突が発生した際に試行する回数を示します。

(a) ハッシュ表の決定

各キーを順番にハッシュ表に挿入する手順を詳しく見ていきましょう。衝突が発生した場合には、 i を増やしながらハッシュ値を計算し、空いている場所を探します [2].

キー (k)	ha(k) = k mod 7	hb(k) = 1 + k mod 6	i	h(k,i) = (ha(k) + i * hb(k)) mod 7	ハッシュ表のインデックス
11	4	6	0	(4 + 0 * 6) mod 7 = 4	4
4	4	5	0	(4 + 0 * 5) mod 7 = 4	衝突
			1	(4 + 1 * 5) mod 7 = 2	2
6	6	1	0	(6 + 0 * 1) mod 7 = 6	6
10	3	5	0	(3 + 0 * 5) mod 7 = 3	3
2	2	3	0	(2 + 0 * 3) mod 7 = 2	衝突
			1	(2 + 1 * 3) mod 7 = 5	5
24	3	1	0	(3 + 0 * 1) mod 7 = 3	衝突
			1	(3 + 1 * 1) mod 7 = 4	衝突
			2	(3 + 2 * 1) mod 7 = 5	衝突
			3	(3 + 3 * 1) mod 7 = 6	衝突
			4	(3 + 4 * 1) mod 7 = 0	0
22	1	5	0	(1 + 0 * 5) mod 7 = 1	1

この表に基づいて、ハッシュ表は次のようになります。

インデックス	0	1	2	3	4	5	6
キー	24	22	4	10	11	2	6

(b) 衝突の総回数

上記の表からわかるように、衝突が発生した回数を数えることで、衝突の総回数を計算できます。

4を挿入する際に1回
2を挿入する際に1回
24を挿入する際に4回

したがって、合計で 7 回の衝突が発生しています [2].

7. グラフに関する問題 [1, 2]

(a) 隣接行列の表示 [1]

与えられた無向グラフの隣接行列を示す必要があります。隣接行列は、グラフの頂点間の隣接関係を表す正方行列です。行列の (i, j) 成分は、頂点 i から頂点 j へ辺が存在するかどうかを示します。無向グラフの場合、隣接行列は対称になります。

与えられたグラフに基づいて隣接行列を作成する必要があります。

(b) 深さ優先探索（DFS）における発見時刻と終了時刻 [1]

**深さ優先探索（DFS）は、グラフを探索するためのアルゴリズムの一つです。この問題では、ノード s を始点としてDFSを行い、各ノードの発見時刻（d）と終了時刻（f）**を記録する必要があります。

発見時刻（d）: ノードが最初に訪問された時刻
終了時刻（f）: ノードのすべての子ノードが訪問された後、ノードの探索が完了した時刻

DFSにおいて、隣接ノードを訪問する順序は辞書順で小さいノードから選ぶという条件があります。ノード s の発見時刻を1とします。

(c) 深さ優先探索の可能な結果の列挙 [2]

ノード s を始点とする深さ優先探索のすべての可能な結果を示す必要があります。深さ優先探索において、隣接するノードを訪問する順番は自由に選択できます。例えば、結果の一つとして s → v → w が挙げられます。

8. 経路探索に関する問題 [2, 3]

(a) 最短経路の数 [2]

Pさんが自宅Aから会社Dへ遠回りをせずにいく経路が何通りあるかを、それぞれの交差点への経路の数も合わせて示す必要があります。道は縦横の整然としたマス目で、交差点と交差点の距離はすべて1とします。

(b) 経路数の漸化式 [3]

交差点の横方向の順番をx、縦方向の順番をyとし、(x, y)はそれぞれの交差点の位置を表します。自宅から交差点(x, y)までの経路の数X(x, y)の漸化式を示す必要があります。なお、(0, 0)が自宅の位置で、X(0, 1) = X(1, 0) = 1とします。

(c) 新しい道と通行不能な交差点がある場合の経路数 [3]

新たな道Eを利用することができ、かつ交差点B, Cが工事中で通行不能な場合、Pさんが自宅から会社へ行く経路が何通りとなるかを求める必要があります。工事中以外の交差点への経路の数も合わせて示します。

9. 重み付き無向グラフに関する問題 [3, 4]

(a) Primのアルゴリズムによる最小全域木 [3]

図に示すグラフについて、頂点1を起点（根）とし、 Primのアルゴリズムを適用した**最小全域木（Minimum Spanning Tree）**を作成する必要があります。各計算ステップで最小全域木に追加する辺を順番に示します。

Primのアルゴリズムは、重み付きグラフにおいて、すべての頂点をつなぐ最小のコストの木のことを指します。

(b) 迷路の最短経路コスト [4]

迷路を解くプログラムを作成したい。迷路は、部屋を頂点、それらを双方向に結ぶ道が辺となっている重み付き無向グラフで表されます。辺に書かれている数字は道を通るために必要なコストを示します。始点sから各部屋への最短コストを示す必要があります。コストは図の頂点の内部に記述し、sのコストを0とします。Ï

Last modified: 06 February 2025