109 年國立陽明交通大學資訊工程學系碩士班《資料結構與演算法》考古題與詳解

Question 1

$r$ may have degree in $T$. (A) 1 (B) 2 (C) 3 (D) 4 (E) 5

Accepted Answer

核心觀念 連通圖有 $6$ 個節點，因此任何 DFS 樹都含 $6-1=5$ 條樹邊。原圖有 $8$ 條邊，所以有 $$ 8-5=3 $$ 條非樹邊。 在無向圖的 DFS 中，每條非樹邊都連接某個節點與它的祖先；不同 DFS 子樹之間不會有非樹邊。題目又給出 $r$ 在原圖中的度數為 $5$，因此 $r$ 與其餘五個節點都相鄰。 解題方法 設 $r$ 在 DFS 樹中的度數為 $d$，也就是 $r$ 的子節點數。 $r$ 連到五個其他節點，其中 $d$ 條邊是 DFS 樹邊，另外 $5-d$ 條是非樹邊。由於全圖只有 $3$ 條非樹邊，必須有 $$ 5-d \le 3 $$ 所以 $d\ge 2$，選項 (A) 的 $1$ 不可能。 再檢查 $d=4$ 與 $d=5$： - 若 $d=4$，五個非根節點分在四棵以 $r$ 的子節點為根的子樹中，只有一棵子樹能多出一個節點，其餘三棵都是單一節點。根的子樹之間不能有非樹邊；唯一含兩個節點的子樹中，兩節點間的邊已是樹邊。因此，除了連到 $r$ 的非樹邊以外，沒有其他非樹邊可用。但要湊足全圖的三條非樹邊，還需要兩條，故不可能。 - 若 $d=5$，五個非根節點全是 $r$ 的直接子節點，各子樹都是單一節點，子樹間不能有非樹邊。可是全圖仍有三條非樹邊，故不可能。 因此只有 $d=2$ 或 $d=3$ 可行。以下給出兩種情形的例子，確認它們確實能形成 DFS 樹：

Question 2

A node is an articulation point if and only if removing it (and the edges through it) disconnects $G$. Is $r$ always an articulation point in $G$ for any possible $G$? (A) Yes (B) Not necessary

Accepted Answer

核心觀念

割點是指移除該頂點及其相連邊後，圖的連通分量數增加。對無向圖的 DFS 樹而言，根節點是割點的條件是：它在 DFS 樹中至少有兩個子節點。

解題方法

根節點 $r$ 在原圖中的度數為 $5$ ，因此它連接其餘全部 $5$ 個節點。移除 $r$ 及其相連的 $5$ 條邊後，剩下 $5$ 個節點與

8-5=3

條邊。

要讓 $5$ 個節點保持連通，至少需要 $5-1=4$ 條邊。因此，移除 $r$ 後的圖不可能連通，必定分成至少兩個連通分量。原圖 $G$ 是連通的，所以這些分量原先只能透過 $r$ 相連；移除 $r$ 會使 $G$ 斷開，故 $r$ 必為割點。

Question 3

For $k=2$, the best known algorithm has time complexity . (A) $O(n)$ (B) $O(n^2)$ (C) $O(n^2\log n)$ (D) $O(n^3)$ (E) superpolynomial time

Accepted Answer

核心觀念 $2$-著色等價於判斷圖是否為二分圖：能把頂點分成兩群，使每條邊的兩端分屬不同群。可用 BFS 或 DFS 嘗試交替染色；若遇到相鄰頂點已被染成相同顏色，圖就不是二分圖。 解題方法 對每個尚未拜訪的頂點啟動 BFS 或 DFS，因為圖可能不連通。將起點染成一色，並把每個鄰點染成相反色；若檢查到同色相鄰點，便判定無法完成 $2$-著色。 若圖以鄰接串列表示，演算法時間為 $O(n+m)$，其中 $m$ 是邊數。題目只用 $n$ 個頂點表示複雜度；簡單無向圖最多有 $$ m \leq \frac{n(n-1)}{2}=O(n^2) $$ 因此最壞情況的時間複雜度是 $O(n^2)$。 選項分析

Question 4

For $k=3$, the best known algorithm has time complexity . (A) $O(n)$ (B) $O(n^2)$ (C) $O(n^2\log n)$ (D) $O(n^3)$ (E) superpolynomial time

Accepted Answer

核心觀念 本題考查圖著色問題的計算複雜度。$3$-著色是指替圖中每個節點指定 $1、2、3$ 其中一種顏色，且每一對相鄰節點的顏色都不同。 判斷複雜度的關鍵是：判定一般圖是否能以 $3$ 種顏色著色，是 NP 完全問題。因此，目前已知的精確演算法需要超多項式時間；若存在多項式時間演算法，便可推出 $P=NP$。 解題方法 題目問的是「最佳已知演算法」的時間複雜度。由於 $3$-著色問題是 NP 完全問題，已知的精確演算法不是 $O(n)$、$O(n^2)$、$O(n^2\log n)$ 或 $O(n^3)$ 這類多項式時間，而是超多項式時間。 這不代表已證明所有演算法都不可能在多項式時間內解題；目前尚未證明 $P
e NP$。考試中依據已知複雜度分類，應選「超多項式時間」。 選項分析

Question 5

For $k=4$, the best known algorithm has time complexity . (A) $O(n)$ (B) $O(n^2)$ (C) $O(n^2\log n)$ (D) $O(n^3)$ (E) superpolynomial time

Accepted Answer

核心觀念 題目考的是固定 $k=4$ 時，一般圖的 $k$-著色決定問題之計算複雜度。問題是判斷能否替每個頂點指定 $1$ 至 $4$ 的顏色，並讓每條邊兩端顏色不同。 一般圖的 4-著色問題是 NP 完全問題。這表示目前沒有已知的多項式時間演算法；若找到這類演算法，便能推出 $P=NP$。已知的精確演算法仍屬指數時間，例如有 $O(1.7159^n)$ 時間的演算法，因此選項中的分類是「超多項式時間」。ESA 2024 研究論文 解題方法 可由 3-著色問題的 NP 完全性說明 4-著色也很難。給定一張圖 $H$，新增一個頂點 $x$，並讓 $x$ 與 $H$ 中每個頂點相鄰： - 若 $H$ 能以 3 種顏色著色，就用第 4 種顏色給 $x$，新圖便能以 4 色著色。 - 若新圖能以 4 色著色，因為 $x$ 與所有原頂點相鄰，原圖頂點不能使用 $x$ 的顏色，所以 $H$ 可用其餘 3 色著色。 因此，若一般圖的 4-著色存在多項式時間演算法，就能用它多項式時間解決 3-著色問題。4-著色問題本身又能在多項式時間內驗證一份著色結果，所以它是 NP 完全問題。

Question 6

Which of the following undirected edges shall be placed in the missing part of Line 3? (A) $(\ell1,\ell2)$ (B) $(\ell1,a1)$ (C) $(\ell1,a2)$ (D) $(\ell1,x2)$

Accepted Answer

