112 年國立成功大學資訊工程系碩士班《程式設計（含資料結構與演算法）》考古題與詳解

Question 1

1. [5%] Which of the following statements is (are) correct? (A) Searching a particular data item in a binary search tree with n nodes requires at most log₂(n+1) comparisons. (B) A full binary tree of a given height h has 2ʰ⁻¹ nodes. (The root is at height of 1.) (C) Represent a binary tree in an one-dimensional array (say, a[]). Assume the root is stored in a[1]. Then, the index of node i's parent is floor(i/2). (D) AVL, red-black tree and compressed trie are binary trees.

Accepted Answer

(A) 銀行搜尋樹的最壞情況高度可達 $n$，比較次數上限須以樹高計算，不能保證不超過 $\log2 (n+1)$ → 錯。 (B) 完全（perfect）二元樹在高度 $h$ 時節點數為 $2^{h}-1$；若僅是「full」二元樹，節點數也不等於 $2^{h-1}$ → 錯。

Question 2

2. [5%] The following graph is a maximum heap. After removing the maximum element, which of the followings is (are) true? 🖼️【此處有附圖，請對照原卷】 (A)30 is a leaf node in the resultant heap after removal. (B) Suppose we use an array to implement the heap. The 5th element in the array is 30. (C) In the post-order traversal, 55 is before 42. (D)25 is at same indexing position in the array for the post-order and in-order traversals. (E) The complexity of removal is O(log n), where n is the number of data items in the heap.

Accepted Answer

核心觀念 最大堆是完全二元樹，且每個父節點的值都不小於子節點。刪除最大值時，先移除根節點，再把最後一個節點移到根部，接著沿著較大的子節點向下調整，直到恢復堆序。 以陣列表示完全二元樹時，若根節點位於索引 $1$，索引 $i$ 的左右子節點分別位於 $2i$ 與 $2i+1$。 解題方法 依圖中由上而下、由左而右排列，原最大堆的陣列為： $$ [85,55,25,11,42,17,19,3,1,35,30] $$ 刪除根節點 $85$，將最後一個元素 $30$ 移到根部，並從根開始向下調整： 1. $30$ 與子節點 $55、25$ 比較，和較大的 $55$ 交換。 2. $30$ 與子節點 $11、42$ 比較，和較大的 $42$ 交換。 3. $30$ 與子節點 $35$ 比較，和 $35$ 交換。 因此刪除後的堆為： $$ [55,42,25,11,35,17,19,3,1,30] $$ 選項分析

Question 3

3. [5%] Given a graph G as depicted as follows. T is minimum spanning tree (MST) of G. Which of the following descriptions is (are) true? 🖼️【此處有附圖，請對照原卷】 (A) Perform Prim's algorithm to find the MST, starting from node L. The last edge included into the MST is (A, B). (B) The minimum spanning tree for G is unique. (C) If let G2 be G by excluding the edge (M, E), then the G2's MST is identical to G's. (D) Let G3 be G2 removing the edge (B, F). The MSTs' of G2 and G3 are identical.

Accepted Answer

核心觀念 最小生成樹（MST）是在連通圖中連接所有頂點、總權重最小的生成樹。含 $n$ 個頂點的生成樹恰有 $n-1$ 條邊。Kruskal 演算法依權重由小到大選邊，遇到會形成環的邊就略過；Prim 演算法則從指定頂點開始，每次選擇連接樹內與樹外頂點的最小權重邊。 解題方法 圖中有 9 個頂點；讀得各邊及權重如下：$(A,B)=13$、$(A,L)=17$、$(B,G)=4$、$(B,F)=20$、$(G,F)=16$、$(L,F)=16$、$(L,D)=17$、$(F,D)=8$、$(F,H)=9$、$(D,H)=7$、$(D,M)=9$、$(M,E)=9$、$(H,E)=14$。 用 Kruskal 演算法依序選邊： 1. 選 $(B,G)=4$、$(D,H)=7$、$(D,F)=8$。 2. 權重為 9 的邊中，選 $(D,M)=9$、$(M,E)=9$；略過 $(F,H)=9$，因為 $F,D,H$ 已連通，加入該邊會形成環。 3. 接著選 $(A,B)=13$。 4. 選 $(G,F)=16$、$(L,F)=16$，將尚未連接的部分接起來。 因此 MST 邊集合為 $$ \{(B,G),(D,H),(D,F),(D,M),(M,E),(A,B),(G,F),(L,F)\}. $$

