108 年 國立臺北大學資訊工程研究所《資料結構與演算法》

一、核心觀念

本題考查兩個主題：

1. C 語言中的「陣列、指標、指標的指標」宣告與記憶體結構。
2. 系統堆疊（system stack）的內容、後進先出特性，以及函式呼叫與返回的運作方式。

判讀宣告時，應先看變數名稱，再向外閱讀：

• list[5]：長度為 5 的陣列。
• *plist[5]：長度為 5 的陣列，每個元素是指標。
• **pplist[5]：長度為 5 的陣列，每個元素是指向指標的指標。

三者的共同點是：變數本身都是「含有 5 個元素的陣列」，差別在於每個元素的型別不同。

---

二、int list[5]、int *plist[5]、int **pplist[5] 的差別

1. int list[5]

宣告一個含有 5 個 int 元素的陣列：

$$\texttt{list} = [\texttt{int},\texttt{int},\texttt{int},\texttt{int},\texttt{int}]$$

記憶體概念如下：

list[0]   list[1]   list[2]   list[3]   list[4]
  int       int       int       int       int

存取方式：

list[i]       // 取得第 i 個 int 值
&list[i]      // 取得第 i 個元素的位址

若 int 佔 4 bytes，則：

sizeof(list) == 5 * sizeof(int)

在一般情況下為 20 bytes。

範例：

int list[5] = {10, 20, 30, 40, 50};
printf("%d", list[2]);   // 30

list[2] 的型別是 int。

---

2. int *plist[5]

宣告一個含有 5 個元素的陣列，且每個元素都是「指向 int 的指標」：

$$\texttt{plist} = [\texttt{int*},\texttt{int*},\texttt{int*},\texttt{int*},\texttt{int*}]$$

記憶體概念如下：

plist[0]   plist[1]   plist[2]   plist[3]   plist[4]
  int*        int*        int*        int*        int*
    |           |           |           |
    v           v           v
   int         int         int

每個 plist[i] 儲存的是某個 int 變數的位址，而不是整數值本身。

存取方式：

plist[i]       // 取得一個 int*
*plist[i]      // 取得該指標所指向的 int 值

範例：

int a = 10;
int b = 20;

int *plist[5] = {&a, &b, NULL, NULL, NULL};

printf("%d", *plist[0]);   // 10
printf("%d", *plist[1]);   // 20

plist[0] 的型別是 int *，*plist[0] 的型別才是 int。

此陣列可讓每個元素指向不同位置，因此不必要求所有資料連續配置。它常用於：

• 指標陣列
• 字串陣列
• 動態配置的資料集合
• 不規則二維陣列

例如：

int *rows[3];

rows[0] = malloc(2 * sizeof(int));
rows[1] = malloc(5 * sizeof(int));
rows[2] = malloc(3 * sizeof(int));

三列可以具有不同長度。

---

3. int **pplist[5]

宣告一個含有 5 個元素的陣列，且每個元素都是「指向 int * 的指標」：

$$\texttt{pplist} = [\texttt{int**},\texttt{int**},\texttt{int**},\texttt{int**},\texttt{int**}]$$

記憶體概念如下：

pplist[0]   pplist[1]   pplist[2]   pplist[3]   pplist[4]
  int**        int**        int**        int**        int**
    |
    v
   int*  ------> int

存取層次如下：

pplist[i]       // 型別為 int**
*pplist[i]      // 型別為 int*
**pplist[i]     // 型別為 int

範例：

int value = 30;
int *ptr = &value;
int **pplist[5] = {&ptr, NULL, NULL, NULL, NULL};

printf("%d", **pplist[0]);   // 30

其中：

pplist[0]  -> ptr  -> value
   int**      int*     int

int ** 常用於：

• 函式中修改呼叫端的指標
• 動態配置二維陣列
• 鏈結串列中修改頭指標
• 需要多一層間接存取的資料結構

例如，函式要修改外部的指標，必須傳入指標的位址：

void allocate(int **p) {
    *p = malloc(sizeof(int));
    **p = 100;
}

int *q = NULL;
allocate(&q);

呼叫後，q 指向一個值為 100 的 int。

---

4. 三者的比較

宣告	陣列元素型別	x[i] 的型別	*x[i] 的型別	**x[i] 的型別
int list[5]	int	int	不適用	不適用
int *plist[5]	int *	int *	int	不適用
int **pplist[5]	int **	int **	int *	int

最重要的差別如下：

• list 的每個元素直接儲存整數。
• plist 的每個元素儲存一個 int 的位址。
• pplist 的每個元素儲存一個 int * 的位址。