核心觀念 要用一次 HamC 判定「是否有一條從 $a1$ 或 $a2$ 出發、走遍其他所有點、停在 $x1,x2,x3$ 之一的路徑」，作法是加入輔助點 $\ell1\sim\ell4$，把路徑沒用到的那個 $a$、那兩個 $x$ 以及所有 $\ell$ 串成一條「回程」，與目標路徑接成一個 Hamiltonian cycle。 回程必須長成： $$ xj-\ell-xk-\ell-xl-\ell-a{	ext{另一個}}-\ell-ai $$ 四個 $\ell$ 正好各司其職： | 輔助點 | 角色 | 加入的邊 | |---|---|---| | $\ell1$ | 接兩個 $a$ | $(\ell1,a1),(\ell1,a2)$ | | $\ell2$ | 接 $a$ 與 $x$ | $(\ell2,a1),(\ell2,a2),(\ell2,x1),(\ell2,x2),(\ell2,x3)$ | | $\ell3$ | 接 $x$ 與 $x$ | $(\ell3,x1),(\ell3,x2),(\ell3,x3)$ | | $\ell4$ | 接 $x$ 與 $x$ | $(\ell4,x1),(\ell4,x2),(\ell4,x3)$ | 正確性 - （⇐） 若 $G$ 有所求路徑 $ai\leadsto xj$，令 $ao$ 為另一個 $a$、$xk,xl$ 為另兩個 $x$，則 $ai\leadsto xj-\ell3-xk-\ell4-xl-\ell2-ao-\ell1-ai$ 是 $H$ 的 Hamiltonian cycle。

Question 7

Which of the following undirected edges shall be placed in the missing part of Line 4? (A) $(\ell2,a1)$ (B) $(\ell2,a2)$ (C) $(\ell2,x2)$ (D) $(\ell2,x3)$

Accepted Answer

核心觀念 要用一次 HamC 判定「是否有一條從 $a1$ 或 $a2$ 出發、走遍其他所有點、停在 $x1,x2,x3$ 之一的路徑」，作法是加入輔助點 $\ell1\sim\ell4$，把路徑沒用到的那個 $a$、那兩個 $x$ 以及所有 $\ell$ 串成一條「回程」，與目標路徑接成一個 Hamiltonian cycle。 回程必須長成： $$ xj-\ell-xk-\ell-xl-\ell-a{	ext{另一個}}-\ell-ai $$ 四個 $\ell$ 正好各司其職： | 輔助點 | 角色 | 加入的邊 | |---|---|---| | $\ell1$ | 接兩個 $a$ | $(\ell1,a1),(\ell1,a2)$ | | $\ell2$ | 接 $a$ 與 $x$ | $(\ell2,a1),(\ell2,a2),(\ell2,x1),(\ell2,x2),(\ell2,x3)$ | | $\ell3$ | 接 $x$ 與 $x$ | $(\ell3,x1),(\ell3,x2),(\ell3,x3)$ | | $\ell4$ | 接 $x$ 與 $x$ | $(\ell4,x1),(\ell4,x2),(\ell4,x3)$ | 正確性 - （⇐） 若 $G$ 有所求路徑 $ai\leadsto xj$，令 $ao$ 為另一個 $a$、$xk,xl$ 為另兩個 $x$，則 $ai\leadsto xj-\ell3-xk-\ell4-xl-\ell2-ao-\ell1-ai$ 是 $H$ 的 Hamiltonian cycle。

Question 8

Which of the following undirected edges shall be placed in the missing part of Line 5? (A) $(\ell3,\ell1)$ (B) $(\ell3,\ell2)$ (C) $(\ell3,x1)$ (D) $(\ell3,x2)$

Accepted Answer

核心觀念 要用一次 HamC 判定「是否有一條從 $a1$ 或 $a2$ 出發、走遍其他所有點、停在 $x1,x2,x3$ 之一的路徑」，作法是加入輔助點 $\ell1\sim\ell4$，把路徑沒用到的那個 $a$、那兩個 $x$ 以及所有 $\ell$ 串成一條「回程」，與目標路徑接成一個 Hamiltonian cycle。 回程必須長成： $$ xj-\ell-xk-\ell-xl-\ell-a{	ext{另一個}}-\ell-ai $$ 四個 $\ell$ 正好各司其職： | 輔助點 | 角色 | 加入的邊 | |---|---|---| | $\ell1$ | 接兩個 $a$ | $(\ell1,a1),(\ell1,a2)$ | | $\ell2$ | 接 $a$ 與 $x$ | $(\ell2,a1),(\ell2,a2),(\ell2,x1),(\ell2,x2),(\ell2,x3)$ | | $\ell3$ | 接 $x$ 與 $x$ | $(\ell3,x1),(\ell3,x2),(\ell3,x3)$ | | $\ell4$ | 接 $x$ 與 $x$ | $(\ell4,x1),(\ell4,x2),(\ell4,x3)$ | 正確性 - （⇐） 若 $G$ 有所求路徑 $ai\leadsto xj$，令 $ao$ 為另一個 $a$、$xk,xl$ 為另兩個 $x$，則 $ai\leadsto xj-\ell3-xk-\ell4-xl-\ell2-ao-\ell1-ai$ 是 $H$ 的 Hamiltonian cycle。

Question 9

Which of the following undirected edges shall be placed in the missing part of Line 6? (A) $(\ell4,\ell3)$ (B) $(\ell4,x1)$ (C) $(\ell4,x2)$ (D) $(\ell4,x3)$

Accepted Answer

核心觀念 要用一次 HamC 判定「是否有一條從 $a1$ 或 $a2$ 出發、走遍其他所有點、停在 $x1,x2,x3$ 之一的路徑」，作法是加入輔助點 $\ell1\sim\ell4$，把路徑沒用到的那個 $a$、那兩個 $x$ 以及所有 $\ell$ 串成一條「回程」，與目標路徑接成一個 Hamiltonian cycle。 回程必須長成： $$ xj-\ell-xk-\ell-xl-\ell-a{	ext{另一個}}-\ell-ai $$ 四個 $\ell$ 正好各司其職： | 輔助點 | 角色 | 加入的邊 | |---|---|---| | $\ell1$ | 接兩個 $a$ | $(\ell1,a1),(\ell1,a2)$ | | $\ell2$ | 接 $a$ 與 $x$ | $(\ell2,a1),(\ell2,a2),(\ell2,x1),(\ell2,x2),(\ell2,x3)$ | | $\ell3$ | 接 $x$ 與 $x$ | $(\ell3,x1),(\ell3,x2),(\ell3,x3)$ | | $\ell4$ | 接 $x$ 與 $x$ | $(\ell4,x1),(\ell4,x2),(\ell4,x3)$ | 正確性 - （⇐） 若 $G$ 有所求路徑 $ai\leadsto xj$，令 $ao$ 為另一個 $a$、$xk,xl$ 為另兩個 $x$，則 $ai\leadsto xj-\ell3-xk-\ell4-xl-\ell2-ao-\ell1-ai$ 是 $H$ 的 Hamiltonian

Question 10

Which of the following statements are (or is) TRUE? ____

(A) Every node can contain at most $2t$ keys.
(B) The depth of every leaf can be different.
(C) There exists one node which may have less than $t$ children.
(D) Every node has at least $t-1$ keys.
(E) If $n\geq1$ , then for any $n$ -key $B$ -tree of height $h$ and minimum degree $t\geq2$ , the condition $\log_t(2t^h)\leq\log_t(n+1)$ is true.

Accepted Answer

核心觀念 本題考查 $B$-tree 的最小度數 $t$，以及由最少節點數推導樹高的界限。依標準定義： - 每個節點最多有 $2t-1$ 個鍵；非根節點至少有 $t-1$ 個鍵。 - 內部非根節點至少有 $t$ 個子節點；根節點是例外，若根為內部節點，至少有 $2$ 個子節點。 - 所有葉節點都在相同深度。 - 非空 $B$-tree 的根至少有 $1$ 個鍵。 解題方法 先用節點容量與根節點的例外判斷 (A) 至 (D)，再由高度為 $h$ 的 $B$-tree 在各層最少能有多少節點，推導 (E)。 若樹高為 $h$，根至少有 $1$ 個鍵，且若根為內部節點，至少有 $2$ 個子節點。對 $i\geq 1$，深度 $i$ 至少有 $2t^{i-1}$ 個節點；每個這些節點至少有 $t-1$ 個鍵。因此： $$ n \geq 1+\sum{i=1}^{h}2t^{i-1}(t-1) $$ $$ n \geq 1+2(t-1)\frac{t^h-1}{t-1} =2t^h-1 $$ $h=0$ 時根是葉節點，且非空樹至少有 $1$ 個鍵，同樣符合 $n\geq 2t^0-1=1$。因此 $n+1\geq 2t^h$。

