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

核心觀念

本題考查「分組計數」與「是否考慮群組標籤」：

• 人員彼此不同。
• 每組恰有 $2$ 人。
• (a) 群組標記為 $A,B,C,D,E$，因此不同群組的排列會形成不同結果。
• (b) 群組沒有標記，因此只要配對方式相同，即視為同一種分組。

常用公式為多項式係數：

$$\frac{10!}{2!2!2!2!2!} = \frac{10!}{(2!)^5}.$$

解題方法

(a) 群組有標記

依序分配各組人員：

1. 從 $10$ 人中選 $2$ 人給 $A$ 組：

   $$\binom{10}{2}$$

2. 從剩下的 $8$ 人中選 $2$ 人給 $B$ 組：

   $$\binom{8}{2}$$

3. 從剩下的 $6$ 人中選 $2$ 人給 $C$ 組：

   $$\binom{6}{2}$$

4. 從剩下的 $4$ 人中選 $2$ 人給 $D$ 組：

   $$\binom{4}{2}$$

5. 剩下的 $2$ 人自動分配給 $E$ 組。

因此總數為

$$\binom{10}{2} \binom{8}{2} \binom{6}{2} \binom{4}{2} \binom{2}{2}.$$

整理成階乘形式：

$$\frac{10!}{2!8!} \cdot \frac{8!}{2!6!} \cdot \frac{6!}{2!4!} \cdot \frac{4!}{2!2!} \cdot \frac{2!}{2!0!} = \frac{10!}{(2!)^5}.$$

計算得

核心觀念

本題考查數學歸納法，用來證明命題

$$P(n):\quad \sum_{i=1}^{n} i(i!)=(n+1)!-1$$

對所有 $n\ge 1$ 都成立。

數學歸納法分為兩個部分：

1. 基礎步驟：證明命題在起始值 $n=1$ 成立。
2. 歸納步驟：假設命題在 $n=k$ 成立，再證明命題在 $n=k+1$ 也成立。

其中階乘的基本公式為

$$(k+2)!=(k+2)(k+1)!.$$

解題方法

令

$$P(n):\quad \sum_{i=1}^{n} i(i!)=(n+1)!-1.$$

採用數學歸納法證明。

一、基礎步驟

當 $n=1$ 時，左側為

$$\sum_{i=1}^{1}i(i!)=1(1!)=1.$$

右側為

$$(1+1)!-1=2!-1=2-1=1.$$

因此

$$\sum_{i=1}^{1}i(i!)=(1+1)!-1,$$

故 $P(1)$ 成立。

二、歸納假設

假設當 $n=k$ 時命題成立，即

$$\sum_{i=1}^{k}i(i!)=(k+1)!-1.$$

此式稱為歸納假設。

三、歸納步驟

證明當 $n=k+1$ 時，命題也成立。由左側開始：

核心觀念

本題考查第二類 Stirling 數 $S(m,n)$ 的定義與遞迴關係：

• $S(m,n)$ 表示將 $m$ 個相異物件分成 $n$ 個非空且不可區分群組的方法數。
• 公式為
  $S(m,n)=\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^m.$
• 當 $m=n$ 時，每個群組恰好包含一個物件，因此 $S(n,n)=n!$。
• 遞迴式
  $S(m+1,n)=S(m,n-1)+nS(m,n)$
  可由觀察第 $m+1$ 個物件所在的群組推得。

---

（a）證明

由題意，$S(n,n)$ 是將 $n$ 個相異物件分配到 $n$ 個相同容器，且每個容器皆非空的方法數。

因為物件數與容器數相同，又要求每個容器非空，所以每個容器恰好放入一個物件。此時分配方式等同於將 $n$ 個物件排列到 $n$ 個位置，共有

$S(n,n)=n!$

種。

另一方面，將 $m=n$ 代入第二類 Stirling 數的公式：

$$S(n,n)=\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^n.$$

結合 $S(n,n)=n!$，得到

$$\boxed{ n!=\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^n }$$

其中 $0^n=0$，因此 $k=0$ 的項對正整數 $n$ 沒有影響。

另一種觀點：容斥原理

也可以先把 $n$ 個相異物件分配到 $n$ 個有標號容器。總方法數為

$n^n.$

扣除至少一個容器空出的情形：