三者不能混淆為：

int *p[5];       // 5 個 int 指標的陣列
int (*p)[5];     // 指向「含 5 個 int 的陣列」的指標

括號的位置會改變宣告意義。

---

三、系統堆疊的內容和運作原理

1. 系統堆疊的定義

核心觀念

本題考查二元運算式樹與樹的三種走訪方式：

• Inorder（中序）：左子樹 → 根節點 → 右子樹
• Preorder（前序）：根節點 → 左子樹 → 右子樹
• Postorder（後序）：左子樹 → 右子樹 → 根節點
• Level order（層序）：由上而下、由左而右逐層走訪

運算式中的優先順序為：

$$*、/ \;>\; +$$

同一層級的運算子採由左至右結合，因此原式為：

$$A*B+C/D+E*F=((A*B)+(C/D))+(E*F)$$

解題方法

依照運算優先順序建立運算式樹：

             +
           /   \
          +     *
        /  \   / \
       *    / E   F
      / \  / \
     A  B C  D

其中：

• 左下子樹代表 $A*B$
• 中間子樹代表 $C/D$
• 最上層左側的 $+$ 代表 $(A*B)+(C/D)$
• 最上層右側的 $*$ 代表 $E*F$
• 根節點的 $+$ 代表完整運算式

1. Preorder

規則為「根 → 左 → 右」：

$$+\rightarrow +\rightarrow *\rightarrow A\rightarrow B\rightarrow /\rightarrow C\rightarrow D\rightarrow *\rightarrow E\rightarrow F$$

因此：

核心觀念

本題考查迷宮問題中的「深度優先搜尋（DFS）」與「回溯法（Backtracking）」。

將迷宮表示成二維陣列：

• 0：可通行
• 1：牆壁
• S：起點
• E：終點

老鼠每次可向上、下、左、右移動一格。演算法必須處理兩件事：

1. 沿著可行路徑移動，直到抵達終點。
2. 遇到沒有任何可走方向的死路時，退回上一個路口，改走其他方向。

每個位置可視為圖中的一個頂點，相鄰可通行位置之間有一條邊，因此迷宮求路等同於在圖中尋找從起點 $S$ 到終點 $E$ 的路徑。

---

解題方法：深度優先搜尋加回溯

從起點開始，依序嘗試四個方向：

1. 檢查相鄰位置是否在迷宮範圍內。
2. 檢查該位置是否為可通行位置。
3. 檢查該位置是否尚未拜訪。
4. 若符合條件，將老鼠移動到該位置，並繼續搜尋。
5. 若所有方向都無法前進，表示目前位置是死路，取消此位置在解答路徑中的標記，回到上一格。

這種「前進到底，失敗後退回」的方式就是回溯。

遞迴版本

Maze(x, y):
    若 (x, y) 是終點：
        將 (x, y) 標記為路徑
        回傳成功

    若 (x, y) 超出迷宮範圍：
        回傳失敗

    若 (x, y) 是牆壁：
        回傳失敗

    若 (x, y) 已拜訪：
        回傳失敗

    將 (x, y) 標記為已拜訪
    將 (x, y) 標記為目前路徑

    依序嘗試四個方向：
        若 Maze(下一格) 成功：
            回傳成功

    將 (x, y) 從目前路徑中移除
    回傳失敗

四個方向可設定為：

$$(\Delta x,\Delta y)\in\{(-1,0),(1,0),(0,-1),(0,1)\}$$

分別代表上、下、左、右。

---

a. 移動到終點

假設老鼠目前位於 $(x,y)$，演算法逐步尋找相鄰的可通行位置。

當遞迴搜尋抵達終點 $(x_E,y_E)$ 時：

$$(x,y)=(x_E,y_E)$$

立即回傳成功。遞迴函式層層回傳後，起點到終點之間被保留的格子即為一條完整路徑。

例如搜尋路徑為：

$$S\rightarrow A\rightarrow B\rightarrow C\rightarrow E$$

抵達 $E$ 後，所有呼叫依序回傳成功，最終得到：

$$S\rightarrow A\rightarrow B\rightarrow C\rightarrow E$$

若只要求找出一條路徑，找到終點後即可停止，不必繼續搜尋其他路徑。

---

b. 解決死路

若目前位置的四個方向均無法前進，表示該位置為死路。此時必須執行回溯：

1. 將目前位置從路徑中移除。
2. 回到上一個位置。
3. 在上一個位置嘗試尚未探索的其他方向。