Question 11

When a new key is added to a $B$-tree, which of the following statements are (or is) TRUE? (A) If the key is inserted into a full node, the full node is split. Then the key must be placed in a new node which is the parent node of the nodes that are split from the full node. (B) The root node can be split even if it is not full. (C) When a full node is split, it is split around the median key. (D) The height of the $B$-tree increases if and only if the root node is split. (E) After a full node is split, it is impossible that another node is split too.

Accepted Answer

核心觀念 最小度數為 $t$ 的 $B$-tree 中，非根節點可有 $t-1$ 到 $2t-1$ 個鍵；根節點最多也有 $2t-1$ 個鍵。含有 $2t-1$ 個鍵的節點稱為滿節點。 分裂滿節點時，將中位鍵提升至父節點，其餘鍵分到兩個子節點。插入過程若分裂根節點，會建立新根，因此樹高增加一層。 解題方法 依序檢查各選項是否符合滿節點分裂規則，以及插入時樹高的變化。特別要分清楚：分裂時提升的是原節點的中位鍵；新插入的鍵則依鍵值大小，放入適當的葉節點。 選項分析 (A) 錯誤。 分裂後，中位鍵會被提升到父節點；新插入的鍵則會依大小放入相應的子節點。新插入的鍵不一定放進由分裂產生的父節點。

Question 12

The minimum spanning tree (MST) of $G$ is ____.

(A) 🖼️【此處有附圖，見下方】
(B) 🖼️【此處有附圖，見下方】
(C) 🖼️【此處有附圖，見下方】
(D) 🖼️【此處有附圖，見下方】
(E) 🖼️【此處有附圖，見下方】

Accepted Answer

核心觀念 最小生成樹（MST）必須連接原圖的全部頂點、不含環，並使邊權重總和最小。若原圖有 $n$ 個頂點，生成樹一定有 $n-1$ 條邊。 本題可用 Kruskal 演算法：依權重由小到大選邊，只要加入該邊不會形成環，就保留它，直到選滿 $n-1$ 條邊。 解題方法 原圖共有 8 個頂點，因此 MST 必須包含 7 條邊。依圖中的位置，將「最左、左上、左下、中央、最下、右上、右下、最右」的頂點，依序記為 $v1,v2,\ldots,v8$。 依 Kruskal 演算法選邊；相同權重的邊可依任意順序處理，以下採用能直接對照選項（B）的順序： | 權重 | 選入的邊 | 選取理由 | |---|---|---| | $1$ | $v2v3$ | 最小權重，加入後不形成環 | | $2$ | $v1v5$、$v6v7$、$v6v8$ | 三條邊都不形成環，全數選入 | | $3$ | $v3v4$、$v3v5$ | 將左側五個頂點連接起來 | | $4$ | $v4v6$ | 連接左、右兩個連通分量 | 處理權重 $3$ 的邊時，選入 $v3v4$、$v3v5$ 後，另一條權重 $3$ 的邊 $v1v2$ 會形成環： $$ v1	o v5	o v3	o v2	o v1, $$ 因此略過。權重 $4$ 的邊 $v2v4$ 也會形成環，略過；$v4v6$ 則能連接左右兩部分，應選入。 以上七條邊正是選項（B），總權重為：

Question 13

A new graph can be obtained after the weight of an edge of graph $G$ is changed to 1 so that the weight of the MST of the new graph has the lowest weight among all the possible resulting graphs. The weight of the MST of the new graph is ____.

(A) 17
(B) 18
(C) 13
(D) 14
(E) 15

Accepted Answer

讀圖（Figure 1） 把 8 個頂點命名為：左 $L$、上 $T$、左下 $M$、中 $C$、下 $B$、中右上 $P$、右 $R$、右下 $Q$。14 條邊與權重： | 邊 | 權重 | 邊 | 權重 | |---|---:|---|---:| | $T$–$M$ | 1 | $T$–$C$ | 4 | | $L$–$B$ | 2 | $C$–$P$ | 4 | | $P$–$R$ | 2 | $L$–$R$（上方弧） | 5 | | $P$–$Q$ | 2 | $C$–$B$ | 5 | | $L$–$T$ | 3 | $L$–$M$ | 6 | | $M$–$C$ | 3 | $Q$–$R$ | 7 | | $M$–$B$ | 3 | $B$–$Q$ | 9 | 原圖的 MST（Kruskal）：依序取 $1,2,2,2,3(L	ext{–}T),3(M	ext{–}C)$；$M$–$B$ 會成圈略過；$T$–$C$ 成圈略過；取 $C$–$P(4)$ 後 8 點連通。 $$ 	ext{MST}=\{T M,\ L B,\ P R,\ P Q,\ L T,\ M C,\ C P\},\quad w=1+2+2+2+3+3+4=17 $$

Question 14

A new graph can be obtained after an edge of graph $G$ is deleted so that the weight of the MST of the new graph has the highest weight among all the possible resulting graphs. The weight of the MST of the new graph is ____.

(A) 22
(B) 23
(C) 19
(D) 20
(E) 21

Accepted Answer

讀圖（Figure 1） 把 8 個頂點命名為：左 $L$、上 $T$、左下 $M$、中 $C$、下 $B$、中右上 $P$、右 $R$、右下 $Q$。14 條邊與權重： | 邊 | 權重 | 邊 | 權重 | |---|---:|---|---:| | $T$–$M$ | 1 | $T$–$C$ | 4 | | $L$–$B$ | 2 | $C$–$P$ | 4 | | $P$–$R$ | 2 | $L$–$R$（上方弧） | 5 | | $P$–$Q$ | 2 | $C$–$B$ | 5 | | $L$–$T$ | 3 | $L$–$M$ | 6 | | $M$–$C$ | 3 | $Q$–$R$ | 7 | | $M$–$B$ | 3 | $B$–$Q$ | 9 | 原圖的 MST（Kruskal）：依序取 $1,2,2,2,3(L	ext{–}T),3(M	ext{–}C)$；$M$–$B$ 會成圈略過；$T$–$C$ 成圈略過；取 $C$–$P(4)$ 後 8 點連通。 $$ 	ext{MST}=\{T M,\ L B,\ P R,\ P Q,\ L T,\ M C,\ C P\},\quad w=1+2+2+2+3+3+4=17 $$ 解題方法 刪掉非樹邊，MST 不變（17）；刪掉樹邊 $e$，樹分成兩塊，要改用跨越這兩塊的最便宜非樹邊：

Question 15

Condition One: The same node is visited a maximum of two times. The weight of the path under Condition One is . (A) $-12$ (B) $-13$ (C) $-29$ (D) $-41$ (E) $-43$

Accepted Answer

讀圖（Figure 2） 雙箭頭的邊代表兩個方向各一條。有向邊與權重： - $A	o B$：$-6$；$A\leftrightarrow B$：$5$（另一條弧，雙向） - $A	o C$：$-9$；$A\leftrightarrow C$：$2$（雙向） - $B\leftrightarrow C$：$15$；$B	o D$：$-17$；$E	o C$：$-10$ - $D\leftrightarrow E$：$3$；$D\leftrightarrow F$：$11$；$E\leftrightarrow F$：$7$ 圖中有負圈，例如 $A	o B	o D	o E	o C	o A$：$-6-17+3-10+2=-28$。所以「不設限」的最短路徑是 $-\infty$，題目才用三種條件限制重複。 左半 $\{A,B,C\}$ 到右半只有一條入口 $B	o D$，右半回到左半只有 $E	o C$；到 $F$ 只能由 $D	o F(11)$ 或 $E	o F(7)$。 解題方法（條件一：每個點最多走兩次）