• 指定 $n-k$ 個容器為空，有 $\binom{n}{n-k}=\binom{n}{k}$ 種選法；
• 剩下 $k$ 個容器可接受每個物件，因此有 $k^n$ 種分配方式；
• 依容斥原理，符號為 $(-1)^{n-k}$。

所以非空分配數為

核心觀念

本題考查「雙射配對」與「容斥原理」。

將每位男性配給一位女性，且每位女性只能被配對一次，等同於求一個排列：

$$\pi:\{1,2,3,4,5\}\to\{1,2,3,4,5\},$$

其中 $\pi(i)=j$ 表示 $M_i$ 配對到 $W_j$。

若題目指定某些配對不得出現，可將這些配對視為「禁配位置」，使用容斥原理扣除違規排列。

---

（a）$M_i$ 不得配對到 $W_i$

共有 $5!$ 種不限制的配對方式。

令事件 $A_i$ 表示「$M_i$ 配對到 $W_i$」。要求的是所有 $A_i$ 都不發生，因此由容斥原理：

$$N = \sum_{k=0}^{5}(-1)^k\binom{5}{k}(5-k)!.$$

各項計算如下：

$$\begin{aligned} N &=5!-\binom51 4!+\binom52 3! -\binom53 2!+\binom54 1!-\binom55 0!\\ &=120-5(24)+10(6)-10(2)+5(1)-1\\ &=120-120+60-20+5-1\\ &=44. \end{aligned}$$

這也就是 $5$ 個元素的錯排數，記為 $!5$。

---

（b）具有多個禁配位置

禁配位置如下表：

男性	不可配對的女性
$M_1$	$W_1,W_4$
$M_2$	$W_2,W_5$
$M_3$	$W_1,W_4$
$M_4$	$W_2,W_3,W_5$
$M_5$	$W_2,W_5$

這類題目可使用「棋盤容斥法」。令 $r_k$ 表示從所有禁配位置中選出 $k$ 個、且不在同一列或同一欄的方式數。則合法配對數為

$$N=\sum_{k=0}^{5}(-1)^k r_k(5-k)!.$$

這裡的 $r_k$ 稱為禁配棋盤的 $k$-車放置數。

---

計算禁配位置的 $r_k$

將 $M_1,M_3$ 視為第一組，將 $M_2,M_5$ 視為第二組：

• 第一組的禁配欄為 $W_1,W_4$；
• 第二組的禁配欄為 $W_2,W_5$；
• $M_4$ 的禁配欄為 $W_2,W_3,W_5$。

先不選取 $M_4$

對 $M_1,M_3$ 而言，最多可放兩個禁配位置，其放置數為：

$$1,\quad 4,\quad 2.$$

原因是：

• 放 $0$ 個：$1$ 種；
• 放 $1$ 個：$2$ 位男性乘 $2$ 個欄，共 $4$ 種；
• 放 $2$ 個：兩位男性必須分別放在 $W_1,W_4$，有 $2! =2$ 種。

$M_2,M_5$ 具有相同結構，因此也是 $1,4,2$。

核心觀念

本題考查：

• 普通生成函數：用 $x^k$ 表示選取 $k$ 顆球。
• 乘法原理：不同顏色的選取方式彼此獨立，因此生成函數相乘。
• 係數擷取：$[x^{10}]f(x)$ 表示總共選取 $10$ 顆球的方法數。
• 奇偶條件：白球數量為偶數，黑球數量為奇數。

令紅、綠、白、黑球分別選取 $r,g,w,b$ 顆，則需滿足

$$r+g+w+b=10,$$

其中

$$0\le r,g,w,b\le 10,\qquad w\text{ 為偶數},\qquad b\text{ 為奇數}.$$

---

（a）生成函數的建立

紅球與綠球

紅球可以選取 $0,1,2,\ldots,10$ 顆，因此紅球的生成函數為

$$1+x+x^2+\cdots+x^{10}.$$

綠球同理，其生成函數也是

$$1+x+x^2+\cdots+x^{10}.$$

兩種顏色彼此獨立，所以合併後為

$$(1+x+x^2+\cdots+x^{10})^2.$$

白球

白球必須選取偶數顆，可選數量為

$$0,2,4,6,8,10.$$

因此白球的生成函數為

$$1+x^2+x^4+x^6+x^8+x^{10}.$$

黑球