Question 4

4. [5%] Given an AVL tree as follows, we perform the operations (A), (B), (C), (D) and (E), independently. Which of these operations would result in the tree to be unbalanced, and shall be restructured? 🖼️【此處有附圖，請對照原卷】 (A) insert 18 (B) insert 33 (C) insert 38 (D) delete 35 (E) delete 22

Accepted Answer

核心觀念 AVL 樹要求每個節點的左右子樹高度差至多為 $1$。節點的平衡因子定義為 $$ BF(v)=h(	ext{左子樹})-h(	ext{右子樹}) $$ 若 $|BF(v)|1$，該節點失衡，必須旋轉重平衡。以下採用空子樹高度 $0$、葉節點高度 $1$；五個操作都各自從原始樹開始。 解題方法 原圖的結構是：根節點 $22$；左子節點 $17$，而 $17$ 只有右子節點 $20$；右子節點 $35$，而 $35$ 只有右子節點 $36$。先依二元搜尋樹規則插入或刪除，再由受影響的節點往根部檢查高度差；只有出現 $|BF|1$ 才需要重平衡。 原始樹中，$17$ 與 $35$ 的高度都是 $2$，因此根節點 $22$ 的左右子樹高度相同。接著逐一看各操作造成的變化。 選項分析 - (A) 插入 18：正確。 搜尋路徑為 $22	o17	o20$，$18$ 成為 $20$ 的左子節點。此時 $20$ 的高度為 $2$，而 $17$ 左子樹高度為 $0$、右子樹高度為 $2$，所以 $|BF(17)|=2$，必須重平衡。這是右左型失衡：先對 $20$ 右旋，再對 $17$ 左旋。

Question 5

5. [5%] Suppose we have a Red-Black tree as shown below. Let us insert 6, 14 and 11 in order. Which of the following statements is (are) correct? 🖼️【此處有附圖，請對照原卷】 (A) The resultant Red-Black tree contains 6 red nodes. (B) The color of node of value 8 is black. (C) The color of node of value 14 is red. (D) The parent's value of node of value 7 is 3. (E) The children of node of value 10 are red nodes.

Accepted Answer

核心觀念 紅黑樹插入新節點時，先依二元搜尋樹規則插入紅色節點，再檢查紅黑樹性質。若新節點的父節點也是紅色，就依父、祖父與叔叔節點的顏色進行重新著色或旋轉；紅黑樹中的空節點（NIL）視為黑色。 本題插入順序為 $6、14、11$。每次插入後，只需處理受影響的局部子樹。樹高為 $O(\log n)$，所以插入時間為 $O(\log n)$，旋轉與重新著色使用 $O(1)$ 額外空間。 解題方法 初始樹中，根節點 $10$ 為黑色；$8$ 為紅色；$3、9、15$ 為黑色；$7、13、22$ 為紅色。 1. 插入 $6$ 按二元搜尋樹順序，$6$ 插在 $7$ 的左側。此時父節點 $7$ 是紅色，祖父節點 $3$ 是黑色，叔叔節點是黑色的 NIL。這是「右子節點的左子節點」情形：先對 $7$ 右旋，再將 $6$ 染黑、$3$ 染紅，並對 $3$ 左旋。 $8$ 左側的子樹因此成為：$6$ 為黑色，左子節點 $3$ 與右子節點 $7$ 為紅色。 2. 插入 $14$ $14$ 插在 $13$ 的右側。父節點 $13$ 與叔叔節點 $22$ 都是紅色，因此將 $13、22$ 改為黑色，祖父節點 $15$ 改為紅色，不需旋轉。$14$ 保持紅色。 3. 插入 $11$

Question 6

