113 年 國立高雄大學資訊工程學系碩士班《離散數學與資料結構》

核心觀念

陣列元素採用「從 $0$ 開始編號」：

$x[0],x[1],x[2],x[3],x[4],\ldots$

因此，第五個元素是 $x[4]$。

陣列名稱在運算式中通常會退化為指向第一個元素的指標，因此：

$x+4 \equiv \&x[4]$

其中：

• $\&x[4]$：取得第五個元素的位址。
• $x[4]$：取得第五個元素的值。
• $*(x+4)$：取得第五個元素的值。
• 若 $ptr$ 指向 $x[0]$，則 $ptr+4$ 是第五個元素的位址，而 $*(ptr+4)$ 是第五個元素的值。

解題方法

題目要求的是「第五個元素的地址」。

由於陣列索引從 $0$ 開始，第五個元素為：

$x[4]$

取得該元素的地址需使用取址運算子 $\&$：

$\&x[4]$

此外，陣列指標運算也可表示為：

$x+4=\&x[4]$

所以正確表達式是：

$\boxed{\&x[4]}$

選項分析

(a) *(ptr+4)

若 $ptr$ 指向陣列第一個元素 $x[0]$，則：

$ptr+4=\&x[4]$

核心觀念

此題考察單向 linked list 的指標走訪。若節點結構為：

$$\text{node} \rightarrow (\text{node}).\text{link}$$

其中 link 指向下一個節點，z 則是目前所在節點的指標。

解題方法

第一行：

z ← (*z).link

將 z 更新為目前節點的下一個節點，因此指標向後移動一次。

第二行：

z ← (*z).link

再從目前節點向後移動一次。

設原本：

$$z = N_0$$

則執行過程為：

$$N_0 \xrightarrow{\text{第一次}} N_1 \xrightarrow{\text{第二次}} N_2$$

核心觀念

本題考查陣列的交集（intersection）與雜湊表（hash table）查找。

給定陣列：

• $x$ 的大小為 $m$
• $y$ 的大小為 $n$

目標是找出同時出現在 $x$ 與 $y$ 中的元素。若陣列可能含有重複值，通常將「common elements」視為集合交集，因此每個共同元素只輸出一次。

雜湊表平均可在 $O(1)$ 時間內完成查找，因此適合用來加速元素是否存在的判斷。

解題方法

先將較小的陣列存入雜湊集合，再掃描另一個陣列。

演算法步驟

1. 將陣列 $x$ 的所有元素放入雜湊集合 $H$。
2. 建立空集合 $R$，用來儲存共同元素。
3. 逐一掃描陣列 $y$：
   • 若 $y[j]$ 存在於 $H$ 中，代表它同時出現在 $x$ 與 $y$。
   • 將 $y[j]$ 加入 $R$。
4. 輸出 $R$。

其中 $R$ 使用集合結構，可避免同一共同元素因為在 $y$ 中重複出現而被輸出多次。

虛擬碼

CommonElements(x, y):
    H ← empty hash set
    R ← empty hash set

    for each element a in x:
        insert a into H

    for each element b in y:
        if b is in H:
            insert b into R

    return R

為降低額外空間，實作時可先選擇較小的陣列建立雜湊集合：

CommonElements(x, y):
    if m > n:
        swap(x, y)

    H ← elements of x
    R ← empty hash set

    for each element b in y:
        if b is in H:
            insert b into R

    return R

正確性說明

對於任意輸出的元素 $a$：

• $a$ 被放入 $R$ 的條件是 $a$ 存在於 $H$ 中；
• $H$ 包含陣列 $x$ 的所有元素；
• $a$ 同時來自陣列 $y$ 的掃描結果。

因此：

$$a \in x \land a \in y$$

所以每個輸出元素必然是共同元素。

另一方面，若 $a$ 同時存在於 $x$ 與 $y$：