黑球必須選取奇數顆，可選數量為

$$1,3,5,7,9.$$

因為總共只選 $10$ 顆，不可能選取 $11$ 顆黑球，因此生成函數為

$$x+x^3+x^5+x^7+x^9.$$

合併

根據乘法原理，四種顏色的生成函數相乘，得到

$$f(x) = (1+x+x^2+\cdots+x^{10})^2 (1+x^2+x^4+\cdots+x^{10}) (x+x^3+x^5+\cdots+x^9).$$

其中 $x^{r+g+w+b}$ 的係數，代表選取總數為 $r+g+w+b$ 的方法數。因此所求方法數為

$$[x^{10}]f(x).$$

---

核心觀念

本題考查後置式（postfix expression，又稱逆波蘭表示法）的運算規則。

後置式不使用括號，運算子會放在運算元之後。從左至右掃描：

• 遇到運算元：推入堆疊。
• 遇到運算子：取出堆疊頂端的兩個運算元，先取出者為右運算元，後取出者為左運算元，計算後再將結果推回堆疊。

題目中的變數值為：

$$W=10,\quad X=5,\quad Y=5,\quad Z=3$$

解題方法

後置式為：

$$\text{WX/YZ-+X*}$$

依序處理如下：

讀入符號	操作	堆疊內容
$W$	推入 $10$	$10$
$X$	推入 $5$	$10,5$
$/$	$10\div 5=2$	$2$
$Y$	推入 $5$	$2,5$
$Z$	推入 $3$	$2,5,3$
$-$	$5-3=2$	$2,2$
$+$	$2+2=4$	$4$
$X$	推入 $5$	$4,5$
$*$	$4\times5=20$	$20$

因此，此後置式等價於：

核心觀念

陣列元素採用 從 0 開始的索引：

• 第 1 個元素：z[0]
• 第 6 個元素：z[5]

陣列名稱 z 在運算式中通常會轉換成指向第 1 個元素的指標，因此：

$$z[i] \equiv *(z+i)$$

而取得變數位址的運算子為 &，所以第 6 個元素的位址為：

$$\&z[5]$$

若 zPtr 指向陣列的第 1 個元素，則第 6 個元素的位址也可寫成：

$$zPtr+5$$

解題方法

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

第六個元素的索引為：

$$6-1=5$$

因此第六個元素是 z[5]。要取得它的地址，必須在前面加上位址運算子 &：

$$\&z[5]$$

因此正確選項為 (d)。

選項分析

(a) *(zPtr+5)

zPtr+5 指向第六個元素，* 會取出該位址所存放的元素值。

因此此式代表：

$$*(zPtr+5)=z[5]$$

核心觀念

最小生成樹（MST）是在連通、無向加權圖中，選出連接所有頂點且不形成環的邊，使總成本最小。若圖有 $n$ 個頂點，生成樹恰有 $n-1$ 條邊。

本題有 $8$ 個頂點，因此生成樹要選 $7$ 條邊。可用 Kruskal 演算法：依邊權重由小到大檢查，若加入該邊不會形成環，就保留。

解題方法

圖中的邊依權重由小到大排列如下：

$$(1,2):1,\quad (7,8):2,\quad (3,4):4,\quad (5,6):6,\quad (2,3):7,\quad (1,3):8,\quad (2,4):9,\quad (3,5):10,\quad (3,6):12,\quad (5,7):14$$

依序選邊：

• 選 $(1,2)$，成本 $1$。
• 選 $(7,8)$，成本 $2$。
• 選 $(3,4)$，成本 $4$。
• 選 $(5,6)$，成本 $6$。
• 選 $(2,3)$，成本 $7$，連接頂點群 $\{1,2\}$ 與 $\{3,4\}$。
• $(1,3)$ 會形成環，略過；

觀念與字典序比較

1. 單詞序列（按句子出現順序）：
   "The", "quick", "brown", "foxes", "jump", "over", "the", "lazy", "dogs"
2. 比較規則：
   依據 ASCII 碼大小進行比較，大寫字母之 ASCII 碼小於小寫字母（如提示："The" 比所有小寫開頭單字小）。
   字典序由小至大排序為：
   $\text{"The"} < \text{"brown"} < \text{"dogs"} < \text{"foxes"} < \text{"jump"} < \text{"lazy"} < \text{"over"} < \text{"quick"} < \text{"the"}$

