114 年 國立嘉義大學資訊工程學系碩士班《資料結構》
第 1 題10 分
- How many children does a binary tree have?
登入後即可作答並保存紀錄。
核心觀念
二元樹（binary tree）的定義是：每個節點最多擁有兩個子節點，且分別稱為左子節點（left child）與右子節點（right child）。
因此，單一節點的子節點數量可能是：
- 個：葉節點（leaf）
- 個：只有左子節點或右子節點
- 個：同時具有左、右子節點
解題方法
題目問：
How many children does a binary tree have?
依二元樹的標準定義，重點是「每個節點最多有兩個子節點」，因此答案不是「每個節點一定有兩個」，而是：
第 2 題20 分
- Consider the following recursive function.
int f(int a, int b)
{
if (a % b == 0)
return b;
else
return f(b, a % b);
}
a. What is the output value given by ? (10%)
b. What is the output value given by ? (10%)
登入後即可作答並保存紀錄。
核心觀念
此函式實作的是歐幾里得演算法，用來求兩個整數的最大公因數：
當 時，表示 已經是 的最大公因數，因此函式回傳 。
解題方法
依照每次遞迴呼叫計算餘數，直到餘數為 。
a. 計算
因此：
繼續計算：
遞迴過程為：
因為：
所以：
因此：
b. 計算
先計算：
第 3 題20 分
- Answer the following questions with either true or false. Assume there are elements in the data structure.
a. The core data structure of Depth-First Search is a list. (4%)
b. One can reverse the order of the elements in a linked list in time . (4%)
c. Returning the maximum element in a max-heap (but not deleting it from the heap) can be done in time . (4%)
d. One can implement a stack (of unbounded size) based on an array so that each individual push/pop operation is time . (4%)
e. One can implement a stack based on a linked list so that each individual push/pop operation is time . (4%)
登入後即可作答並保存紀錄。
(a)
解析：
深度優先搜尋（Depth-First Search, DFS）的核心資料結構為堆疊（Stack）（或利用遞迴呼叫系統 Stack），而廣度優先搜尋（BFS）的核心資料結構才是佇列（Queue）。因此本敘述錯誤。
【答案】False
(b)
解析：
反轉一個包含 個元素的鏈結串列（Linked List），只需走訪串列一次並依次調整節點指標方向，時間複雜度為 ，額外空間複雜度為 。因此本敘述正確。
【答案】True
(c)
解析：
在最大堆疊（Max-Heap）中，最大元素必定位於樹根（Root node）。若僅讀取並回傳最大值而不做刪除，直接存取根節點即可，時間複雜度為 。因此本敘述正確。
【答案】True
第 4 題10 分
- Kruskal's algorithm builds a minimum cost spanning tree T by adding edges to T one at a time. The following is Kruskal's algorithm and the original graph with weighted values. Show the minimum cost spanning tree T by means of Kruskal's algorithm.
(10%)
🖼️【此處有附圖，請對照原卷】
登入後即可作答並保存紀錄。
核心觀念
Kruskal 演算法依邊權重由小到大檢查，每次加入一條不會形成環的邊。對含有 個頂點的連通圖，最小生成樹會有 條邊；本圖有 個頂點，因此要選出 條邊。
解題方法
依圖讀出各邊及權重，按權重由小到大排列：
| 權重 | 邊 |
|---|---|
| 10 | |
| 12 | |
| 14 | |
| 16 | |
| 18 | |
| 22 | |
| 24 | |
| 25 | |
| 28 |
依序選邊：
第 5 題20 分
- For the digraph shown in the right hand side: (20%)
a. Obtain its adjacency-matrix
b. Obtain its adjacency-list representation
c. Obtain its inverse adjacency-list representation.
d. Obtain its adjacency-multilist representation
🖼️【此處有附圖，請對照原卷】
登入後即可作答並保存紀錄。
核心觀念
本題考查有向圖（digraph）的四種表示法。設有向圖為
其中：
- 為頂點集合。
- 為有向邊集合；若 ，表示存在一條由 指向 的邊。
- 鄰接矩陣記錄「是否有邊由列頂點指向行頂點」。
- 鄰接串列記錄每個頂點的所有出邊。
- 反向鄰接串列記錄每個頂點的所有入邊。
- 鄰接多重串列讓每條有向邊同時串接在其起點的出邊串列與終點的入邊串列中。
圖形資訊
目前附上的掃描圖只包含第 1～3 題，未出現第 5 題題目所稱的右側有向圖。因此缺少：
- 頂點名稱與數量。
- 每一條有向邊的方向。
- 是否存在平行邊或自我迴圈。
在未補充圖形前，無法唯一決定本題的具體矩陣與串列內容。以下以圖中實際頂點集合 與邊集合 表示正確作法。
解題方法
a. Adjacency-matrix
若採用「列表示起點、行表示終點」的慣例，鄰接矩陣 定義為：
因此矩陣第 列代表頂點 的所有出邊，第 欄代表指向頂點 的邊。
若圖中有：
則：
其餘位置依照圖上的邊逐一填入 或 。
若採用矩陣元素代表邊的數量，則有向多重圖中的 應填入由 到 的邊數，而非僅填入 或 。
b. Adjacency-list representation
鄰接串列以每個頂點為起點，列出所有由該頂點出發的終點：
表示方式為：
例如若圖中有：
則鄰接串列為：
沒有出邊的頂點，其串列指標為 NULL。
c. Inverse adjacency-list representation
反向鄰接串列記錄每個頂點的所有入邊：
也就是把每一條邊 的方向反向記錄為「 的前驅是 」。
以上述邊集合為例：
第 6 題20 分
- The pseudo program is shown in the following. (20%)
void program (item a[], item b[])
{
int n, i, j, temp;
n = a[0].valueC;
b[0].valueA = a[0].valueB;
b[0].valueB = a[0].valueA;
b[0].valueC = n;
if (n > 0) {
temp = 1;
for (i = 0; i < a[0].valueB; i++) {
for (j = 1; j <= n; j++) {
if (a[j].valueB == i) {
b[temp].valueA = a[j].valueB;
b[temp].valueB = a[j].valueA;
b[temp].valueC = a[j].valueC;
temp++;
}
}
}
}
}
#define MAX_TERMS 100
typedef struct {
int valueA;
int valueB;
int valueC;
} item;
item a [MAX_TERMS], b [MAX_TERMS];
a. What is the purpose of carrying out the above pseudo program? (10%)
b. Give the time complexity of the program in terms of big oh. (10%)
登入後即可作答並保存紀錄。
核心觀念
本題考「稀疏矩陣的三元組表示法」與「矩陣轉置」。
三元組陣列中，a[0] 儲存矩陣資訊：valueA 是列數、valueB 是行數、valueC 是非零元素個數；a[1] 到 a[n] 則各自記錄一個非零元素的列、行與值。
矩陣轉置會交換每個元素的列與行座標，元素值不變；矩陣的列數與行數也互換。
解題方法
令原矩陣有 列、 行、 個非零元素。程式先設定：
b[0].valueA = a[0].valueB：轉置後的列數為原矩陣行數 。b[0].valueB = a[0].valueA：轉置後的行數為原矩陣列數 。b[0].valueC = n：非零元素個數維持 。
接著，外層迴圈依原矩陣的行索引 i 由小到大掃描；內層迴圈逐一檢查所有非零元素。若某元素的原行座標 a[j].valueB 等於 i，便將它的列、行座標對調後寫入 b，並保留原值：