• 因為 $a \in x$，所以 $a$ 已被放入 $H$；
• 因為 $a \in y$，掃描到 $a$ 時會在 $H$ 中查找成功；
• 因此 $a$ 會被加入 $R$。

核心觀念

本題考查圖論中的「社交網路表示法」與邊的查詢。

將每一個人視為一個頂點（vertex），將兩人之間的直接友誼視為一條邊（edge）。由於朋友關係通常具有對稱性，若 $A$ 是 $B$ 的朋友，則 $B$ 也是 $A$ 的朋友，因此此社交網路可表示為無向圖：

$$G=(V,E)$$

其中：

• $|V|=100000$
• $|E|=1000000$

題目要判斷的是：圖中是否存在直接連接頂點 $A$ 與頂點 $B$ 的邊。

---

解題方法

採用「雜湊表搭配鄰接串列」表示圖。

對每一個人 $u$，建立一個集合 friends[u]，存放所有與 $u$ 有直接友誼的人。

若 $A$ 與 $B$ 是朋友，則加入：

$$B \in friends[A]$$

由於友誼是雙向的，也必須同時加入：

$$A \in friends[B]$$

建立資料結構的流程如下：

1. 建立 $100000$ 個空的雜湊集合。
2. 逐一讀取每條友誼邊 $(u,v)$。
3. 將 $v$ 加入 friends[u]。
4. 將 $u$ 加入 friends[v]。

查詢 $A$ 與 $B$ 是否為直接朋友時，只需檢查：

$$B \in friends[A]$$

---

關鍵程式碼

#include <unordered_set>
#include <vector>

using namespace std;

const int N = 100000;

vector<unordered_set<int>> friends(N);

void addFriendship(int A, int B) {
    friends[A].insert(B);
    friends[B].insert(A);
}

bool areFriends(int A, int B) {
    return friends[A].find(B) != friends[A].end();
}

areFriends(A, B) 使用雜湊表查詢，因此平均時間複雜度為：

$$O(1)$$

---

複雜度分析

建立資料結構

共有 $1000000$ 條友誼，每條邊加入兩次，因此平均建立時間為：

$$O(|E|)=O(1000000)$$

查詢時間

使用雜湊集合查詢：

$$O(1)$$

這是平均複雜度；在雜湊碰撞嚴重時，最壞情況可能退化，但實務上可透過良好雜湊函數與適當容量配置維持常數時間。

空間複雜度

每條無向邊在兩個鄰接集合中各儲存一次，因此總儲存量為：

$$O(|V|+|E|)$$

本題約需儲存 $100000$ 個頂點及 $2000000$ 個鄰接項目，遠小於鄰接矩陣所需的空間。

(a) 建立二元搜尋樹（Binary Search Tree, BST）

依序插入資料：D, B, X, I, C, J, L, A, Z，規則為較小值放左子樹，較大值放右子樹：

1. 插入 D：作為根節點 $D$。
2. 插入 B：$B < D$，插入至 $D$ 的左子節點。
3. 插入 X：$X > D$，插入至 $D$ 的右子節點。
4. 插入 I：$I > D$ 且 $I < X$，插入至 $X$ 的左子節點。
5. 插入 C：$C < D$ 且 $C > B$，插入至 $B$ 的右子節點。
6. 插入 J：$J > D$、$J < X$ 且 $J > I$，插入至 $I$ 的右子節點。
7. 插入 L：$L > D$、$L < X$、$L > I$ 且 $L > J$，插入至 $J$ 的右子節點。
8. 插入 A：$A < D$ 且 $A < B$，插入至 $B$ 的左子節點。
9. 插入 Z：$Z > D$ 且 $Z > X$，插入至 $X$ 的右子節點。

---

(b) 建立 AVL 樹（AVL Tree）

AVL 樹要求每個節點的平衡因子（$\text{BF} = \text{左子樹高度} - \text{右子樹高度}$）滿足 $\text{BF} \in \{-1, 0, 1\}$。