Question 16

Condition Two: The same node is visited at most once. The weight of the path under Condition Two is . (A) $-10$ (B) $-11$ (C) $-12$ (D) $-13$ (E) $-17$

Accepted Answer

讀圖（Figure 2） 雙箭頭的邊代表兩個方向各一條。有向邊與權重： - $A	o B$：$-6$；$A\leftrightarrow B$：$5$（另一條弧，雙向） - $A	o C$：$-9$；$A\leftrightarrow C$：$2$（雙向） - $B\leftrightarrow C$：$15$；$B	o D$：$-17$；$E	o C$：$-10$ - $D\leftrightarrow E$：$3$；$D\leftrightarrow F$：$11$；$E\leftrightarrow F$：$7$ 圖中有負圈，例如 $A	o B	o D	o E	o C	o A$：$-6-17+3-10+2=-28$。所以「不設限」的最短路徑是 $-\infty$，題目才用三種條件限制重複。 左半 $\{A,B,C\}$ 到右半只有一條入口 $B	o D$，右半回到左半只有 $E	o C$；到 $F$ 只能由 $D	o F(11)$ 或 $E	o F(7)$。 解題方法（條件二：每個點最多一次，即簡單路徑）

Question 17

Condition Three: The same edge is visited a maximum of two times. The weight of the path under Condition Three is . (A) $-50$ (B) $-48$ (C) $-45$ (D) $-44$ (E) $-37$

Accepted Answer

讀圖（Figure 2） 雙箭頭的邊代表兩個方向各一條。有向邊與權重： - $A	o B$：$-6$；$A\leftrightarrow B$：$5$（另一條弧，雙向） - $A	o C$：$-9$；$A\leftrightarrow C$：$2$（雙向） - $B\leftrightarrow C$：$15$；$B	o D$：$-17$；$E	o C$：$-10$ - $D\leftrightarrow E$：$3$；$D\leftrightarrow F$：$11$；$E\leftrightarrow F$：$7$ 圖中有負圈，例如 $A	o B	o D	o E	o C	o A$：$-6-17+3-10+2=-28$。所以「不設限」的最短路徑是 $-\infty$，題目才用三種條件限制重複。 左半 $\{A,B,C\}$ 到右半只有一條入口 $B	o D$，右半回到左半只有 $E	o C$；到 $F$ 只能由 $D	o F(11)$ 或 $E	o F(7)$。 解題方法（條件三：每條邊最多走兩次） - 進入右半只能走 $B	o D$，最多兩次；走路最後要停在 $F$，所以最多「一次去而復返」加「一次去到 $F$」。 - 去而復返最省：$B	o D	o E	o C$，$-17+3-10=-24$。

Question 18

What is the purpose of union by rank?

Accepted Answer

核心觀念 「按秩合併」（union by rank）是並查集森林的合併策略：合併兩個集合時，比較兩棵樹根節點的秩（rank），將秩較小的根接到秩較大的根底下；兩根秩相同時，任選一根作為新根，並將新根的秩加 $1$。 秩用來控制樹高。採用按秩合併後，含 $n$ 個元素的樹高至多為 $\lfloor \log2 n \rfloor$，因此可避免合併操作把森林退化成很長的鏈。 解題方法 題目問按秩合併的目的，直接對照各敘述所描述的操作即可：將較小秩樹的根接到較大秩樹的根，正是按秩合併的規則；其目的在限制樹高。若再搭配路徑壓縮，並查集操作的攤銷時間複雜度可達 $O(\alpha(n))$，其中 $\alpha$ 是反阿克曼函數。 選項分析

Question 19

What is the purpose of path compression?

Accepted Answer

核心觀念 不相交集合（disjoint set）森林以樹表示集合，根節點是代表元。Find(x) 會沿著父節點指標往上走，直到找到根節點。若樹很高，這段路徑就會很長。 路徑壓縮（path compression）是在執行 Find(x) 時，把查找路徑上的節點直接改指向根節點，降低樹高，讓後續的 Find 更快。壓縮的是這次查找走過的路徑，不代表一次操作就把整個森林中的所有節點都改成指向根節點。 解題方法 依序判斷選項描述的集合操作。路徑壓縮的關鍵特徵是：它在尋找代表元時，縮短查找路徑，使沿途節點直接連到根。因此，最符合題意的是選項 C。 選項分析

Question 20

What is the purpose of weighted-union heuristic?

Accepted Answer

核心觀念 這題考的是鏈結串列表示法中的加權合併（weighted-union heuristic）。每個集合以鏈結串列表示，並讓每個元素都能指向該集合的代表元素。 合併兩個集合時，若把其中一個串列的所有元素都更新為新代表，成本與被更新的串列長度成正比。加權合併的做法是：把較短的串列接到較長的串列後面，讓需要更新代表指標的元素數量較少。 解題方法 對每次合併，選較短的串列作為被接上的串列，只更新其中元素的代表指標。若某元素的代表指標因此改變，該元素所在的集合至少會變成原來的兩倍大：它原先在較短串列中，合併後串列長度至少是它原集合大小的兩倍。 因此，一個元素的代表指標最多改變 $\lfloor \log2 n \rfloor$ 次，其中 $n$ 是元素總數。這使得連結串列表示法的合併操作更有效率，全部合併的代表指標更新成本為 $O(n\log n)$。 選項分析

Question 21

Which of the following statements are (or is) TRUE? (A) $a2=1$. (B) $b3=30$. (C) $a5=a4+6b4$. (D) $b5=2a4+6b4$. (E) For some finite $n$, $an$ is not integral.

Accepted Answer

核心觀念 本題考查根式係數的乘法，以及遞迴演算法所對應的數學遞迴式。若 $$ an+bn\sqrt{3}=(1+2\sqrt{3})^n $$ 將兩邊乘上 $1+2\sqrt{3}$，可得 $$ \begin{aligned} a{n+1}+b{n+1}\sqrt{3} &=(an+bn\sqrt{3})(1+2\sqrt{3})\ &=(an+6bn)+(2an+bn)\sqrt{3}. \end{aligned} $$ 因此係數滿足 $$ a{n+1}=an+6bn,\qquad b{n+1}=2an+bn, $$ 且初始值為 $a1=1,\ b1=2$。 解題方法 依照遞迴式逐步計算： $$ \begin{array}{c|r|r} n & an & bn\ \hline 1 & 1 & 2\ 2 & 1+6(2)=13 & 2(1)+2=4\ 3 & 13+6(4)=37 & 2(13)+4=30\ 4 & 37+6(30)=217 & 2(37)+30=104\ 5 & 217+6(104)=841 & 2(217)+104=538 \end{array} $$

Question 22

Algorithm 2 has running time in the worst case (as close as possible). (A) $O(\log n)$ (B) $O(n)$ (C) $O(n\log n)$ (D) $O(n^2)$ (E) $O(\log^2 n)$

Accepted Answer

核心觀念

這題考遞迴演算法的時間複雜度。分析時要看每次遞迴把輸入規模縮小多少，以及每次呼叫額外花多少時間。

解題方法

當 $n>1$ 時，演算法呼叫 $P(n-1)$ ，接著只做固定次數的加法與乘法，因此每次呼叫的額外工作量為 $\Theta(1)$ 。

令 $T(n)$ 表示執行時間，則：