6. [5%] Which of the following statements is (are) correct? (A) The maximum number of data items stored in an m-way search tree is mᵇ⁻¹, where h is the height of the tree. (B) An 2-3-4 tree is a B-tree of order 5. (C) Any internal node (excluding the root) has at a least ceil(m/2) children in an B-tree of order m. (D) The external nodes on the same level in an B-tree. (E) An Red-Black tree is a binary tree form of an 2-3 tree.

Accepted Answer

題意排版說明 A 的公式依標準題意解讀為 $m^h-1$；D 的句子缺少謂語，解讀為「B-tree 的所有 external nodes 位於同一層」。 核心觀念 - 一棵 $m$-way search tree 的每個節點最多有 $m$ 個子樹，因此最多存放 $m-1$ 個資料項目。 - 一棵 order $m$ 的 B-tree，每個節點最多有 $m$ 個子節點；除根節點外的內部節點至少有 $\lceil m/2\rceil$ 個子節點。 - B-tree 的所有葉節點都位於相同深度。 - 標準 Red-Black tree 對應的是 $2$-$3$-$4$ tree。 解題方法 逐一將各選項與上述定義、公式比較即可判斷。 選項分析 (A) 正確 假設高度 $h$ 表示樹的層數。為使資料項目數量最大，每一層都必須完全展開： - 第 $0$ 層有 $1$ 個節點； - 第 $1$ 層有 $m$ 個節點； - 第 $i$ 層有 $m^i$ 個節點； - 每個節點最多存放 $m-1$ 個資料項目。 因此最大資料項目數為 $$ \sum{i=0}^{h-1}(m-1)m^i =(m-1)\frac{m^h-1}{m-1} =m^h-1. $$ 所以 (A) 正確。 (B) 錯誤 $2$-$3$-$4$ tree 的節點可能具有： - $2$ 個子節點； - $3$ 個子節點； - $4$ 個子節點。 因此它的最大子節點數為 $4$，所以是 order $4$ 的 B-tree，而不是 order $5$ 的 B-tree。 (C) 正確 在 order $m$ 的 B-tree 中：

Question 7

7. [5%] A hash table in size of 10 adopts open addressing with linear probing, where its hash function is defined as h(k)=k%10. The table is initially empty. We insert 6 data items into the table, resulting in the following table. Which of the following choices gives a possible order for inserting the data items to the table? 🖼️【此處有附圖，請對照原卷】 (A) 32, 14, 53, 26, 22, 43 (B) 42, 22, 13, 26, 53, 32 (C) 22, 43, 14, 32, 53, 26 (D) 43, 22, 14, 26, 32, 53 (E) 14, 43, 22, 32, 26, 53

Accepted Answer

核心觀念 線性探測的開放定址法先計算 $h(k)=k\bmod 10$。若該位置已被占用，就依序檢查下一格，直到找到空格；索引會在 $9$ 之後回到 $0$。插入後，每個數值所在的位置會受到先前插入項目的影響。 解題方法 圖中的雜湊表為： | 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |---|---|---|---|---|---|---|---|---|---|---| | 數值 | 空 | 空 | 22 | 43 | 14 | 32 | 26 | 53 | 空 | 空 | 依序模擬各選項的插入，檢查最後能否得到這個表。 選項分析 - (A) 錯誤。 32 的雜湊位置是 $2$。依序插入時，32 會先放在索引 2，無法形成題圖中的配置。 - (B) 錯誤。 此選項含有 42、13，但題圖中的數值是 43、14，插入的項目就與表格不符。 - (C) 錯誤。 22、43、14、32 依序占據索引 2、3、4、5。

Question 8

8. [5%] Consider an Min-Max heap represented as an array [3, 20, 13, 6, 5, 4, 8, 10, 15, 12, 9, 7]. If we exchange any two values X and Y in the array, which of the choices is (are) NOT Min-Max heap(s)? (A) 5 and 7 (B) 4 and 9 (C) 8 and 9 (D) 13 and 9 (E) 5 and 10

Accepted Answer

