112 年 國立成功大學工程科學系碩士班丙組《計算機數學》

這題考驗對質數定義的理解。

一個質數（prime number）的定義是：一個大於 1 的自然數，除了 1 和它本身以外不再有其他因數。
因此，任何一個質數都恰好有兩個因數：1 和它本身。

這題考驗對質數與合數定義的理解，特別是數字 1 的特殊性。

根據數論的定義：

• 質數（Prime Number）：一個大於 1 的自然數，除了 1 和它本身以外不再有其他因數。

這題考驗對質數性質的理解，以及質數加法的結果。

我們來分析不同情況：

1. 兩個質數都是奇質數：

   • 所有質數（除了 2 以外）都是奇數。
   • 兩個奇數相加，結果一定是偶數。
   • 例如：3 + 5 = 8 (偶數，合數)，7 + 11 = 18 (偶數，合數)。
   • 由於題目要求是「兩個不同的質數」，如果它們都不是 2，那麼它們都是奇數。兩個奇數相加必為偶數。大於 2 的偶數都是合數。

2. 其中一個質數是 2：

   • 如果我們取質數 2 和另一個不同的質數（例如 3），它們的和是 2 + 3 = 5。5 是一個質數。

核心觀念

本題考查等差級數求和。數列

$$2,4,6,\ldots,4m$$

為首項 $a_1=2$、公差 $d=2$ 的等差數列。

末項 $4m$ 可寫成 $2(2m)$，因此共有 $2m$ 項。

等差級數和公式為

$$S_n=\frac{n(a_1+a_n)}{2}.$$

解題方法

代入 $n=2m$、$a_1=2$、$a_n=4m$：

$$S_{2m} =\frac{2m(2+4m)}{2} =m(4m+2) =4m^2+2m.$$

因此，

$$2+4+6+\cdots+4m=4m^2+2m.$$

選項分析

(a) $m^2+3$

此式與正確結果

$$4m^2+2m$$

不相等。例如 $m=3$ 時，原級數為

$$2+4+6+8+10+12=42,$$

而 $m^2+3=12$，故錯誤。

(b) $m+1$

核心觀念

二元樹的前序走訪（preorder traversal）順序為「根節點、左子樹、右子樹」，可記為：

$$\text{Root} \rightarrow \text{Left} \rightarrow \text{Right}$$

因此，走訪的第一步是拜訪根節點；接著走訪左子樹。

解題方法

依前序走訪的定義排列步驟：

1. 拜訪根節點。
2. 走訪左子樹。
3. 走訪右子樹。

所以第二步是走訪左子樹，對應選項 (B)。

選項分析

核心觀念

本題考二元樹的典型應用。霍夫曼編碼（Huffman coding）利用二元樹建立可變長度的前綴碼：每個符號放在葉節點，從根走到葉節點的路徑可轉成該符號的二進位碼。

解題方法

依原卷圖，第 6 題詢問二元樹的重要應用，選項依序為 Huffman coding、stack implementation、queue implementation、traverse a cyclic graph。判斷各項是否直接以二元樹作為主要結構或用途；霍夫曼編碼正是以二元樹表示符號的編碼方式。

霍夫曼樹通常依符號出現頻率建構：每次取出頻率最低的兩個節點合併成父節點，重複直到形成一棵樹。頻率高的符號通常得到較短的碼，且任一符號的碼都不會是另一符號碼的前綴。

選項分析

核心觀念

使用「補集計數」：先計算符合總範圍的數量，再扣除完全不含數字 $7$ 的數量。三位數的百位數不能為 $0$，十位與個位則可為 $0$。

解題方法

介於 $99$ 與 $1000$ 之間的整數為 $100$ 到 $999$，共有

$$999-100+1=900$$

個。

先計算完全不含 $7$ 的三位數：

核心觀念

這題考的是組合。從 $n$ 個不同的人中選出 $r$ 個，若不考慮選取順序，選法數為

$$\binom{n}{r}=\frac{n!}{r!(n-r)!}$$

「至少一位男生」可用補集原理計算：先算所有選法，再扣掉完全沒有男生的選法。

解題方法

先不限制性別，從 $10$ 位學生中選出 $4$ 位，共有