---

(a) 原始未平衡二元搜尋樹（Unbalanced BST）

依單詞出現順序依次插入：

1. 插入 "The"：作為根節點（Root）。
2. 插入 "quick"：大於 "The" $\rightarrow$ 置於 "The" 之右子樹。
3. 插入 "brown"：小於 "quick" $\rightarrow$ 置於 "quick" 之左子樹。
4. 插入 "foxes"：大於 "brown" $\rightarrow$ 置於 "brown" 之右子樹。
5. 插入 "jump"：大於 "foxes" $\rightarrow$ 置於 "foxes" 之右子樹。
6. 插入 "over"：大於 "jump" $\rightarrow$ 置於 "jump" 之右子樹。
7. 插入 "the"：大於 "quick" $\rightarrow$ 置於 "quick" 之右子樹。
8. 插入 "lazy"：小於 "over" $\rightarrow$ 置於 "over" 之左子樹。
9. 插入 "dogs"：小於 "foxes" $\rightarrow$ 置於 "foxes" 之左子樹。

---

(b) AVL 樹建構過程（AVL Tree）

核心觀念

多項式可表示為若干個非零項的集合：

$$A(x)=7x^{12}-5x^4+6$$

每一項包含兩項資訊：

• 係數（coefficient）
• 指數（exponent）

使用單向鏈結串列（singly linked list）時，每個節點可定義為：

$$\text{Node}=(\text{coefficient},\text{exponent},\text{next})$$

其中 next 指向下一個節點。通常依指數由大到小排列，且省略係數為 $0$ 的項，以節省空間。

---

解題方法

將多項式逐項拆開：

$$7x^{12},\qquad -5x^4,\qquad 6$$

常數項 $6$ 可視為：

$$6x^0$$

因此各節點內容為：

節點	係數	指數
第 1 個	$7$	$12$
第 2 個	$-5$	$4$
第 3 個	$6$	$0$

依指數遞減順序串接：

$$(7,12)\longrightarrow(-5,4)\longrightarrow(6,0)\longrightarrow\text{NULL}$$

可畫成：

head
  |
  v
+--------+--------+-------+    +--------+--------+-------+    +--------+--------+-------+
| coeff  | exp    | next  | -> | coeff  | exp    | next  | -> | coeff  | exp    | next  | -> NULL
|   7    |  12    |       |    |  -5    |   4    |       |    |   6    |   0    |       |
+--------+--------+-------+    +--------+--------+-------+    +--------+--------+-------+

---

關鍵程式碼

以下以類似 C 語言的結構表示：

核心觀念

本題考查搜尋引擎中的「倒排索引（inverted index）」與雜湊表（hash table）。

一般資料儲存方式是：

$$\text{網頁} \rightarrow \text{該網頁包含的單字}$$

倒排索引則反過來建立：

$$\text{單字} \rightarrow \text{包含該單字的網頁集合}$$

例如題目中的資料可建立：

單字	包含該單字的網頁
Mary	Webpage 1
Andy	Webpage 1、2、3
quicker	Webpage 1、3
basketball	Webpage 2
Mike	Webpage 3

因此，查詢某個單字是否出現在任一網頁，只要查詢該單字在索引中是否存在即可。

題目共有約 $100000$ 個不同單字，因此以「單字」作為索引鍵最重要；網頁總數雖然極大，但不必在每次查詢時逐一掃描所有網頁。

---

（a）既有一十億個網頁的索引

解題方法：倒排索引搭配雜湊表

建立一個雜湊表：

$$H[\text{word}] = \text{包含此單字的網頁編號集合}$$

例如：

$$H[\text{Andy}] = \{1,2,3\}$$

建立索引時，逐一讀取每個網頁中的單字。對於網頁編號 $p$ 與單字 $w$：

1. 計算單字 $w$ 的雜湊值。
2. 若 $w$ 尚未出現在雜湊表，建立新項目。
3. 將網頁編號 $p$ 加入 $w$ 的 posting list。

其中 posting list 是「包含該單字的網頁編號列表」。

查詢單字 $x$ 時：

• 若 $x \in H$，表示至少有一個網頁包含 $x$。
• 若 $x \notin H$，表示目前索引中的網頁皆不包含 $x$。

時間複雜度