最小‑最大堆的性質： - 偶數層（根層 0）為 min 層，節點的值必須 不大於 所有子孫； - 奇數層為 max 層，節點的值必須 不小於 所有子孫。 - 同層的祖先（相隔兩層）必須保持相同的比較方向： min‑層節點 ≤ 其父（max‑層）且 ≤ 祖父（min‑層） max‑層節點 ≥ 其父（min‑層）且 ≥ 祖父（max‑層） 原始陣列（索引從 1 起） 1:3、2:20、3:13、4:6、5:5、6:4、7:8、8:10、9:15、10:12、11:9、12:7 已符合上述規則。 檢查每個交換： | 交換 | 影響節點 | 判斷 | |------|----------|------| | (A) 5 ↔ 7 (idx5 ↔ idx12) | idx5 成 7（min 層） ≤ 其子 12、9 ✔；

Question 9

9. [5%] Suppose we have a Patricia trie as shown below. Let us insert 0110 into and then delete 1100 from the trie. What does node 1101 point to? 🖼️【此處有附圖，請對照原卷】 (A) 0001 (B) 0110 (C) 0011 (D) 1001 (E) 1000

Accepted Answer

核心觀念 Patricia trie 會依節點標示的測試位元決定搜尋分支，並以回指連到已存的鍵值。回指不代表一般樹中的子樹關係，因此刪除節點時，要依照指標連結調整，而不能把它當成刪除整個子樹。 解題方法 圖中可讀到：1101 的兩個指標原本分別連到 0011 和 1001；1100 的兩個指標分別回指自身與 1101，而 1001 有指標連到 1100。 插入 0110 後，1101 原本連到 0011 的左指標改連到 0110；另一個指標仍連到 1001。接著刪除 1100，將 1001 原本指向 1100 的指標改接 1101。這只調整了 1001 的指標，不會改變 1101 指向 1001 的指標。

Question 10

Please identify which of the following statement(s) is (are) true.

(A) Tries outperform digital search trees in terms of the number of comparison operations performed.
(B) Compared with tries, compressed tries take less storage overhead.
(C) Patricia outperforms compressed tries in terms of storage overhead.
(D) Both Patricia and digital search trees take the identical complexity of storage overhead.
(E) Patricia outperforms digital search trees in terms of the number of comparison operations performed.

Accepted Answer

核心觀念 本題比較四種數位搜尋結構：Trie、compressed trie、Patricia 與 digital search tree（DST），重點是搜尋時的比較次數，以及節點數所造成的額外空間開銷。 Trie 依照搜尋鍵的字元或位元逐層往下走，主要做的是數位比較；DST 在節點中存放鍵，搜尋時會逐節點檢查鍵是否相符。Patricia 則略過不分歧的位元位置，並在節點記錄分歧位置。對有 $n$ 個鍵的二元 compressed trie，葉節點有 $n$ 個，分歧內部節點至多 $n-1$ 個，因此節點數至多為 $2n-1$；Patricia 與 DST 的節點數皆為 $\Theta(n)$。 解題方法 先分開比較兩件事： 1. 比較次數：區分逐字元／位元的數位檢查，與逐節點進行的整鍵比較。Trie 沿鍵的數位前進，不必在每一層把搜尋鍵和節點中的完整鍵相比；DST 會在搜尋路徑上檢查節點所存的鍵。Patricia 透過跳過不分歧的位置，減少搜尋路徑上的比較。 2. 空間開銷：compressed trie 合併只有單一子節點的路徑，比未壓縮 Trie 少用節點；Patricia 進一步以分歧位置導引搜尋，節點開銷較低。若只看漸近複雜度，Patricia 與 DST 的節點空間同為 $\Theta(n)$。 選項分析

Question 11

Use the master method to give tight asymptotic bounds for the following recursive $T(n)=27T(n/3)+\Theta(n^3/\lg n)$. Assume that $T(n)$ is a constant for sufficiently small $n$.

Accepted Answer

核心觀念

本題考查主定理（Master Theorem）及其對數邊界情形。對遞迴式

T(n)=aT(n/b)+f(n)

先比較 $f(n)$ 與臨界函數 $n^{\log_b a}$ 。本題參數為 $a=27$ 、 $b=3$ ，因此

