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

核心觀念

這題考的是窮舉法（exhaustive search）：列出所有符合限制的配置，計算各配置的總成績，再選出總成績最高者。

令 $d_i$ 表示分配給科目 $X_i$ 的準備天數。每科至少準備 1 天，總共只有 5 天，因此：

各科分數依準備天數查表，目標是最大化四科成績總和 $s$。

解題方法

先為四科各分配 1 天，共用掉 4 天；剩下 1 天可加給任一科。因此所有合法分配恰有以下 4 種：

核心觀念

本題考遞迴函數的基礎情況與遞迴關係式。程式中，當 $n=0$ 時回傳 $0$；當 $n>0$ 時，函數值由前一項 $f(n-1)$ 加上 $n^2$ 得到：

因此，計算 $f(n)$ 等同於把 $1^2$ 到 $n^2$ 逐項累加。

解題方法

（一）求 $f(3)$

依照遞迴式逐層代入，直到遇到基礎情況：

（二）求 $f(n)$，$\forall n\in\mathbb{N}$

由遞迴式反覆展開：

核心觀念

樹中每個節點的分支度，是該節點所擁有的子節點數。若分支度為 $i$ 的節點有 $i$ 個，則分支度為 $i$ 的節點共提供 $i\cdot i=i^2$ 條由父節點連向子節點的邊。

對任何非空樹，若總節點數為 $N$，則邊數為 $N-1$。因此，所有節點的分支度總和必須等於 $N-1$。

解題方法

令葉節點數為 $L(k)$。題目給定分支度為 $i$ 的節點有 $i$ 個，$i=1,2,\ldots,k$，所以非葉節點數為

加上葉節點後，總節點數為

另一方面，非葉節點所提供的邊數，也就是分支度總和，為

由樹的邊數等於總節點數減一，可得

移項整理：

核心觀念

本題考環狀串列的循環特性：節點依序相連，最後一個節點會再連回第一個節點。因此，若以串列表示密文並依指定步長循環移動，越過尾端時要從首端繼續計數。

解題方法

題目未說明環狀串列的起點、移動方向或步長；依密文與預期解碼方式，採用「每次向右移動一個字，從密文首字開始讀取」的設定。

將密文「明請到家玩天你我來」依序編號：

核心觀念

本題比較兩種背包問題：

• 0-1 背包：物件不可分割，每件只能整件放入或不放入，以 $x_i\in\{0,1\}$ 表示。
• 分數背包：物件可分割，可取其中一部分，以單位重量利益 $p_i/w_i$ 由高至低取用。

依貪婪策略，先計算各物件的利益重量比 $p_i/w_i$，再由高至低選取。

解題方法與計算

各物件的利益重量比為：

依利益重量比排序為 $C、A、B、E、D$。

（一）不可分割的 0-1 背包

背包限重為 $100$。依排序逐件檢查：

1. 放入 C：重量 $30$，利益 $66$，剩餘容量 $70$。
2. 放入 A：重量 $10$，利益 $20$，剩餘容量 $60$。
3. 放入 B：重量 $20$，利益 $30$，剩餘容量 $40$。
4. E 重量為 $50$，超過剩餘容量，略過。
5. 放入 D：重量 $40$，利益 $40$，剛好用滿容量。

因此選取 $A、B、C、D$，總重量為 $100$，總利益為：

$20+30+66+40=156$

對應的 $0-1$ 整數規劃為：