$$\binom{10}{4} = \frac{10!}{4!6!} = 210$$

核心觀念

此題考布林代數的分配律與吸收律。符號 $+$ 表示 OR（或），相乘表示 AND（且），並使用下列定律：

• 分配律：$(a+b)(c+d)=ac+ad+bc+bd$
• 冪等律：$xx=x$
• 吸收律：$x+xy=x$

解題方法

先將兩個括號展開，再利用吸收律化簡：

核心觀念

本題使用樹的兩個基本性質：

1. 握手定理：圖中所有頂點的度數總和，等於邊數的兩倍。
2. 樹的邊數公式：若樹有 $n$ 個頂點，則邊數為 $n-1$。

因此，樹的頂點度數總和為

$$2(n-1)$$

解題方法

設度數為 $1$ 的頂點有 $x$ 個。題目給定的度數為 $2、3、4、5$ 的頂點共有 $31$ 個，因此樹的頂點總數為

$$n=31+x$$

依握手定理，所有頂點的度數總和為

$$10(2)+10(3)+10(4)+1(5)+x =20+30+40+5+x =95+x$$

核心觀念

每個位置都從 $\{0,1,2\}$ 中等機率選出，因此一個 20 位數序列共有 $3^{20}$ 種，且每種序列的機率相同。

令 $X$ 為序列中 $1$ 的個數，則 $X\sim\operatorname{Binomial}(20,\frac13)$。題目要求 $X$ 為偶數的機率。

解題方法

直接依照 $1$ 的個數計數：若恰有 $k$ 個 $1$，先選出這 $k$ 個位置，有 $\binom{20}{k}$ 種；其餘 $20-k$ 個位置各可填 $0$ 或 $2$，有 $2^{20-k}$ 種。因此，$1$ 的個數為偶數的序列總數為

$$\sum_{\substack{k=0\\k\text{ 為偶數}}}^{20} \binom{20}{k}2^{20-k}.$$

利用二項式定理的偶次項公式

$$\sum_{\substack{k=0\\k\text{ 為偶數}}}^{n} \binom{n}{k}a^{n-k}b^k = \frac{(a+b)^n+(a-b)^n}{2},$$

核心觀念

每個位置都從 $\{0,1,2\}$ 中等機率選出一個數字，因此共有 $3^{20}$ 種等可能序列。題目要求「$1$ 的個數為偶數」且「$2$ 的個數為偶數」。

可用奇偶指示式計數：對任意整數 $k$，

$$\mathbf{1}_{k\text{ 為偶數}}=\frac{1+(-1)^k}{2}.$$

因此，同時符合兩個偶數條件的指示式為

$$\frac{1+(-1)^{N_1}}{2}\cdot \frac{1+(-1)^{N_2}}{2},$$

其中 $N_1,N_2$ 分別表示序列中 $1$ 與 $2$ 的個數。

解題方法

展開指示式後，符合條件的序列數為

$$\frac{1}{4}\sum_{\text{所有序列}} \left(1+(-1)^{N_1}+(-1)^{N_2}+(-1)^{N_1+N_2}\right).$$

逐項計算：

• 常數項對所有 $3^{20}$ 種序列的總和為 $3^{20}$。

核心觀念

這題考的是同餘運算與冪次的循環性。計算 $43^{86}$ 除以 $5$ 的餘數時，可以先將底數化成模 $5$ 的同餘類，再利用冪次循環簡化計算。

解題方法

因為 $43=5\cdot 8+3$，所以

$$43\equiv 3\pmod 5.$$

因此

$$43^{86}\equiv 3^{86}\pmod 5.$$

計算 $3$ 的前幾次冪模 $5$ 的結果：

核心觀念

本題考查費馬小定理：若 $p$ 為質數，且 $p\nmid a$，則

$$a^{p-1}\equiv 1\pmod p.$$

題目中模數 $97$ 是質數，且 $97\nmid 75$，因此可用費馬小定理化簡 $75$ 的高次冪。

解題方法

取 $p=97$、$a=75$，費馬小定理給出

$$75^{96}\equiv 1\pmod{97}.$$

由於指數 $384=4\times 96$，所以