假設搜尋形成：

$$S\rightarrow A\rightarrow B\rightarrow C$$

而 $C$ 的四個方向都不可走，則：

$$C\text{ 為死路}$$

移除 $C$ 後回到 $B$：

$$S\rightarrow A\rightarrow B$$

核心觀念

本題考查以 linked list 實作 stack，以及 C 語言中「指向指標的指標」Node **top 的使用方式。

Stack 遵守後進先出（Last In, First Out, LIFO）：

• push：將新節點放到 stack 頂端。
• pop：移除 stack 頂端節點，取出其資料。
• linked list 的頂端由 *top 指向。
• 因為 push 與 pop 都需要修改頂端指標，所以函式參數使用 Node **top。

解題方法

push：將新節點插入頂端

新節點加入 stack 頂端時，必須依序完成：

1. 將新值存入 new_node->value。
2. 讓新節點指向原本的頂端：new_node->next = *top。
3. 更新 stack 頂端，使 *top 指向新節點。

關鍵程式碼如下：

void push (Node **top, int new_value) { // assume top is not null
    Node *new_node = (Node *) malloc (sizeof (Node));
    // Your answer starts here

    new_node->value = new_value;
    new_node->next = *top;
    *top = new_node;
}

插入前：

top → A → B → NULL

插入新節點 N 後：

top → N → A → B → NULL

因此，新節點必須先連接原本的 linked list，再將 top 改指向新節點。

pop：移除頂端節點

移除頂端節點時，必須完成：

1. 讀出頂端節點的資料。
2. 將 *top 往下一個節點移動。
3. 釋放原本的頂端節點。
4. 回傳取出的值。

關鍵程式碼如下：

int pop (Node **top) { // assume top is not null
    int value;
    Node *deleting_node = *top;
    // Your answer starts here

    value = deleting_node->value;
    *top = deleting_node->next;

    free(deleting_node);
    return value;
}

移除前：

top → A → B → NULL

執行：

value = deleting_node->value;
*top = deleting_node->next;

移除後：

top → B → NULL

最後釋放節點 A 所占用的記憶體。

完整答案

核心觀念

Breadth-First Search（BFS，廣度優先搜尋）從起點 $a$ 出發，依照「距離起點的層數」逐層拜訪頂點：

• 第 $0$ 層：$a$
• 第 $1$ 層：與 $a$ 相鄰且尚未拜訪的頂點
• 第 $2$ 層：由第 $1$ 層頂點發現的未拜訪頂點
• 依此類推

BFS tree 中，每個頂點（起點除外）都與「第一次發現它的頂點」連接，形成一棵以 $a$ 為根的樹。

解題方法

使用佇列（queue）執行 BFS：

1. 將 $a$ 標記為已拜訪並放入佇列。
2. 取出佇列前端頂點，依圖上的鄰接關係檢查其鄰點。
3. 每發現一個尚未拜訪的頂點，就：
   • 標記為已拜訪；
   • 將該頂點與目前頂點連成 BFS tree 的樹邊；
   • 將該頂點加入佇列。
4. 持續至佇列為空。

若某頂點可由多條路徑抵達，只採用最先被發現的那條邊。

圖形資訊判定

核心觀念

題目要求計算三階線性遞迴：

$$F_n=2F_{n-1}+F_{n-2}+F_{n-3}\qquad(n\ge 3)$$

若直接使用遞迴，會重複計算大量相同子問題，時間複雜度為指數級。若使用動態規劃，雖可降為 $O(n)$，但仍未達到題目要求的 $O(\lg n)$。

本題應使用：

• 矩陣表示線性遞迴
• 矩陣快速冪（Repeated Squaring）

矩陣快速冪可在 $O(\lg n)$ 次矩陣乘法內計算 $A^k$。

---

解題方法：矩陣快速冪

將連續三項組成狀態向量：

$$\begin{bmatrix} F_n\\ F_{n-1}\\ F_{n-2} \end{bmatrix}$$

根據遞迴式：

$$F_{n+1}=2F_n+F_{n-1}+F_{n-2}$$

因此有：

$$\begin{bmatrix} F_{n+1}\\ F_n\\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 2&1&1\\ 1&0&0\\ 0&1&0 \end{bmatrix} \begin{bmatrix} F_n\\ F_{n-1}\\ F_{n-2} \end{bmatrix}$$

令轉移矩陣為：

$$A= \begin{bmatrix} 2&1&1\\ 1&0&0\\ 0&1&0 \end{bmatrix}$$

