110 身心障礙特考三等 資訊處理 資料結構 考古題詳解

核心觀念

稀疏矩陣的非零元素遠少於所有元素的總數。若矩陣大小為 $r\times c$、非零元素數為 $t$，一般二維陣列需儲存 $rc$ 個值；稀疏表示法只記錄非零元素及其座標，空間需求可降為 $O(t)$。

以下採用三元組表示法：每個非零元素記錄列索引、行索引和值。索引採 C 語言常見的 0 起算方式。矩陣相乘則以列鏈結串列儲存各列的非零元素，方便依列走訪及累加乘積。

解題方法

（一）稀疏矩陣資料結構

三元組中的 row、col 與題目慣用的「列、行」方向容易混淆，因此程式碼以 row 表示矩陣的列索引、col 表示行索引。

typedef struct {
 int row; // 列索引，0 起算
 int col; // 行索引，0 起算
 double value; // 非零值
} Term;

typedef struct {
 int rows; // 矩陣列數
 int cols; // 矩陣行數
 int terms; // 非零元素數
 Term *data; // 長度為 terms 的三元組陣列
} SparseMatrix;

data[k] 儲存一個非零元素及其座標。矩陣中值為 $0$ 的元素不建立三元組，因此不占用儲存空間。三元組可依 (row, col) 排序；以下轉置程式會按列、行順序輸出結果。

（二）矩陣轉置

轉置會交換每個非零元素的列與行索引，並交換矩陣的列數與行數：

以下採簡單的逐欄掃描：依原矩陣的欄索引 c 由小到大掃描全部三元組。每次找到該欄的元素，就交換其索引後寫入結果。這樣輸出的三元組會依新矩陣的列、行順序排列，時間複雜度為 $O(cols\times terms)$。

#include <stdlib.h>

int transpose(const SparseMatrix *src, SparseMatrix *dst)
{
 dst->rows = src->cols;
 dst->cols = src->rows;
 dst->terms = src->terms;
 dst->data = NULL;

 if (src->terms == 0)
 return 1;

 dst->data = malloc((size_t)src->terms * sizeof(Term));
 if (dst->data == NULL)
 return 0;

 int k = 0;
 for (int c = 0; c < src->cols; ++c) {
 for (int i = 0; i < src->terms; ++i) {
 if (src->data[i].col == c) {
 dst->data[k].row = src->data[i].col;
 dst->data[k].col = src->data[i].row;
 dst->data[k].value = src->data[i].value;
 ++k;
 }
 }
 }
 return 1;
}

呼叫成功後，dst->data 由呼叫端負責釋放；來源與目的矩陣應使用不同的結構，避免覆寫來源資料。

（三）矩陣相乘

令 $A$ 為 $m\times n$ 矩陣，$B$ 為 $n\times l$ 矩陣，則乘積 $C=AB$ 的大小為 $m\times l$，元素定義為：

只有當 $A_{i,k}$ 與 $B_{k,j}$ 都是非零值時，才會對 $C_{i,j}$ 累加乘積。以下將三元組依列分組成鏈結串列，讓程式依序取得 $A$ 的第 $i$ 列，以及 $B$ 中列索引等於 $k$ 的元素。

核心觀念

本題考有向加權圖的相鄰矩陣，以及 Floyd–Warshall 全點對最短路徑演算法。相鄰矩陣的列代表出發點、欄代表到達點；若有邊，填入該邊權重，若無邊則填入 $\infty$，對角線填 $0$。

解題方法

依圖中箭頭方向讀取邊，矩陣列、欄順序均採 $A,B,C,D,E$。例如，$A\to B$ 權重為 $8$，所以第 $A$ 列、第 $B$ 欄填 $8$；反向的 $B\to A$ 權重為 $7$，因此第 $B$ 列、第 $A$ 欄填 $7$。

（一）相鄰矩陣

此矩陣是加權有向圖的相鄰矩陣；$W_{ij}$ 表示從節點 $i$ 到節點 $j$ 的直接邊權重。

（二）Floyd–Warshall 演算法

依序把 $A,B,C,D,E$ 當作中繼點。令 $D^{(k)}_{ij}$ 表示只允許前 $k$ 個節點作為中繼點時，從 $i$ 到 $j$ 的最短距離，更新公式為：

每次更新都比較「目前距離」與「經過新中繼點的距離」，取較小值。計算結果如下，矩陣列、欄順序皆為 $A,B,C,D,E$。

初始矩陣 $D^{(0)}=W$：

以 $A$ 為中繼點後，$B\to C$ 更新為 $7+4=11$，$B\to D$ 更新為 $7+8=15$；$D\to B$ 更新為 $4+8=12$，$D\to C$ 更新為 $4+4=8$：

核心觀念

$m=5$ 表示每個節點最多有 $5$ 個子節點、最多存放 $4$ 個鍵值。非根節點至少有 $\lceil 5/2\rceil=3$ 個子節點，因此至少有 $2$ 個鍵值；根節點至少有 $1$ 個鍵值。節點鍵值超過上限時，將中間鍵值提升至父節點，並把節點分成左右兩個節點；若父節點也溢位，分裂會向上傳遞。

（一）$K$ 層以上的 B-tree 最少資料筆數

要讓樹具有至少 $K$ 層，採用每層節點數及鍵值數皆為最少的結構：

• 根節點有 $1$ 個鍵值，並至少有 $2$ 個子節點。
• 根的下一層有 $2$ 個節點；之後每個非根內部節點至少有 $3$ 個子節點。
• 每個非根節點至少有 $2$ 個鍵值。

因此，第 $i$ 層（根為第 $1$ 層，$i\ge 2$）最少有 $2\cdot 3^{i-2}$ 個節點，各有 $2$ 個鍵值。總筆數為

所以，具有 $K$ 層以上的 $5$-way B-tree 最少可存放

（二）依序執行 $\operatorname{insert}(7)$ 與 $\operatorname{insert}(28)$

初始根節點為 $[9,20]$，三個子節點依序為 $[1,3,5]$、$[11,14,16,18]$、$[22,24,26,27]$。

插入 $7$ 後，第一個葉節點成為 $[1,3,5,7]$，未超過每個節點最多 $4$ 個鍵值的限制。

核心觀念

霍夫曼碼（Huffman code）是一種最佳前綴碼：任何一個字元的編碼都不是另一個字元編碼的前綴，因此解碼時不需要分隔符號。

建構時反覆選取目前頻率最低的兩個節點，合併成一個頻率為兩者總和的父節點，直到只剩一個根節點。由根走到葉節點的路徑形成該字元的碼字；每次向左記為 $0$，向右記為 $1$。低頻字元通常位於較深處，高頻字元則通常位於較淺處，以降低加權碼長。

解題方法

先計算訊息中每個字元的出現次數。訊息共有 $27$ 個字元，包含 4 個底線：

頻率總和為 $27$。為使合併過程與碼字明確，以下遇到同頻節點時，以字元名稱及子樹內字元名稱的字典序決定先後；每次合併中，頻率較小者置左，並以左枝 $0$、右枝 $1$ 記碼。霍夫曼碼遇到同頻節點時可以有不同的合併順序，因此碼字不唯一，但都能達到最佳加權碼長。

建構霍夫曼樹

依序合併兩個最低頻率的節點：

最後只剩頻率 $27$ 的根節點，建樹完成。沿樹由根至葉記錄 $0$、$1$，得到一組霍夫曼碼：