T(n)=T(n-1)+\Theta(1),\qquad T(1)=\Theta(1)

從 $n$ 遞減到 $1$ ，共呼叫 $P(n),P(n-1),\ldots,P(1)$ ，總計 $n$ 次。每次工作量為常數，因此：

T(n)=\Theta(n)

最接近的選項是 $O(n)$ 。

選項分析

Question 23

Which of the following statements are (or is) TRUE? ____

(A) Every node can contain at most $2t$ keys.
(B) The depth of every leaf can be different.
(C) There exists one node which may have less than $t$ children.
(D) Every node has at least $t-1$ keys.
(E) If $n\geq1$ , then for any $n$ -key $B$ -tree of height $h$ and minimum degree $t\geq2$ , the condition $\log_t(2t^h)\leq\log_t(n+1)$ is true.

Accepted Answer

核心觀念 這題考的是代數式的係數表示、遞迴演算法的效率，以及快速冪。 將 $a+b\sqrt{3}$ 視為一組係數 $(a,b)$。兩個這類表示相乘時： $$ (a+b\sqrt{3})(c+d\sqrt{3}) =(ac+3bd)+(ad+bc)\sqrt{3} $$ 因此，係數相乘的規則是： $$ (a,b)\cdot(c,d)=(ac+3bd,\ ad+bc) $$ 題目給的遞迴正是由 $$ (a+b\sqrt{3})(1+2\sqrt{3}) =(a+6b)+(2a+b)\sqrt{3} $$ 推得，所以每次將指數增加 $1$，就能更新 $(an,bn)$。 解題方法 直接依照 Algorithm 2 從 $P(1)$ 算到 $P(n)$，每次只做固定次數的算術運算，共需 $n-1$ 次更新，時間為 $O(n)$。但利用二進位快速冪，可以在 $O(\log n)$ 次係數乘法內算出 $(an,bn)$。 設 $m=\lfloor n/2\rfloor$，先算出 $$ (am+bm\sqrt{3})^2 =(am^2+3bm^2)+2ambm\sqrt{3} $$ 因此： $$ a{2m}=am^2+3bm^2,\qquad b{2m}=2ambm $$ 若 $n=2m+1$，再乘上 $(1+2\sqrt{3})$，即可得到： $$ a{2m+1}=a{2m}+6b{2m},\qquad b{2m+1}=2a{2m}+b{2m} $$ 每次將指數折半，遞迴深度為 $O(\log n)$，所以能比 Algorithm 2 更有效率地計算。 選項分析

Question 24

What is the largest $k$? (A) 6 (B) 4 (C) 3 (D) 7 (E) 5

Accepted Answer

核心觀念 每選入一個數字，後續數字就必須滿足「已選總和不超過目前數字的 6 倍」。因此，對每個選取數量 $k$，只需保留能達成該數量的最小總和：總和越小，越容易符合後續數字的條件。 令 $dp[k]$ 表示目前處理過的數字中，恰好選取 $k$ 個數字時可達成的最小總和；若無法達成，記為 $\infty$。初始值為 $dp[0]=0$。 解題方法 依序處理輸入 $2,5,3,6,2,1,2$。遇到數字 $x$ 時，若目前恰選 $k$ 個的最小總和 $dp[k]$ 符合 $dp[k]\le 6x$，就能再選入 $x$，形成 $k+1$ 個數字，總和為 $dp[k]+x$。表中各欄列出處理完該數字後，各選取數量能達成的最小總和。 | 已處理數字 | $k=0$ | $k=1$ | $k=2$ | $k=3$ | $k=4$ | $k=5$ | $k=6$ | |---|---:|---:|---:|---:|---:|---:|---:| | 無 | 0 | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | | 2 | 0 | 2 | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | | 5 | 0 | 2 | 7 | $\infty$ | $\infty$ | $\infty$ | $\infty$ | | 3 | 0 | 2 | 5 | 10 | $\infty$ | $\infty$ | $\infty$ | | 6 | 0 | 2 | 5 | 10 | 16 | $\infty$ | $\infty$ |

Question 25

Consider the sequence $\langle1,1,1,1,1,1,w,2,2,2,3,3,4,4,x,y\rangle$ that satisfies the above condition. Which of the following statements are (or is) TRUE?

(A) $x\geq5$ .
(B) $y>5$ .
(C) The smallest possible $w$ is 2.
(D) There is a possible solution with $w+x+y=12$ .
(E) This sequence can be extended to be an infinite sequence that satisfies the above condition.

Accepted Answer

核心觀念 設目前項目前的前綴和為 $S$，若下一項是 $a$，Prefix-Sum condition 等價於 $$ S\le 6a \quad\Longleftrightarrow\quad a\ge \left\lceil \frac{S}{6}\right\rceil . $$ 因此，逐項檢查前綴和即可找出 $w,x,y$ 的限制。 解題方法 前六項都是 $1$，其前綴和依序不超過 $5$，都符合條件。到 $w$ 前的前綴和為 $6$，故 $w\ge 1$。 接著檢查三個 $2$。第三個 $2$ 前的前綴和為 $10+w$，所以 $$ 10+w\le 6(2)=12 \quad\Longrightarrow\quad w\le 2. $$ 其他 $2$、$3$、$4$ 的條件不會比這個限制更嚴格。因此 $$ w\in\{1,2\}. $$ 到 $x$ 前的前綴和為 $$ 6+w+3(2)+2(3)+2(4)=26+w. $$ 所以 $$ x\ge \left\lceil\frac{26+w}{6}\right\rceil=5, $$ 其中 $w=1$ 或 $w=2$ 都得到 $x\ge 5$。 到 $y$ 前的前綴和為 $26+w+x$，因此 $$ y\ge \left\lceil\frac{26+w+x}{6}\right\rceil. $$

Question 26

Denote $D(i,s)$ to be the maximum number of elements that can be selected from the first $i$ integers in $A$ with a sum at most $s$ , and satisfy the Prefix-Sum condition. Which of the following statements are (or is) TRUE?

(A) This problem can be solved with Dynamic Programming.
(B) $D(i,s)=\max(D(i-1,s),D(i-1,s-a_i)+1)$ .
(C) $D(i,s)=\max(D(i-1,s),D(i-1,\min(s-a_i,6a_i))+1)$ .
(D) The answer is $D(n,6a_n)$ .
(E) The time complexity to find the answer is $O(n\max_{i\in\{1,2,\ldots,n\}}\{a_i\})$ .

Accepted Answer

核心觀念 這題把「選取子序列」的限制轉成動態規劃。每加入一個新元素 $ai$，要同時滿足兩件事： 1. 選取元素的總和不超過狀態上限 $s$。 2. 加入 $ai$ 前，已選元素的總和不超過 $6ai$。 因此，若要選 $ai$，前面已選元素的總和最多是 $\min(s-ai,6ai)$。 解題方法 考慮前 $i$ 個元素時，對 $ai$ 分成「不選」和「選」兩種情況： - 不選 $ai$：最多選 $D(i-1,s)$ 個。 - 選 $ai$：前面元素的總和須不超過 $s-ai$，也須不超過 $6ai$，所以最多選 $D(i-1,\min(s-ai,6ai))+1$ 個。 故遞迴式為 $$ D(i,s)=\max\left(D(i-1,s),D(i-1,\min(s-ai,6ai))+1\right). $$ 若 $s<ai$，選取 $ai$ 的情況不可行；實作時可略過該分支，或將不可行狀態設為負無限大。 設 $M=\maxi ai$。任何非空合法子序列若最後選到 $aj$，其先前元素總和至多為 $6aj$，因此整個子序列的總和至多為 $7aj\leq 7M$。所以計算到總和上限 $7M$，即可涵蓋所有可能的合法子序列，答案為 $D(n,7M)$。 共有 $n$ 列、至多 $7M+1$ 個總和狀態，每個狀態只需常數時間，時間複雜度為 $O(nM)$；用逐列更新可將空間降為 $O(M)$。 選項分析

