111 關務特考三等 資訊處理 資料結構 考古題詳解

核心觀念

本題考查漸近分析（asymptotic analysis）與 Big O notation。常用規則如下：

1. 常數倍不影響時間複雜度： $O(c f(n))=O(f(n)) \quad (c>0)$

2. 多項式和式由成長較快的項主導： $O(f(n)+g(n))=O(\max\{f(n),g(n)\})$

3. 指數函數的底數越大，成長越快： $3^n \gg 2^n$

4. 階乘函數成長速度快於固定底數的指數函數： $n! \gg 2^n$

因此，本題各小題只需比較同一和式中各項的成長速度，保留成長最快的主導項即可。

解題方法

（1）$2022n\ln n+111n^{1.001}$

先忽略常數係數 $2022$ 與 $111$，比較：

$n\ln n \quad \text{與} \quad n^{1.001}$

計算兩者比值：

$$\frac{n^{1.001}}{n\ln n} =\frac{n^{0.001}}{\ln n}$$

對於 $n$ 趨近無限大時，任何正次方 $n^{0.001}$ 的成長速度都快於 $\ln n$，因此：

$$n^{1.001} \gg n\ln n$$

所以主導項為 $111n^{1.001}$：

$$2022n\ln n+111n^{1.001}=\Theta(n^{1.001})$$

因此以 Big O notation 表示為：

$$\boxed{O(n^{1.001})}$$

（2）$2022n^3 2^n+111n^2 3^n$

忽略常數係數後，比較：

$n^3 2^n \quad \text{與} \quad n^2 3^n$

計算第二項與第一項的比值：

$$\frac{n^2 3^n}{n^3 2^n} =\frac{1}{n}\left(\frac{3}{2}\right)^n$$

由於 $\left(\frac{3}{2}\right)^n$ 的指數成長速度遠快於 $n$，故：

核心觀念

本題考查遞迴函數與線性遞迴關係的計算。已知初始值：

$$P(0)=P(1)=P(2)=1$$

以及遞迴公式：

$$P(n)=P(n-1)-2P(n-2)+P(n-3),\quad n\geq 3$$

計算每一項時，必須依序使用前三項數值。

解題方法

先依照 $n=3,4,5,\ldots$ 的順序逐項計算。

當 $n=3$：

$$\begin{aligned} P(3) &=P(2)-2P(1)+P(0)\\ &=1-2(1)+1\\ &=0 \end{aligned}$$

當 $n=4$：

$$\begin{aligned} P(4) &=P(3)-2P(2)+P(1)\\ &=0-2(1)+1\\ &=-1 \end{aligned}$$

因此，前 5 個值為：

$$P(0),P(1),P(2),P(3),P(4)=1,1,1,0,-1$$

所以第（1）題所填的兩個數字為：

$$\boxed{0,\ -1}$$

接著計算第（2）題所需的 $P(6)$ 與 $P(8)$。

當 $n=5$：

$$\begin{aligned} P(5) &=P(4)-2P(3)+P(2)\\ &=-1-2(0)+1\\ &=0 \end{aligned}$$

當 $n=6$：

核心觀念

本題考「單一機器工作排程問題」（Job Sequencing with Deadlines）。

每個工作具有：

• 利潤 $p_i$
• 最後期限 $d_i$
• 處理時間皆為 $1$ 個時間單位

若工作 $i$ 被安排在第 $t$ 個時段，必須滿足：

$$t \leq d_i$$

目標是在每個時段最多安排一個工作的前提下，使總利潤最大。

由於所有工作處理時間均為 $1$，可使用經典貪婪法：

1. 依利潤由大到小排列工作。
2. 依序處理每個工作。
3. 將工作安排在「不超過其最後期限的最晚空閒時段」。
4. 若期限內沒有空閒時段，則放棄該工作。

安排在最晚時段的原因，是要保留較前面的時段給期限較早的工作。

---

解題方法

各工作的資料如下：

工作	利潤	最後期限
3	60	2
7	55	3
5	45	2
1	40	2
4	20	3
2	15	4
6	10	1

依利潤由大到小的順序為：

$$3,\ 7,\ 5,\ 1,\ 4,\ 2,\ 6$$

