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

核心觀念

本題考查：

• 乘法原理與排列：$P(n,r)$
• 組合：$\binom{n}{r}$
• 重複組合：$\binom{n+r-1}{r}$
• 補集原理
• 容斥概念與分類計數

車牌允許以 $0$ 開頭，因此六位數字的總數為

$$10^6=1,000,000.$$

---

(a) 六個數字皆相異

六個位置依序選取不同數字：

• 第 1 位：$10$ 種
• 第 2 位：$9$ 種
• 第 3 位：$8$ 種
• 第 4 位：$7$ 種
• 第 5 位：$6$ 種
• 第 6 位：$5$ 種

因此

$$10\times 9\times 8\times 7\times 6\times 5 =P(10,6) =151,200.$$

---

(b) 六個數字嚴格遞增

條件為

$$x_1<x_2<x_3<x_4<x_5<x_6.$$

先從 $0$ 至 $9$ 的十個數字中選出六個，再按照遞增順序排列。選定數字後，排列方式唯一，因此

$$\binom{10}{6}=210.$$

---

(c) 六個數字非遞減

條件為

$$x_1\le x_2\le x_3\le x_4\le x_5\le x_6.$$

此時數字可以重複。問題等同於從 $10$ 種數字中選取 $6$ 個，允許重複且不計順序，使用重複組合公式：

$$\binom{10+6-1}{6} =\binom{15}{6} =5,005.$$

---

(d) 至少出現一次數字 $2$

使用補集原理。

全部車牌數：

$$10^6.$$

完全不出現數字 $2$ 時，每個位置有 $9$ 種選擇，因此共有

$$9^6.$$

所以至少出現一次數字 $2$ 的車牌數為

$$10^6-9^6 =1,000,000-531,441 =468,559.$$

---

(e) 至少出現一個數字 $0,1,2$

先計算完全不出現 $0,1,2$ 的車牌。每個位置只能使用

$$3,4,5,6,7,8,9$$

共 $7$ 種數字，因此有

$$7^6$$

張車牌。

核心觀念

本題考查「雙重計數法」：對同一個集合，用兩種不同方式計算其元素個數。

右式

$$\binom{n+2}{3}$$

表示從集合

$$\{1,2,\ldots,n+2\}$$

中選出三個相異元素的方式數。選出的三個數必可唯一排列為

$$a<b<c.$$

固定中間數 $b$ 後：

• 比 $b$ 小的數有 $b-1$ 個，可選作 $a$；
• 比 $b$ 大的數有 $n+2-b$ 個，可選作 $c$。

因此固定 $b$ 時共有

$$(b-1)(n+2-b)$$

組三元素集合。

---

解題方法：以中間數分類

考慮集合

$$S=\{1,2,\ldots,n+2\}$$

中所有三個相異元素的子集合。

直接選取三個元素，總數為

$$|S|=\binom{n+2}{3}.$$

接著按照三元素中的中間數 $b$ 分類。

由於必須有一個數小於 $b$、一個數大於 $b$，所以

$$b=2,3,\ldots,n+1.$$

當中間數固定為 $b$ 時：

$$a\in\{1,2,\ldots,b-1\},$$

共有 $b-1$ 種選法；而

$$c\in\{b+1,b+2,\ldots,n+2\},$$

共有 $n+2-b$ 種選法。因此此類別共有

$$(b-1)(n+2-b)$$

種。

將所有可能的中間數加總：

$$\sum_{b=2}^{n+1}(b-1)(n+2-b) = \binom{n+2}{3}.$$

令

$$k=b-1,$$

則當 $b=2$ 時 $k=1$，當 $b=n+1$ 時 $k=n$，且

$$n+2-b=n+1-k.$$

所以

$$\sum_{b=2}^{n+1}(b-1)(n+2-b) = \sum_{k=1}^{n}k(n+1-k).$$

展開即得

核心觀念

本題考查資料結構的用途，以及如何表示「語法成分與其內容」之間的對應關係。

句子可拆解為：

• 主詞（subject）：Mary、John
• 動詞（verb）：is
• 程度修飾語（modifier）：much、slightly
• 形容詞（adjective）：quicker
• 比較結構（comparison）：than John、than Mary

這些資料具有明確的「欄位名稱 → 對應內容」關係，例如：