n^{\log_3 27}=n^3.

題目的非遞迴成本為 $f(n)=\Theta(n^3/\lg n)$ ，比臨界函數少一個 $\lg n$ 因子。這是擴充版主定理的邊界情形：當 $f(n)=\Theta(n^d/\lg n)$ 且 $d=\log_b a$ 時，解的量級為 $\Theta(n^d\lg\lg n)$ 。

解題方法

比較 $f(n)$ 與臨界函數：

f(n)=\Theta\left(\frac{n^3}{\lg n}\right), \qquad n^{\log_3 27}=n^3.

每個遞迴層級的總成本可用遞迴樹計算。第 $i$ 層有 $27^i$ 個子問題，每個子問題大小為 $n/3^i$ ，所以該層總成本為

Question 12

The following procedure is a bottom-up method for matrix chain order. This procedure assumes that matrix $A_i$ has dimensions $p_{i-1}\times p_i$ for $i=1,2,\ldots,n$ . Its input is a sequence $p=(p_0,p_1,\ldots,p_n)$ , where $p.\text{length}=n+1$ . Let $m[i,j]$ be the minimum number of scalar multiplications needed to compute the matrix $A_iA_{i+1}\cdots A_j$ . The procedure uses an auxiliary table $m[1\ldots n,1\ldots n]$ for storing the $m[i,j]$ costs and another auxiliary table $s[1\ldots n-1,2\ldots n]$ that records which index of $k$ achieved the optimal cost in computing $m[i,j]$ . Please fill in the empty statements.

$n=p.\text{length}-1$

Let $m[1\ldots n,1\ldots n]$ and $s[1\ldots n-1,2\ldots n]$ be new tables.

For $i=1$ to $n$ :
$m[i,i]=0$

For $l=2$ to $n$ // $l$ is the chain length

For $i=1$ to $n-l+1$ :
$j=$ ____ (a) (3%)
$m[i,j]=\infty$

For $k=i$ to $j-1$ :
$q=$ ____ (b) (4%)
If $q<m[i,j]$ :
$m[i,j]=q$
$s[i,j]=$ ____ (c) (3%)

Accepted Answer

核心觀念 矩陣鏈乘法的目標，是在不改變矩陣相乘順序的前提下，選擇括號化方式，使純量乘法次數最少。令 $m[i,j]$ 表示計算 $AiA{i+1}\cdots Aj$ 的最少純量乘法次數；若最後一次乘法在 $Ak$ 與 $A{k+1}$ 之間切開，則成本為 $$ m[i,k]+m[k+1,j]+p{i-1}pkpj $$ 其中最後一項是將 $p{i-1}	imes pk$ 矩陣與 $pk	imes pj$ 矩陣相乘所需的純量乘法次數。 解題方法 圖中給出矩陣 $Ai$ 的維度為 $p{i-1}	imes pi$，並以 $m$ 表記錄最少成本、以 $s$ 記錄達成最少成本的切分位置 $k$。演算法依鏈長 $l$ 由短到長填表，先設定區間右端點 $j$，再枚舉所有切分點 $k$。 因此三個空格依序為： - (a) $i+l-1$：鏈長為 $l$、起點為 $i$ 時，終點是 $j=i+l-1$。 - (b) $m[i,k]+m[k+1,j]+p{i-1}pkpj$：切分於 $k$ 的總成本。 - (c) $k$：記錄使成本達到目前最小值的切分點。 關鍵程式碼如下：

Question 13

Illustrate the operation of HEAPSORT on the array $S=[5,13,2,25,7,17,20,8,4]$.

Accepted Answer