最大最後期限為 $4$，因此可使用第 $1$ 至第 $4$ 個時間單位。

逐一安排

處理順序	工作	利潤	期限	安排結果
1	3	60	2	安排於時段 2
2	7	55	3	安排於時段 3
3	5	45	2	安排於時段 1
4	1	40	2	時段 1、2 均已滿，放棄
5	4	20	3	時段 1、2、3 均已滿，放棄
6	2	15	4	安排於時段 4
7	6	10	1	時段 1 已滿，放棄

因此各時段的最適排程為：

核心觀念

本題考查暴力比較法（exhaustive search）在不同比對方向下的字元比較次數。

文本：

$$X=\text{AGTCATTCGATTC}$$

樣式：

$$Y=\text{ATTC}$$

其中 $|X|=13$、$|Y|=4$，因此樣式共有

$$13-4+1=10$$

個可能的對齊位置。

• 樣式前向法（forward）：每一個對齊位置都由樣式左端開始，比較 $Y[1]、Y[2],\ldots$。
• 樣式後向法（backward）：每一個對齊位置都由樣式右端開始，比較 $Y[4]、Y[3],\ldots$。
• 比對一旦發生不相等即停止，若全部相等則完成該次比對。

---

解題方法一：樣式前向法（forward）

樣式 $Y=\text{ATTC}$，由左至右比較。

對齊起點	文本子字串	比較過程	比較次數
1	AGTC	A=A；G≠T	2
2	GTCA	G≠A	1
3	TCAT	T≠A	1
4	CATT	C≠A	1
5	ATTC	A=A；T=T；T=T；C=C	4
6	TTCG	T≠A	1
7	TCGA	T≠A	1
8	CGAT	C≠A	1
9	GATT	G≠A	1
10	ATTC	A=A；T=T；T=T；C=C	4

因此，前向法的總比較次數為

$$2+1+1+1+4+1+1+1+1+4=17$$

---

核心觀念

本題考查三維陣列在不同儲存順序下的「位址計算」。

陣列大小為：

• 第一維：$1\sim 8$，共 $8$ 個元素
• 第二維：$1\sim 9$，共 $9$ 個元素
• 第三維：$1\sim 4$，共 $4$ 個元素

每一個元素占用 $2$ 個儲存單元，因此相鄰元素的位址差為 $2$。

已知基準元素為 $A[1,2,1]$，其位址為 $234$。計算其他元素時，先求其相對於 $A[1,2,1]$ 的元素個數位移，再乘以 $2$。

---

（1）列序為主序（Row Major）

儲存規則

列序為主序表示最右側的下標變化最快，因此：

1. 第三維下標先連續變化；
2. 第三維走完後，第二維下標增加；
3. 第二維走完後，第一維下標增加。

對三維陣列 $A[i,j,k]$，相對於 $A[1,2,1]$ 的元素位移為：

$$(i-1)\times 9\times 4+(j-2)\times 4+(k-1)$$

其中：

• 第一維每增加 $1$，需跨過一整個 $9\times 4$ 的區塊；
• 第二維每增加 $1$，需跨過 $4$ 個元素；
• 第三維每增加 $1$，只移動 $1$ 個元素。

計算 $m=A[2,3,1]$ 的位址

元素位移為：

$$(2-1)\times 9\times 4+(3-2)\times 4+(1-1)$$ $$=36+4=40$$

換算成儲存單元位移：

$$40\times 2=80$$

因此：

$$m=234+80=\boxed{314}$$

計算 $n=A[2,3,4]$ 的位址

元素位移為：

$$(2-1)\times 9\times 4+(3-2)\times 4+(4-1)$$ $$=36+4+3=43$$

換算成儲存單元位移：

$$43\times 2=86$$

因此：

$$n=234+86=\boxed{320}$$

---

（2）行序為主序（Column Major）

儲存規則

行序為主序表示最左側的下標變化最快，因此：

1. 第一維下標先連續變化；
2. 第一維走完後，第二維下標增加；
3. 第二維走完後，第三維下標增加。

對三維陣列 $A[i,j,k]$，相對於 $A[1,2,1]$ 的元素位移為：