令：

• $V=100000$：不同單字數量；
• $T$：所有網頁中的單字總出現次數；
• $k$：包含查詢單字的網頁數量。

由於每個網頁約有 $100$ 個單字，因此：

$$T \approx 10^9 \times 100 = 10^{11}$$

建立索引

每個單字平均進行一次雜湊查詢，因此建立時間為：

$$O(T)$$

若同一網頁中的同一單字重複出現，需先在該網頁內去重，避免同一網頁編號重複加入 posting list。

查詢單字是否存在

雜湊表的平均查詢時間為：

$$O(1)$$

若查詢結果還需要列出所有相關網頁，則需加上輸出成本：

$$O(1+k)$$

因為取得索引項目平均為 $O(1)$，但列出 $k$ 個網頁本身至少需要 $O(k)$。

雜湊表在碰撞嚴重時，最壞查詢時間可能為：

$$O(V)$$

實務上透過良好雜湊函數與適當負載因子，平均時間仍視為 $O(1)$。

空間複雜度

雜湊表的單字部分需要：

$$O(V)$$

所有 posting list 的總長度等於「單字—網頁」關聯數。設不同的單字—網頁配對數為 $E$，則索引空間為：

$$O(V+E)$$

若只需要判斷某單字是否曾出現，不需要知道它出現在哪些網頁，則可將資料結構簡化為：

$$H[\text{word}] = \text{true}$$

此時只需 $O(V)$ 的額外空間，但搜尋引擎通常仍會保存 posting list，因為後續還需要找出符合條件的網頁。

---

（b）每日新增網頁的索引

解題方法：建立動態增量索引

新網頁會持續加入，因此不宜每天重新掃描一十億個舊網頁並重建完整索引。適合使用另一個動態雜湊表，稱為增量索引（delta index）：

$$H_{\text{new}}[\text{word}] = \text{新增網頁中包含該單字的網頁集合}$$

舊索引與新增索引分開維護：

核心觀念

本題考查：

• 已排序陣列的合併式掃描（two-pointer technique）。
• 利用元素的大小關係排除不可能成為共同元素的資料。
• 時間複雜度與空間複雜度分析。

設陣列 $A$ 有 $m$ 個元素，陣列 $B$ 有 $n$ 個元素，且兩者皆以非遞減順序排列。

若目前比較的元素為 $A[i]$ 與 $B[j]$：

• 若 $A[i] = B[j]$，此元素就是共同元素。
• 若 $A[i] < B[j]$，因為 $A$ 已排序，$A[i]$ 不可能再與 $B[j]$ 或其後元素相等，因此應向右移動 $i$。
• 若 $A[i] > B[j]$，同理應向右移動 $j$。

---

解題方法：雙指標同步掃描

使用兩個指標：

• $i$ 指向陣列 $A$ 的目前元素。
• $j$ 指向陣列 $B$ 的目前元素。

初始時：

$$i=0,\qquad j=0$$

依照下列規則掃描：

1. 若 $A[i]=B[j]$，將此元素加入共同元素集合，並將 $i,j$ 同時加 $1$。
2. 若 $A[i]<B[j]$，將 $i$ 加 $1$。
3. 若 $A[i]>B[j]$，將 $j$ 加 $1$。
4. 當 $i=m$ 或 $j=n$ 時停止。

演算法虛擬碼

FindCommonElements(A, B):
    i ← 0
    j ← 0
    result ← empty list

    while i < length(A) and j < length(B):
        if A[i] == B[j]:
            append A[i] to result
            i ← i + 1
            j ← j + 1

        else if A[i] < B[j]:
            i ← i + 1

        else:
            j ← j + 1

    return result

套用題目資料

陣列開頭的比較如下：

• $A[0]=3$、$B[0]=2$，因為 $3>2$，移動 $B$ 的指標。
• $A[0]=3$、$B[1]=3$，兩者相等，找到共同元素 $3$。
• 後續掃描到 $A=280$、$B=280$，找到共同元素 $280$。
• 末端掃描到 $A=100985$、$B=100985$，找到共同元素 $100985$。

因此，題目明確列出的共同元素為：

$$3,\quad 280,\quad 100985$$

省略號所代表的其他資料也必須依照相同演算法逐一比較，因此完整共同元素須以實際陣列內容為準。

---

正確性說明