核心觀念 堆積排序（Heapsort）先把陣列整理成最大堆積，再反覆將堆頂最大值移到陣列尾端，並對剩餘部分重新維持最大堆積，最後得到遞增排序。 以 1 起始索引表示陣列時，節點 $i$ 的左、右子節點分別是 $2i$ 與 $2i+1$。最大堆積要求每個父節點的值都不小於子節點。含 $n$ 個元素的堆積，其最後一個非葉節點是 $\lfloor n/2\rfloor$，因此建堆時從該位置往前逐一調整。 解題方法 採用最大堆積搭配遞增排序。先由底向上建堆，再逐次交換堆頂與未排序區間的最後一個元素，並將新的堆頂向下調整。 一、建立最大堆積 初始陣列為： $$ [5,13,2,25,7,17,20,8,4] $$ 最後一個非葉節點為 $\lfloor 9/2\rfloor=4$，從索引 $4$ 開始往前調整： - 索引 $4$ 的值為 $25$，子節點為 $8、4$，不需調整。 - 索引 $3$ 的值為 $2$，子節點為 $17、20$，與較大的子節點 $20$ 交換。 - 索引 $2$ 的值為 $13$，與較大的子節點 $25$ 交換；接著檢查新位置，無需再調整。 - 索引 $1$ 的值為 $5$，先與較大的子節點 $25$ 交換，再與子節點 $13$ 交換，最後與子節點 $8$ 交換。 建堆後： $$ [25,13,20,8,7,17,2,5,4] $$ 二、反覆取出最大值 每一行中，直線左側是尚未排序的堆積，右側是已排序區間。每輪先交換堆頂與堆積末端，再將新堆頂向下調整。 | 輪次 | 交換並調整後的陣列 | |---|---| | 初始最大堆積 | $[25,13,20,8,7,17,2,5,4]$ | | 取出 $25$ | $[20,13,17,8,7,4,2,5\mid25]$ | | 取出 $20$ | $[17,13,4,8,7,5,2\mid20,25]$ | | 取出 $17$ | $[13,8,4,2,7,5\mid17,20,25]$ | | 取出 $13$ | $[8,7,4,2,5\mid13,17,20,25]$ | | 取出 $8$ | $[7,5,4,2\mid8,13,17,20,25]$ | | 取出 $7$ | $[5,2,4\mid7,8,13,17,20,25]$ |

Question 14

We are given a sequence $K=(k1,k2,\ldots,kn)$ of $n$ distinct keys in sorted order (so that $k1<k2<\cdots<kn$), and we wish to build a binary search tree from these keys. For each key $ki$, we have a probability $pi$ that a search will be for $ki$. Some searches may be for values not in $K$, and so we also have $n+1$ “dummy keys” $d0,d1,\ldots,dn$ representing values not in $K$. In particular, $d0$ represents all values less than $k1$, $dn$ represents all values greater than $kn$, and for $i=1,2,\ldots,n-1$, the dummy key $di$ represents all values between $ki$ and $k{i+1}$. For each dummy key $di$, we have a probability $qi$ that a search will correspond to $di$. Determine the cost and structure of an optimal binary search tree in the expected cost of search time for a set of $n=7$ keys w…

Accepted Answer

核心觀念 這題考的是最佳二元搜尋樹（Optimal Binary Search Tree, OBST）。搜尋成功的機率為 $pi$，搜尋失敗的機率為 $qi$；目標是安排樹的結構，使搜尋所需比較次數的期望值最小。 令 $e[i,j]$ 表示由 $ki,\ldots,kj$ 建成的最佳搜尋樹，其期望成本；令 $w[i,j]$ 為該區間內所有成功與失敗搜尋的總機率。空區間的成本為： $$ e[i,i-1]=q{i-1} $$ 若選 $kr$ 為根，左右子樹中的每次搜尋都會多比較根 $kr$ 一次，因此： $$ e[i,j] = \min{i\le r\le j} \left\{ e[i,r-1]+e[r+1,j]+w[i,j] ight\} $$ 其中： $$ w[i,j]=\sum{m=i}^{j}pm+\sum{m=i-1}^{j}qm $$ 解題方法 依區間長度由短到長計算動態規劃。先計算單一鍵的區間，再逐步擴大區間；每個區間都試選其中一個鍵作為根，保留成本最低者。 為方便列算，以下將機率乘以 $100$，所以表中成本單位為 $0.01$。例如表中 $312$ 代表期望成本 $3.12$。 | 區間長度 | 區間成本 $e[i,j]$ | |---|---| | 1 | $[1,1]:28,\ [2,2]:30,\ [3,3]:30,\ [4,4]:24,\ [5,5]:30,\ [6,6]:32,\ [7,7]:34$ | | 2 | $[1,2]:62,\ [2,3]:68,\ [3,4]:57,\ [4,5]:57,\ [5,6]:72,\ [6,7]:78$ | | 3 | $[1,3]:100,\ [2,4]:93,\ [3,5]:102,\ [4,6]:101,\ [5,7]:120$ | | 4 | $[1,4]:134,\ [2,5]:141,\ [3,6]:148,\ [4,7]:155$ | | 5 | $[1,5]:183,\ [2,6]:196,\ [3,7]:213$ | | 6 | $[1,6]:244,\ [2,7]:261$ | | 7 | $[1,7]:312$ | 以區間 $[1,4]$ 為例，$w[1,4]=49$。比較各鍵作為根的成本： $$ \begin{aligned} r=1 &: \quad q0+e[2,4]+w[1,4]=6+93+49=148\ r=2 &: \quad e[1,1]+e[3,4]+w[1,4]=28+57+49=134\ r=3 &: \quad e[1,2]+e[4,4]+w[1,4]=62+24+49=135\ r=4 &: \quad e[1,3]+q4+w[1,4]=100+5+49=154 \end{aligned} $$ 因此 $[1,4]$ 的根為 $k2$，成…