Question 27

Which of the following statements are (or is) TRUE? ____

(A) Let $\alpha$ be the load factor of a hash table. If collisions are resolved by chaining in the hash table, then both the successful search and the unsuccessful search take expected time $O(1+\alpha)$ under the assumption of simple uniform hashing.
(B) The asymptotic time complexity of searching a key in a heap structure is $O(\log n)$ , where $n$ is the number of elements in the structure.
(C) Suppose that a hash table has $m$ slots. The table can store at most $m$ keys if collision is resolved by chaining.
(D) An AVL tree is a binary search tree.
(E) In a red-black tree, a node has two children and one of the children is red. The node must be black.

Accepted Answer

核心觀念

本題考查雜湊表的鏈結法、堆積的搜尋複雜度、AVL 樹的定義，以及紅黑樹的顏色規則。

雜湊表的負載因子為 $\alpha=n/m$ ，其中 $n$ 是鍵值數量、 $m$ 是槽位數量。
鏈結法會在每個槽位存放一條鏈結串列，因此每個槽位可容納多個鍵值。
堆積只保證父子節點符合堆積順序，不保證整體符合二元搜尋樹的順序。
AVL 樹是具有高度平衡限制的二元搜尋樹。
紅黑樹規定紅色節點的子節點必須是黑色。

解題方法

逐項對照資料結構的定義與複雜度。特別注意搜尋堆積中的任意鍵值，不等同於取得堆積頂端元素；堆積的局部順序不足以像二元搜尋樹那樣排除一半搜尋範圍。

選項分析

(A) 正確。
在簡單均勻雜湊假設下，每個鍵值平均均勻地分布到 $m$ 個槽位。鏈結法的失敗搜尋，平均需要檢查所選槽位中的鏈結串列，期望檢查數量為 $O(\alpha)$ ；若計入雜湊與定位等固定成本，期望時間為 $O(1+\alpha)$ 。成功搜尋的期望時間也為 $O(1+\alpha)$ 。因此敘述正確。

Question 28

BubbleSort has running time complexity in the worst case. (A) $O(\log n)$ (B) $O(n\log n)$ (C) $O(n)$ (D) $O(n^2)$ (E) $O(1)$

Accepted Answer

核心觀念

氣泡排序會反覆比較相鄰元素，若順序不符合目標，就交換兩者。分析最壞情況時，要計算輸入資料最不利時，演算法執行的比較與交換次數。

本題要求由大到小排序；排序方向會影響比較條件，但不改變氣泡排序在最壞情況下的漸近時間複雜度。

解題方法

每一趟掃描會將尚未排定範圍中的一個元素移至正確位置。最壞情況下，第一趟最多比較 $n-1$ 次，第二趟最多比較 $n-2$ 次，依此類推，直到最後一趟比較 $1$ 次。

因此，比較次數為：

(n-1)+(n-2)+\cdots+1 =\frac{n(n-1)}{2}

展開後的最高次項為 $\frac{1}{2}n^2$ ，所以最壞情況的時間複雜度為 $\Theta(n^2)$ ，以選項中的大 $O$ 表示為 $O(n^2)$ 。即使實作包含「某一趟沒有交換就提前結束」的檢查，最壞情況仍須進行二次量級的比較與交換。

選項分析

Question 29

HeapSort has running time complexity in the worst case. (A) $O(\log n)$ (B) $O(n\log n)$ (C) $O(n)$ (D) $O(\sqrt{n})$ (E) $O(1)$

Accepted Answer

核心觀念

本題考查 HeapSort（堆積排序）的最壞時間複雜度。二元堆積是一種完全二元樹，含有 $n$ 個元素時，高度為 $\Theta(\log n)$ 。插入或刪除堆頂元素時，至多沿著樹高調整，因此單次操作需要 $\Theta(\log n)$ 時間。

解題方法

HeapSort 先將 $n$ 個元素建立成堆積，再反覆取出堆頂元素，並調整剩餘元素，使其重新符合堆積性質。

建立堆積可用自底向上的方法，時間為 $\Theta(n)$ 。
每次取出堆頂後，最多需要沿堆積高度調整，時間為 $O(\log n)$ 。
取出所有元素共需 $n$ 次，因此這部分的時間為 $O(n\log n)$ 。

合計為：

\Theta(n) + \Theta(n\log n) = \Theta(n\log n)

要排成遞減順序，可使用適當方向的堆積；排序方向不影響最壞時間複雜度。因此 HeapSort 的最壞時間複雜度是 $O(n\log n)$ 。

選項分析

Question 30

Consider the above table with $N=4$ and let the communication cost be $c_{1,2}=5$ , $c_{2,3}=6$ , $c_{2,4}=2$ , $c_{3,4}=1$ , and the rest have 0 communication cost. Let $X$ be the best answer. Which of the following statements are (or is) TRUE?

(A) $X\bmod10=4$
(B) $\lfloor X/10\rfloor=1$
(C) $X\leq25$
(D) $X\bmod2=0$
(E) None of the above is true.

Accepted Answer

核心觀念 這題是兩處理器工作分配的最小化問題。每個模組只能分配到一個處理器，總成本由兩部分組成： 1. 各模組在所分配處理器上的執行成本。 2. 相鄰模組分配到不同處理器時產生的通訊成本。 若以 $xi\in\{1,2\}$ 表示模組 $i$ 分配到的處理器，總成本為 $$ C(x1,x2,x3,x4) = \sum{i=1}^{4} \begin{cases} ai,&xi=1\ bi,&xi=2 \end{cases} + \sum{(i,j)} c{i,j}\,\mathbf{1}[xi
e xj], $$ 其中 $\mathbf{1}[xi
e xj]$ 在兩模組分配到不同處理器時為 $1$，否則為 $0$。 解題方法 題目只有 $4$ 個模組，可把可能分配方式分組計算。觀察通訊成本的連線：$(1,2)$、$(2,3)$、$(2,4)$、$(3,4)$。先固定模組 $2$、$3$ 的處理器，再分別選擇模組 $1$、$4$ 的最佳處理器。 模組 $1$ 只和模組 $2$ 有通訊成本： - 若模組 $2$ 在處理器 2，模組 $1$ 選處理器 2 的成本為 $4$；選處理器 1 則成本為 $6+5=11$，故最佳成本為 $4$。 - 若模組 $2$ 在處理器 1，模組 $1$ 選處理器 1 的成本為 $6$；選處理器 2 則成本為 $4+5=9$，故最佳成本為 $6$。 模組 $4$ 的最佳成本則需計入它與模組 $2$、$3$ 的通訊成本： | 模組 2 | 模組 3 | 模組 4 在處理器 1 的成本 | 模組 4 在處理器 2 的成本 | 最佳成本 | |---|---|---:|---:|---:| | 2 | 2 | $4+2+1=7$ | $8$ | $7$ | | 2 | 1 | $4+2=6$ | $8+1=9$ | $6$ | | 1 | 2 | $4+1=5$ | $8+2=10$ | $5$ | | 1 | 1 | $4$ | $8$ | $4$ |

Question 31

We can model this problem with an undirected graph $G=(V,E)$ , where $V=\{p_1,p_2,v_1,\ldots,v_N\}$ and
$E=\{(p_1,v_i),(v_i,p_2):i=1..N\}\cup\{(v_i,v_j):c_{i,j}>0\}$ . For $i=1..N$ , the weight for edge $(p_1,v_i)$ is $a_i$ and the weight for edge $(v_i,p_2)$ is $b_i$ . The weight for $(v_i,v_j)\in E$ is $c_{i,j}$ . Which of the following statements are (or is) TRUE?