初始狀態為：

$$\begin{bmatrix} F_2\\ F_1\\ F_0 \end{bmatrix} = \begin{bmatrix} 1\\ 1\\ 0 \end{bmatrix}$$

因此對於 $n\ge 2$：

$$\begin{bmatrix} F_n\\ F_{n-1}\\ F_{n-2} \end{bmatrix} = A^{n-2} \begin{bmatrix} 1\\ 1\\ 0 \end{bmatrix}$$

計算出右側向量後，第一個分量就是 $F_n$。

---

矩陣快速冪

利用以下公式：

$$A^k= \begin{cases} I,&k=0\\ A^{k/2}A^{k/2},&k\text{ 為偶數}\\ A\cdot A^{k-1},&k\text{ 為奇數} \end{cases}$$

其中 $I$ 為單位矩陣。

實作時採用二進位快速冪：

1. 初始令 $R=I$、$B=A$。
2. 若目前指數 $k$ 為奇數，令 $R\leftarrow R B$。
3. 令 $B\leftarrow B B$。
4. 將 $k$ 整除以 $2$。
5. 重複直到 $k=0$。

每次迭代都將指數減半，因此只需 $O(\lg k)=O(\lg n)$ 次迭代。

---

關鍵程式碼

以下為虛擬碼：

核心觀念

本題考查：

• 排序後的雙指標（two pointers）技巧。
• 排序的時間複雜度：$O(n\log n)$。
• 利用陣列單調性，在不遺漏答案的情況下縮小搜尋範圍。

先將集合 $S$ 排序為：

$$a_1 \leq a_2 \leq \cdots \leq a_n$$

使用左、右兩個指標，分別指向目前區間的最小值與最大值。令：

$$\text{sum}=a_L+a_R$$

根據 $\text{sum}$ 與 $x$ 的大小關係移動指標。

解題方法

步驟一：排序

將 $n$ 個整數排序，得到：

$$a_1 \leq a_2 \leq \cdots \leq a_n$$

排序時間為：

$$O(n\log n)$$

步驟二：設定雙指標

設定：

$$L=1,\qquad R=n$$

此時 $a_L$ 是目前範圍中的最小元素，$a_R$ 是目前範圍中的最大元素。

重複執行以下步驟，直到 $L\geq R$：

1. 計算 $a_L+a_R$。

2. 若

   $$a_L+a_R=x$$

   則找到符合條件的兩個不同元素，回傳「存在」。

3. 若

   $$a_L+a_R<x$$

   由於 $a_R$ 已是目前範圍內最大值，固定 $a_L$ 時，任何其他配對的和都不會大於 $a_L+a_R$。因此 $a_L$ 不可能與目前範圍內任何元素組成 $x$，將 $L$ 向右移動。

4. 若

   $$a_L+a_R>x$$

   由於 $a_L$ 已是目前範圍內最小值，固定 $a_R$ 時，任何其他配對的和都不會小於 $a_L+a_R$。因此 $a_R$ 不可能與目前範圍內任何元素組成 $x$，將 $R$ 向左移動。

關鍵程式碼

TwoSum(S, x):
    sort(S)

    L = 1
    R = n

    while L < R:
        sum = S[L] + S[R]

        if sum == x:
            return true
        else if sum < x:
            L = L + 1
        else:
            R = R - 1

    return false

其中 $L<R$ 確保使用的是兩個不同的位置。即使集合中存在相同數值，只要它們是不同元素，仍可由不同索引表示。

正確性說明

維持以下搜尋不變量：

核心觀念

插入排序法（Insertion Sort）將陣列分為「已排序區」與「未排序區」，每回合取未排序區的第一個元素作為插入鍵值（Key），由後向前與已排序區元素比較後插入適當位置。

---

執行步驟

初始陣列：$(7, 6, 5, 4, 2, 3, 1)$

1. Pass 1 ($\text{Key} = 6$)：將 $6$ 插入已排序區 $(7)$
   • 結果：$(6, 7, 5, 4, 2, 3, 1)$
2. Pass 2 ($\text{Key} = 5$)：將 $5$ 插入已排序區 $(6, 7)$
   • 結果：$(5, 6, 7, 4, 2, 3, 1)$
3. Pass 3 ($\text{Key} = 4$)：將 $4$ 插入已排序區 $(5, 6, 7)$
   • 結果：$(4, 5, 6, 7, 2, 3, 1)$
4. Pass 4 ($\text{Key} = 2$)：將 $2$ 插入已排序區 $(4, 5, 6, 7)$