109 關務特考三等 資訊處理 資料結構 考古題詳解
第 一 題20 分
資料庫應用中，需要根據主鍵值（Primary Key）建立索引檔，索引檔的建立常使用 -tree 樹狀結構。今有一串資料，其主鍵值分別為：、、、、、、、。
(一) 畫出將此串資料建成 order 的 -tree。
(二) 畫出從此串資料新增（Insert）主鍵值 後，order 的 -tree。
(三) 畫出從此串資料刪除（Delete）主鍵值 後，order 的 -tree。
登入後即可作答並保存紀錄。
核心觀念
-tree 是多路平衡搜尋樹。此題的 表示每個節點最多有 個子節點，因此最多可放 個索引鍵；除根節點外，每個內部節點至少有 個子節點，也就是至少有 個索引鍵。所有葉節點都位於同一層。
節點內的索引鍵依遞增排列。若節點含索引鍵 ，則其三個子樹的鍵值範圍依序為：小於 、介於 與 之間、大於 。
解題方法
依題目給定的順序逐筆插入。節點若暫時出現 個索引鍵，就將中間鍵提升至父節點，左右兩個鍵分別形成分裂後的節點；若根節點分裂，則建立新根。
（一）建立 order 3 的 -tree
插入 後，根節點暫時成為 。將中間鍵 提升為新根：
[39]
/ \
[29] [44]
接著插入 。右側葉節點成為 ，分裂並將 提升至根：
[39,64]
/ | \
[29] [44] [67]
插入 後，落在 與 之間的葉節點為 ；插入 至最右葉節點，得到 。最後插入 ，中間葉節點成為 ，分裂並將 提升至根。根也因此溢位，將根內三個鍵分裂並提升中間鍵 ：
[49]
/ \
[39] [64]
/ \ / \
[29] [44] [59] [67,69]
（二）新增主鍵值
第 二 題20 分
給定一個無向圖（Undirected Graph） 的鄰接列表（Adjacency List）如下圖，試依據該列表提供的資訊繪製出對應的無向圖 ，然後由節點（Vertex） 為起始點繪製 Depth First Search（DFS）與 Breadth First Search（BFS）生成樹（Spanning Tree）。遇有多個節點可被走訪時，字母順序越前面的節點，其被走訪的優先順序就越高。
鄰接列表：
- ：、
- ：、、
- ：、、
- ：、
- ：、
- ：、
- ：、
- ：、、、
🖼️【此處有附圖，請對照原卷】
登入後即可作答並保存紀錄。
核心觀念
本題考查無向圖的鄰接列表表示，以及從指定起點建立深度優先搜尋（DFS）與廣度優先搜尋（BFS）生成樹。
無向圖中，若 列在 的鄰接列表，則 也會列在 的鄰接列表；同一條邊只計一次。生成樹包含所有可到達的頂點，且不含環，因此有 個頂點時，生成樹有 條邊。
解題方法
依鄰接列表整理出無向圖的邊：
對應的無向圖如下：
graph LR
A --- B
A --- C
B --- D
B --- E
C --- F
C --- G
D --- H
E --- H
F --- H
G --- H
**DFS：**從 出發，每次走訪尚未拜訪的相鄰頂點，並依字母順序優先。走訪次序為：
DFS 生成樹的邊為：
graph LR
H --- D
D --- B
B --- A
A --- C
C --- F
C --- G
B --- E
第 三 題20 分
新冠肺炎肆虐全球，目前世界各國生物及醫學實驗室均在尋找新型冠狀病毒的基因。假設新型冠狀病毒的基因由 A、T、C、G、H、M 核苷酸所組成，今有一新型冠狀病毒的基因為：
ATATATCCHCGMCMA
請使用霍夫曼演算法（Huffman Algorithm）設計霍夫曼樹（Huffman Trees），並設計一編碼表（Code Words），依序分別寫出 A、T、C、G、H、M 核苷酸的編碼位元數，將此新型冠狀病毒基因以最少位元數（Minimum Bit Strings）編碼，並計算出最少位元數（Minimum Bit Strings）。
登入後即可作答並保存紀錄。
核心觀念
本題考霍夫曼編碼（Huffman Coding）：依各符號出現頻率反覆取出頻率最低的兩個節點合併，直到形成一棵二元樹。每次合併後，兩個子節點的頻率相加，作為新節點的頻率。
將霍夫曼樹的左、右分支分別標為 與 ，根節點到各核苷酸葉節點的路徑即為該核苷酸的編碼。頻率越高的符號通常位於越淺處，編碼也越短；霍夫曼編碼可使總編碼位元數最小。
解題方法
先統計基因序列 ATATATCCHCGMCMA 中各核苷酸的出現次數：
| 核苷酸 | A | T | C | G | H | M |
|---|---|---|---|---|---|---|
| 出現次數 | 3 | 3 | 4 | 1 | 1 | 3 |
合計 個核苷酸。
依頻率由小到大執行霍夫曼合併。相同頻率的節點可以有不同合併順序；以下採用一種合法順序：
| 步驟 | 合併節點 | 新節點頻率 |
|---|---|---|
| 1 | G(1) 與 H(1) | 2 |
| 2 | GH(2) 與 M(3) | 5 |
| 3 | A(3) 與 T(3) | 6 |
| 4 | C(4) 與 GHM(5) | 9 |
| 5 | AT(6) 與 CGHM(9) | 15 |
由此得到一棵霍夫曼樹。將左分支標為 、右分支標為 ，可得下列編碼表：
第 四 題20 分
給予一串資料：，將此串資料依序建成一 max-heap 樹，並說明如何從此 max-heap 樹進行由小至大的排序（Sorting）。
登入後即可作答並保存紀錄。
核心觀念
本題考查 max-heap（最大堆積） 的建立，以及利用最大堆積進行由小至大的 Heap Sort（堆積排序）。
最大堆積是一棵完全二元樹，且每個節點的鍵值都大於或等於其子節點。以陣列表示時，採 1 起始索引，索引 的左、右子節點分別為 、。因此，陣列必須符合完全二元樹的排列方式，並滿足每個父節點不小於子節點。
解題方法：依序插入建立 max-heap
將資料依序插入堆積末端。每插入一個數值，就將它與父節點比較；若大於父節點，便向上交換，直到符合最大堆積性質。
| 插入值 | 插入並向上調整後的陣列 |
|---|---|
以插入 為例：先將 放在索引 ，與父節點索引 的 交換；再與父節點索引 的 交換。插入最後一個數值 時，它只需與父節點 交換。
因此，建立完成的 max-heap 陣列為：
對應的堆積樹為：
第 五 題20 分
給予兩線性鏈結串列，其節點 C 語言的宣告如下：
#include <stdio.h> #include <stdlib.h>
struct node { int data; struct node *next; };
typedef struct node *NODEPTR;
此兩線性鏈結串列，分別由指標 plist1 與 plist2 指在串列首，請完成下列程式片段，將 plist2 所指串列接在 plist1 所指串列後面。
void concate(NODEPTR plist1, NODEPTR plist2) { NODEPTR p; }
登入後即可作答並保存紀錄。
核心觀念
本題考單向鏈結串列的串接。每個節點的 next 指向下一個節點；串列尾端節點的 next 為 NULL。要把 plist2 所指串列接到 plist1 後方，先走訪 plist1 找到尾端，再令尾端的 next 指向 plist2。
解題方法
從 plist1 的首節點開始，沿著 next 前進；當目前節點的 next 為 NULL 時，就找到尾端。將尾端的 next 設為 plist2，即可完成串接。
void concate(NODEPTR plist1, NODEPTR plist2)
{
NODEPTR p;
if (plist1 == NULL)
return;
p = plist1;
while (p->next != NULL)
p = p->next;
p->next = plist2;
}
例如，若兩串列原先為：
plist1：A → B → NULL
plist2：C → D → NULL
走訪到 B 後，將 B->next 設為 plist2，結果為：
A → B → C → D → NULL