$$\text{subject} \rightarrow \text{Mary}$$ $$\text{modifier} \rightarrow \text{much}$$ $$\text{adjective} \rightarrow \text{quicker}$$

最適合此種「依照鍵值快速尋找資料」需求的資料結構是 Dictionary（字典、映射表）。

---

解題方法

判斷資料結構時，先觀察資料的主要操作方式。

本題不是要求按照先進後出順序處理資料，也不是要求按照先進先出順序排隊，更不是單純處理節點的線性串接，而是要將不同語法角色對應到各自的內容。因此可使用下列形式表示：

{
  subject: "Mary",
  verb: "is",
  modifier: "much",
  adjective: "quicker",
  comparison: "than John"
}

第二句則可表示為：

{
  subject: "John",
  verb: "is",
  modifier: "slightly",
  adjective: "quicker",
  comparison: "than Mary"
}

其中：

• subject、verb、modifier 等是鍵（key）。
• Mary、is、much 等是值（value）。
• 可透過鍵直接取得指定的語法成分。

因此，Dictionary 最能符合題目所說的「儲存並分析語法組成」。

---

選項分析

(a) Stack

Stack 採用後進先出（Last In, First Out, LIFO）原則，主要操作包括：

• push：將資料放入堆疊頂端。
• pop：取出最上方資料。

Stack 適合處理函式呼叫、括號匹配、深度優先搜尋及復原操作等具有「最近加入的資料先處理」特性的問題。

核心觀念

本題考查雜湊表（hash table）在「開放定址法」（open addressing）中的碰撞處理，以及 double hashing 對叢集問題（clustering）的改善效果。

當兩個鍵值經由雜湊函數得到相同位置時，就會發生碰撞。開放定址法不使用鏈結串列，而是在表格內尋找其他空位。常見探測方法包括：

• 線性探測（linear probing）
• 二次探測（quadratic probing）
• 雙重雜湊（double hashing）

雙重雜湊通常使用下列探測公式：

$$h(k,i)=\bigl(h_1(k)+i\cdot h_2(k)\bigr)\bmod m$$

其中：

• $k$：待插入或搜尋的鍵值
• $h_1(k)$：第一次雜湊所得到的起始位置
• $h_2(k)$：決定探測步長的第二個雜湊函數
• $i=0,1,2,\ldots$：第 $i$ 次探測
• $m$：雜湊表大小

與線性探測固定以相同步長逐格尋找不同，雙重雜湊會依照鍵值產生不同的探測步長，因此不同鍵值即使發生碰撞，也較不容易走過相同的探測路徑。

---

解題方法

判斷各選項是否為 double hashing 的主要優點即可。

線性探測的探測位置通常為：

$$h(k,i)=\bigl(h(k)+i\bigr)\bmod m$$

當連續位置逐漸被占用時，容易形成一長段連續的已使用區域，稱為主要叢集（primary clustering）。後續發生碰撞的鍵值容易加入同一區域，使叢集越來越大，降低搜尋效率。

雙重雜湊使用第二個雜湊函數決定步長：

$$h(k,i)=\bigl(h_1(k)+i\cdot h_2(k)\bigr)\bmod m$$

不同鍵值通常會得到不同的 $h_2(k)$，探測序列因此較分散，可有效降低開放定址法中的 clustering 問題。

必須注意，雙重雜湊主要是「降低」叢集，不是保證完全消除所有碰撞，也不會保證所有操作在任何情況下都是 $O(1)$。

---

選項分析

(a) It allows for dynamic resizing of the hash table.

觀念說明

求解二元樹從根節點至葉節點的最大路徑和（Maximum Root-to-Leaf Path Sum），最佳策略為使用動態規劃（Dynamic Programming）配合自底向上（Bottom-up，即後序遍歷 Post-order Traversal）。

定義 $dp(u)$ 為以節點 $u$ 為根之子樹中，從 $u$ 到葉節點的最大路徑總和，狀態轉移方程為：
$dp(u) = \text{val}(u) + \max\big(dp(\text{left}), dp(\text{right})\big)$

核心觀念

本題考查三個重點：

1. 使用適當的資料結構，依唯一識別碼快速取得向量。
2. 利用 cosine similarity 衡量兩個向量的方向相似程度。
3. 分析逐一比較所有向量時的時間複雜度。

設資料庫中的第 $i$ 個向量為

$$\mathbf{v}_i=(v_{i1},v_{i2},\ldots,v_{id}),\qquad d=128$$