1. 插入 D, B, X：樹結構平衡。

     D
    / \
   B   X
   

2. 插入 I：

   • 節點 $D$ 之 $\text{BF} = 1 - 2 = -2$，發生 RL 型不平衡。
   • 對 $D$ 執行 RL 旋轉（先對 $X$ 右旋，再對 $D$ 左旋）。

       I
      / \
     D   X
    /
   B
   

核心觀念

本題考查巢狀迴圈的執行次數，以及以下計數方法：

• 嚴格遞增索引的組合計數
• 獨立條件的乘法原理
• 容斥原理
• 三角形數公式

若索引滿足

$$1\leq x_1<x_2<\cdots<x_r\leq 10,$$

其可能組合數為

$$\binom{10}{r}.$$

---

（a）

程式中的條件為：

$$1\leq m<k<j<i\leq 10.$$

每執行一次 n := n + 1，就相當於從 $1$ 到 $10$ 中選出四個數，並依序指定為

$$m<k<j<i.$$

因此執行次數為

$$\binom{10}{4} =\frac{10\cdot 9\cdot 8\cdot 7}{4\cdot3\cdot2\cdot1} =210.$$

因此：

$$\boxed{n=210}$$

時間複雜度為 $O(10^4)$；若上限改為一般的 $N$，則為 $O(N^4)$。空間複雜度為 $O(1)$。

---

（b）

此處的索引關係為：

$$1\leq k<j<i\leq 10.$$

每次累加相當於從 $1$ 到 $10$ 中選出三個數，並依序排列成

$$k<j<i.$$

因此執行次數為

$$\binom{10}{3} =\frac{10\cdot9\cdot8}{3\cdot2\cdot1} =120.$$

因此：

$$\boxed{n=120}$$

也可直接逐層計算：

$$\sum_{i=1}^{10}\sum_{j=1}^{i-1}(j-1) = \sum_{i=1}^{10}\binom{i-1}{2} = \binom{10}{3} =120.$$

時間複雜度為 $O(10^3)$；一般上限為 $N$ 時，時間複雜度為 $O(N^3)$。空間複雜度為 $O(1)$。

---

（c）

四個變數各自從 $1$ 到 $10$：

$$1\leq i,j,k,m\leq 10.$$

條件為：

$$i\neq j\quad\text{且}\quad k\neq m.$$

先計算 $i,j$ 的選法：

• $i$ 有 $10$ 種選法；
• $j$ 必須不同於 $i$，因此有 $9$ 種選法。

所以：

$$10\cdot9=90.$$

同理，$k,m$ 的選法為：

$$10\cdot9=90.$$

兩組變數彼此獨立，因此總執行次數為：

$$90\cdot90 =(10\cdot9)^2 =8100.$$

因此：

$$\boxed{n=8100}$$

時間複雜度為 $O(10^4)$；一般上限為 $N$ 時，為 $O(N^4)$。空間複雜度為 $O(1)$。

---

（d）

迴圈範圍為：

$$1\leq m\leq k\leq j\leq i\leq 10.$$

累加條件為三個事件的聯集：

$$A:\ i=2j, \qquad B:\ j=2k, \qquad C:\ k=2m.$$

因此使用容斥原理：

$$|A\cup B\cup C| = |A|+|B|+|C| -|A\cap B|-|A\cap C|-|B\cap C| +|A\cap B\cap C|.$$

計算 $|A|$

由 $i=2j$ 且 $i\leq10$，可知 $j=1,2,3,4,5$。

固定 $j$ 後，$(k,m)$ 滿足

$$1\leq m\leq k\leq j,$$

共有

$$\frac{j(j+1)}{2}$$

種。

因此：

$$|A| = \sum_{j=1}^{5}\frac{j(j+1)}{2} = 1+3+6+10+15 =35.$$

計算 $|B|$