Question 15

The following graph is about the maximum flow problem. Each edge is labeled with its capacity. What is the maximum flow from vertex $s$ to vertex $t$? 🖼️【此處有附圖，請對照原卷】

Accepted Answer

核心觀念 最大流問題要在每條有向邊的容量限制下，讓從 $s$ 流出的總流量最大。依據最大流最小割定理，最大流量等於所有 $s$-$t$ 割中容量最小者；割的容量是由源點側通往另一側的邊容量總和。 解題方法 圖中可讀出的邊與容量為：$s	o1$ 為 $18$、$s	o2$ 為 $16$、$2	o1$ 為 $6$、$1	o3$ 為 $16$、$3	o2$ 為 $19$、$2	o4$ 為 $14$、$4	o3$ 為 $7$、$3	o t$ 為 $22$、$4	o t$ 為 $8$。 先取割的源點側為 $\{s,1,2\}$，另一側為 $\{3,4,t\}$。跨越此割、由源點側流向另一側的邊只有 $1	o3$ 和 $2	o4$，所以割容量為 $$ 16+14=30 $$

$i$	0	1	2	3	4	5	6	7
$p_i$		0.04	0.06	0.08	0.02	0.10	0.12	0.14
$q_i$	0.06	0.06	0.06	0.06	0.05	0.05	0.05	0.05

112 年國立成功大學資訊工程系碩士班《程式設計（含資料結構與演算法）》

第 1 題5 分

第 2 題5 分

第 3 題5 分

第 4 題5 分

第 5 題5 分

第 6 題5 分

第 7 題5 分

第 8 題5 分

第 9 題5 分

第 10 題5 分

第 11 題10 分

核心觀念

解題方法

第 12 題10 分

第 13 題10 分

核心觀念

解題方法

一、建立最大堆積

二、反覆取出最大值

第 14 題10 分

核心觀念

解題方法

第 15 題10 分

其他考古題

112 年成功大學的其他科目

成功大學《程式設計》其他年度

其他學校的資工系考古題

112 年 國立成功大學資訊工程系碩士班《程式設計（含資料結構與演算法）》

第 1 題5 分

第 2 題5 分

第 3 題5 分

第 4 題5 分

第 5 題5 分

第 6 題5 分

第 7 題5 分

第 8 題5 分

第 9 題5 分

第 10 題5 分

第 11 題10 分

核心觀念

解題方法

第 12 題10 分

第 13 題10 分

核心觀念

解題方法

一、建立最大堆積

二、反覆取出最大值

第 14 題10 分

核心觀念

解題方法

第 15 題10 分

其他考古題

112 年成功大學的其他科目

成功大學《程式設計》其他年度

其他學校的資工系考古題

112 年國立成功大學資訊工程系碩士班《程式設計（含資料結構與演算法）》