查詢向量為

$$\mathbf{q}=(q_1,q_2,\ldots,q_d)$$

兩向量的 cosine similarity 定義為

$$\operatorname{sim}(\mathbf{q},\mathbf{v}_i) = \frac{\mathbf{q}\cdot\mathbf{v}_i} {\|\mathbf{q}\|\,\|\mathbf{v}_i\|}$$

其中內積與向量長度分別為

$$\mathbf{q}\cdot\mathbf{v}_i = \sum_{j=1}^{d}q_jv_{ij}$$

以及

$$\|\mathbf{q}\| = \sqrt{\sum_{j=1}^{d}q_j^2}, \qquad \|\mathbf{v}_i\| = \sqrt{\sum_{j=1}^{d}v_{ij}^2}$$

cosine similarity 越大，表示兩向量方向越接近；若向量皆為非零向量，其值介於 $-1$ 與 $1$ 之間。

---

解題方法

（a）向量儲存資料結構

可使用「雜湊表搭配向量陣列」：

$$\text{HashTable}[\text{vectorID}] \longrightarrow \text{向量所在位置或向量內容}$$

例如：

HashTable
    "V0001" → vectors[0]
    "V0002" → vectors[1]
    "V0003" → vectors[2]

其中：

• vectorID 是每個向量的唯一識別碼。
• vectors 可使用連續陣列儲存所有 $N=10,000$ 個 $128$ 維向量。
• 雜湊表負責由識別碼快速找到向量位置。
• 向量本身可使用浮點數陣列儲存，例如 float[128]。

若雜湊函數分布良好，依照唯一識別碼查詢的平均時間複雜度為

$$O(1)$$

因此，此設計同時具備：

• 依 ID 快速存取；
• 向量資料排列集中，便於連續掃描；
• 可預先儲存向量長度，避免每次搜尋重複計算。

每個向量可額外儲存其平方長度：

$$\|\mathbf{v}_i\|^2=\sum_{j=1}^{128}v_{ij}^2$$

搜尋時再取平方根，或直接利用正規化向量進行比較。

---

（b）使用 cosine similarity 搜尋最相似向量

採用精確線性搜尋：對資料庫中的每個向量計算 cosine similarity，保留相似度最大的向量。

步驟一：計算查詢向量長度

$$\|\mathbf{q}\| = \sqrt{\sum_{j=1}^{128}q_j^2}$$

若 $\mathbf{q}$ 為零向量，則 cosine similarity 無定義，必須先拒絕該查詢或另行指定處理規則。本題假設查詢向量不是零向量。

步驟二：逐一計算相似度

對每個資料庫向量 $\mathbf{v}_i$：

1. 計算內積：

   $$\mathbf{q}\cdot\mathbf{v}_i = \sum_{j=1}^{128}q_jv_{ij}$$

2. 計算或讀取 $\|\mathbf{v}_i\|$。

3. 計算：

   $$s_i= \frac{\mathbf{q}\cdot\mathbf{v}_i} {\|\mathbf{q}\|\,\|\mathbf{v}_i\|}$$

4. 若 $s_i$ 大於目前最大相似度，更新最佳答案。

伪程式如下：

(a) 程式碼錯誤與潛在問題分析

1. 無法處理重複次數大於等於 10 的字元（邏輯缺陷）：
   程式中使用 output[j++] = count + '0'; 將計數寫入輸出陣列。該寫法僅適用於單數位計數（$1 \le count \le 9$）。若連續字元重複次數 $count \ge 10$，如 $count = 10$ 時，$10 + '0'$ 會得到 ASCII 碼的 ':' 而非字串 "10"，導致編碼結果錯誤。
2. 缺乏輸出緩衝區邊界檢查（安全隱患）：
   encode 函式未傳入 output 陣列的容量限制，若編碼後的字串長度超過 output 分配空間（本例為 50 bytes），會引發緩衝區溢位（Buffer Overflow）。

---

(b) 修正後的執行結果

修正多位數計數問題（如改用 sprintf 寫入數字）後，對輸入字串 "aaabbccccdaa" 進行游程統計：

• 'a' 重複 3 次 $\rightarrow$ "a3"
• 'b' 重複 2 次 $\rightarrow$ "b2"
• 'c' 重複 4 次 $\rightarrow$ "c4"