(A) There are $2^N$ possible ways to assign the modules to the two processors.
(B) Let $A_i$ be the set of modules assigned to processor $i$ , for $i\in\{1,2\}$ . Then the cost is $\sum_{j\in A_1}a_j+\sum_{j\in A_2}b_j+\sum_{(v_i,v_j)\in A_1\times A_2}c_{i,j}$ .
(C) The cost relates to a cut of the graph $G=(V,E)$ with $p_1$ and $p_2$ on the same side.
(D) The minimum cost relates to a minimum flow from a source to a sink.
(E) Let $A_i$ be the set of modules assigned to processor $i$ , for $i\in\{1,2\}$ . Then $\{p_1\}\cup A_1,\{p_2\}\cup A_2$ is a cut.

Accepted Answer

核心觀念 每個模組只能指派給處理器 1 或處理器 2，因此共有 $2^N$ 種指派。總成本包含兩部分： 1. 各模組在所屬處理器上的執行成本。 2. 分配到不同處理器的模組對之間的通訊成本。 令 $A1$、$A2$ 分別為指派給處理器 1、2 的模組集合，則 $A1$ 與 $A2$ 互斥，且兩者聯集為所有模組。總成本為 $$ \sum{j\in A1}aj+\sum{j\in A2}bj+ \sum{\substack{i\in A1,\ j\in A2}}c{i,j}. $$ 圖論中的割是把頂點分成兩個不相交且聯集為全體頂點的集合；兩側之間的邊稱為割邊。若要用「$p1$ 到 $p2$ 的割」表示兩處理器的指派，$p1$ 和 $p2$ 必須分處割的兩側，割邊的權重總和才代表割容量。 解題方法 先將模組指派寫成集合分割，再逐一核對各選項。圖的頂點集合為 $\{p1,p2,v1,\ldots,vN\}$，其中模組對應頂點 $vi$。把模組分配到不同處理器所產生的通訊成本，對應到兩側之間的模組邊；因此割的通訊成本部分，會計入所有跨越 $A1$、$A2$ 的邊。 不過，題目給定的處理器邊權重與執行成本的對應方向不吻合。若採用選項（E）的分割方式 $\{p1\}\cup A1$ 與 $\{p2\}\cup A2$，則 $p1$ 到 $vi$ 的邊在 $i\in A2$ 時跨割，產生 $ai$；而 $vi$ 到 $p2$ 的邊在 $i\in A1$ 時跨割，產生 $bi$。

Question 32

Which of the following statements are (or is) TRUE?

(A) The above $G=(V,E)$ is a bipartite graph.
(B) The minimum cost can be found with the Prim algorithm.
(C) The minimum cost can be found with the Dijkstra algorithm.
(D) The minimum cost can be found with the Edmonds-Karp algorithm.
(E) The minimum cost can be found with the Ford-Fulkerson algorithm.

Accepted Answer

核心觀念 這題考的是把「模組分配到兩台處理器，使總成本最小」轉換成最小割問題，再利用最大流最小割定理求解。 最小割把頂點分成包含源點 $s$ 的集合 $S$ 與包含匯點 $t$ 的集合 $T$，割的容量是所有由 $S$ 指向 $T$ 的邊容量總和。最大流最小割定理指出：最大流的值等於最小割的容量。 解題方法 建立流網路如下： - 加入源點 $s$、匯點 $t$，並為每個模組 $i$ 建立一個頂點。 - 加入容量為 $bi$ 的邊 $s	o i$，以及容量為 $ai$ 的邊 $i	o t$。 - 對每對模組 $i,j$，加入容量為 $c{i,j}$ 的雙向通信邊。 將割的 $S$ 側視為分配到處理器 1，$T$ 側視為分配到處理器 2： - 模組 $i$ 在 $S$ 側時，邊 $i	o t$ 跨越割，成本為 $ai$。 - 模組 $i$ 在 $T$ 側時，邊 $s	o i$ 跨越割，成本為 $bi$。 - 模組 $i,j$ 位於不同側時，通信邊跨越割，成本為 $c{i,j}$。

Question 33

What are the outputs by the post-order traversal?

(A) $35,27,21,13,19,11,10,9,7,8,17$
(B) $35,27,13,9,7,19,8,17,21,11,10$
(C) $9,7,13,8,17,19,27,11,10,21,35$
(D) $9,7,13,8,17,19,27,35,11,10,21$
(E) $9,13,7,27,8,19,17,35,11,21,10$

Accepted Answer

核心觀念 最大堆插入新鍵值時，先將新值放到完全二元樹的下一個空位，再沿著父節點向上調整；若新值大於父節點，就交換，直到符合最大堆條件。 後序走訪依序為「左子樹、右子樹、根節點」。 解題方法 圖中原有的最大堆包含 $10$ 個節點：根節點為 $27$；其左、右子節點分別為 $19$、$21$；下一層為 $13,17,11,10$；最下層為 $9,7,8$。依完全二元樹的排列方式，新鍵值 $35$ 先放在節點 $17$ 的右子節點位置。 因為 $3517$、$3519$、$3527$，所以插入後依序向上交換。調整後的堆為： 依後序走訪： - 左子樹：先走訪 $13$ 的左右子節點，再走訪 $13$，接著走訪 $19$ 的左右子節點，再走訪 $19$，最後走訪 $27$，得到 $9,7,13,8,17,19,27$。

Question 34

What are the outputs by the in-order traversal?

(A) $35,27,21,13,19,11,10,9,7,8,17$
(B) $35,27,13,9,7,19,8,17,21,11,10$
(C) $9,7,13,8,17,19,27,11,10,21,35$
(D) $9,7,13,8,17,19,27,35,11,10,21$
(E) $9,13,7,27,8,19,17,35,11,21,10$

Accepted Answer

核心觀念 最大堆積（max heap）是完全二元樹，每個父節點的值皆不小於子節點。插入新值時，先放在維持完全二元樹的下一個位置，再與父節點比較，必要時交換並向上調整。 中序走訪（in-order traversal）的順序為： $$ 	ext{左子樹}\;ightarrow\;	ext{根節點}\;ightarrow\;	ext{右子樹} $$ 此規則必須遞迴套用於每棵子樹。最大堆積並非二元搜尋樹，因此中序走訪的結果不必由小到大排列。 解題方法 原圖的根節點為 $27$，左右子節點分別為 $19、21$；$19$ 的左右子節點為 $13、17$，$21$ 的左右子節點為 $11、10$。另外，$13$ 的左右子節點為 $9、7$，$17$ 的左子節點為 $8$。 1. 插入 $35$ 並向上調整 依完全二元樹的插入規則，$35$ 放在 $17$ 的右子節點。由於 $35$ 大於沿途的父節點，因此依序交換： $$ 35 \leftrightarrow 17,\qquad 35 \leftrightarrow 19,\qquad 35 \leftrightarrow 27 $$ 調整後的堆積如下： 2. 依「左、根、右」走訪 根節點 $35$ 的左子樹以 $27$ 為根：

Question 35

Consider a binary search tree which stores distinct elements. The keys in the left subtree of a node are smaller than those in the right subtree of the node (if any). Denote NIL as a null pointer. $p$ and $right$ are the pointers directing to a node’s parent node and the right child node, respectively. Function TreeMinimum($n$) returns the minimum node (i.e., the node that has the smallest key) of a subtree rooted at node $n$. Assume that $x$ is a node in the binary search tree. The following code fragment is executed. After that, $y$ is not equal to NIL. if $right[x]
e NIL$ $y=Tree\Minimum(right[x])$; return $y=p[x]$ while $y
e NIL$ and $x=right[y]$ do $x=y$ and $y=p[y]$ return Which of the following statements are (or is) TRUE? (A) $y$ must be the successor node of $x$. (B) $y$ must be…

Accepted Answer

核心觀念 二元搜尋樹中，節點 $x$ 的後繼是鍵值大於 $x$ 的所有節點中鍵值最小的節點。 - 若 $x$ 有右子樹，後繼就是右子樹中的最小節點。 - 若 $x$ 沒有右子樹，沿父節點往上走，跳過所有「目前節點是父節點右子節點」的路徑；第一個讓目前節點位於其左側的祖先，就是後繼。 題目已指定最後 $y
e NIL$，表示 $x$ 確實有後繼。 解題方法 分支判斷程式如何找到 $y$： 1. 若 $right[x]
e NIL$，程式令 $y=Tree\Minimum(right[x])$。右子樹中的節點都大於 $x$，其中最小者正是後繼。 2. 若 $right[x]=NIL$，程式從 $x$ 的父節點往上走。只要目前節點是父節點的右子節點，就繼續上爬；停止時，$y$ 是第一個使目前節點位於其左側的祖先。該祖先大於 $x$，且是往上可找到的最小鍵值，因此是後繼。 所以兩種情況都找到 $x$ 的後繼。 選項分析

Question 36

$L$ is a circular linked list. Initially, $L$ is empty. The elements $3,4,5,9,$ and $7$ are appended to $L$ one by one. Assume that $x$ is a node of $L$ . Denote $next[x]$ and $prev[x]$ as the next and previous nodes of $x$ , respectively. $value[x]$ is the element stored in $x$ . Given that $x$ stores element 7. Thus, $value[next[x]]$ and $value[prev[x]]$ are 3 and 9, respectively.

What is $value[x]$ after the following code fragment is executed?

$n=1$

while $n<2020$

$x=next[next[x]]$
$n=n+1$

$x=prev[prev[prev[x]]]$

(A) 3
(B) 4
(C) 5
(D) 9
(E) 7

Accepted Answer

核心觀念 循環鏈結串列的節點會首尾相接，因此沿著 next 前進或沿著 prev 後退，位置都可以用「模節點數」計算。本題共有 $5$ 個節點；每次執行 x=next[next[x]]，等於讓 x 沿 next 前進 $2$ 個節點。 解題方法 依序加入元素後，串列順序為： $$ 3	o4	o5	o9	o7	o3 $$ 初始時 $x$ 指向元素 $7$。迴圈從 $n=1$ 開始，直到 $n=2020$ 時停止，因此共執行 $2019$ 次。每次前進 $2$ 個節點，總共前進： $$ 2	imes2019=4038	ext{ 個節點} $$ 因為串列有 $5$ 個節點，$4038$ 除以 $5$ 餘 $3$，所以迴圈後相當於從 $7$ 沿 next 前進 $3$ 個節點： $$ 7	o3	o4	o5 $$ 接著執行 x=prev[prev[prev[x]]]，從 $5$ 沿 prev 後退 $3$ 個節點： $$ 5	o4	o3	o7 $$

輔助點	角色	加入的邊
$\ell_1$	接兩個 $a$	$(\ell_1,a_1),(\ell_1,a_2)$
$\ell_2$	接 $a$ 與 $x$	$(\ell_2,a_1),(\ell_2,a_2),(\ell_2,x_1),(\ell_2,x_2),(\ell_2,x_3)$
$\ell_3$	接 $x$ 與 $x$	$(\ell_3,x_1),(\ell_3,x_2),(\ell_3,x_3)$
$\ell_4$	接 $x$ 與 $x$	$(\ell_4,x_1),(\ell_4,x_2),(\ell_4,x_3)$

輔助點	角色	加入的邊
$\ell_1$	接兩個 $a$	$(\ell_1,a_1),(\ell_1,a_2)$
$\ell_2$	接 $a$ 與 $x$	$(\ell_2,a_1),(\ell_2,a_2),(\ell_2,x_1),(\ell_2,x_2),(\ell_2,x_3)$
$\ell_3$	接 $x$ 與 $x$	$(\ell_3,x_1),(\ell_3,x_2),(\ell_3,x_3)$
$\ell_4$	接 $x$ 與 $x$	$(\ell_4,x_1),(\ell_4,x_2),(\ell_4,x_3)$

輔助點	角色	加入的邊
$\ell_1$	接兩個 $a$	$(\ell_1,a_1),(\ell_1,a_2)$
$\ell_2$	接 $a$ 與 $x$	$(\ell_2,a_1),(\ell_2,a_2),(\ell_2,x_1),(\ell_2,x_2),(\ell_2,x_3)$
$\ell_3$	接 $x$ 與 $x$	$(\ell_3,x_1),(\ell_3,x_2),(\ell_3,x_3)$
$\ell_4$	接 $x$ 與 $x$	$(\ell_4,x_1),(\ell_4,x_2),(\ell_4,x_3)$

輔助點	角色	加入的邊
$\ell_1$	接兩個 $a$	$(\ell_1,a_1),(\ell_1,a_2)$
$\ell_2$	接 $a$ 與 $x$	$(\ell_2,a_1),(\ell_2,a_2),(\ell_2,x_1),(\ell_2,x_2),(\ell_2,x_3)$
$\ell_3$	接 $x$ 與 $x$	$(\ell_3,x_1),(\ell_3,x_2),(\ell_3,x_3)$
$\ell_4$	接 $x$ 與 $x$	$(\ell_4,x_1),(\ell_4,x_2),(\ell_4,x_3)$

邊	權重	邊	權重
$T$ – $M$	1	$T$ – $C$	4
$L$ – $B$	2	$C$ – $P$	4
$P$ – $R$	2	$L$ – $R$ （上方弧）	5
$P$ – $Q$	2	$C$ – $B$	5
$L$ – $T$	3	$L$ – $M$	6
$M$ – $C$	3	$Q$ – $R$	7
$M$ – $B$	3	$B$ – $Q$	9

109 年 國立陽明交通大學資訊工程學系碩士班《資料結構與演算法》

第 1-(1) 題

第 1-(2) 題

核心觀念

解題方法

第 2-(1) 題

核心觀念

解題方法

選項分析

第 2-(2) 題

核心觀念

解題方法

選項分析

第 2-(3) 題

核心觀念

解題方法

第 3-(1) 題

第 3-(2) 題

第 3-(3) 題

第 3-(4) 題

第 4-(1) 題

第 4-(2) 題

核心觀念

解題方法

選項分析

第 5-(1) 題

核心觀念

解題方法

第 5-(2) 題

第 5-(3) 題

第 6-(1) 題

第 6-(2) 題

第 6-(3) 題

第 7-(1) 題

第 7-(2) 題

第 7-(3) 題

核心觀念

解題方法

選項分析

第 8-(1) 題

核心觀念

解題方法

第 8-(2) 題

核心觀念

解題方法

選項分析

第 8-(3) 題

核心觀念

解題方法

選項分析

第 9-(1) 題

第 9-(2) 題

核心觀念

解題方法

第 9-(3) 題

第 10 題5 分

核心觀念

解題方法

選項分析

第 11-(1) 題

核心觀念

解題方法

選項分析

第 11-(2) 題

核心觀念

解題方法

選項分析

第 12-(1) 題

核心觀念

解題方法

第 12-(2) 題

第 12-(3) 題

第 13-(1) 題

第 13-(2) 題

核心觀念

解題方法

第 14 題5 分

第 15 題5 分

核心觀念

解題方法

109 年國立陽明交通大學資訊工程學系碩士班《資料結構與演算法》