111 年 國立成功大學電腦與通信工程研究所丁組《資料結構》

📄 試題原卷　免費註冊後即可對照原始考卷 PDF免費註冊

第 1 題20 分

  1. (20 pts) True or False (一題一分,答錯一題倒扣一分)
    a. Objective oriented language
    A) A programming language is considered as object-oriented if it supports objects and requires objects belonging to a class.
    B) Abstract makes modifications of program much easier.
    C) Software development time and money can be saved if template is used in a program.
    D) A derived class inherits all the non-private members (data and functions) of the base class including constructor and destructor.
    b. Recursive function
    A) Any program that can be written using assignment, the if-else statement, and the while statement can also be written using assignment, if-else, and recursion.
    B) Merge sort is stable if we use the iterative procedure to implement it. However, it is not stable in the recursive version.
    C) No matter in the recursive version or in the iterative version, the time complexity of merge sort is O(nlog⁡n)O(n \log n), where nn is the number of input.
    D) Merge sort is an in-place algorithm.
    c. Tree
    A) The time complexity to insert a key in to a binary tree is O(log⁡n)O(\log n).
    B) The time complexity to increase a value in a Max-Heap is O(log⁡n)O(\log n).
    C) It will waste n(k−1)+1n(k-1) + 1 fields if we use a list representation to represent each node in a k-ary tree (i.e., a tree of degree k), where each node uses a list with a fixed size k to record its children.
    D) We need an additional node to represent the overall winner in a loser tree and it runs slower than a winner tree.
    d. Graph
    A) 2→32 \to 3 is a strongly connected component of the graph ① 2→42 \to 4
    B) The precedence relation of the edges in an AOV network can be irreflexive.
    C) We can avoid traversing the same edge if the adjacency multilist is used to record a graph.
    D) There exists no backward edge in a breadth-first search tree obtained from a undirected graph.
    e. Stack and queue
    A) The infix expression of the postfix expression " x 4+y7−/z+x \ 4+y7-/z+" is "(x+4)/(y-7)+z".
    B) With postfix notation, there is no need for parentheses because there is no ambiguity.
    C) Evaluating the postfix expression "7 2+5 8 4/ - *" returns 27.
    D) "+*abcd" is a valid prefix expression.

登入後即可作答並保存紀錄。

這一題的完整詳解

一、核心觀念

本題涵蓋五大主題：

  • 物件導向：抽象、樣板、繼承、建構子與解構子。
  • 遞迴與合併排序：遞迴表達能力、穩定性、時間複雜度、額外空間。
  • 樹：二元樹、二元搜尋樹、Max-Heap、kk 元樹與優勝者樹。
  • 圖：強連通分量、AOV 網路、adjacency multilist、BFS。
  • 堆疊與佇列：中序／後序／前序表示法及後序運算。

a. Objective-Oriented Language

A. 正確

在本題採用的傳統「類別導向物件導向」定義中，物件導向語言必須支援物件，且物件應屬於某個類別（class）。類別描述物件的資料與行為，物件則是類別的實例。

因此本敘述正確。

B. 正確

Abstract（抽象化）是將物件的重要特徵與操作介面保留，隱藏不必要的實作細節。

程式使用者只依賴公開介面，不必知道內部如何實作，因此當內部資料結構或演算法修改時，只要介面不變，其他程式通常不必跟著修改。

所以抽象化確實能讓程式修改與維護更容易。

C. 正確

Template（樣板）能將演算法與資料型態泛化，使同一份程式碼適用於多種型態。

例如 C++ 的 template 可以避免為 int、double 等型態重複撰寫相同演算法，因此能減少開發時間與成本。

D. 錯誤

衍生類別會繼承基底類別的非 private 成員，但建構子與解構子不會被繼承。

建構子與解構子的名稱必須與所屬類別相同，且衍生類別通常需要自行定義初始化與資源釋放行為。

因此「包括 constructor 和 destructor」錯誤。

小結

A：T,B：T,C：T,D：F\boxed{\text{A：T,\quad B：T,\quad C：T,\quad D：F}}

b. Recursive Function

A. 正確

任何可由：

  • 指派敘述；
  • if-else；
  • while

構成的程式，都可以使用遞迴模擬。

例如：

while (condition) {
    statement;
}

可改寫成：

function loop() {
    if (condition) {
        statement;
        loop();
    }
}

因此，迴圈可用遞迴取代；反過來，遞迴也能透過明確的 stack 與迴圈模擬。

B. 錯誤

Merge sort 的穩定性取決於合併階段是否在兩個相同鍵值中，優先取左半部元素。

若使用穩定的 merge procedure，則無論採用遞迴或疊代方式實作，都可以保持穩定性。

遞迴版本並不會自然失去穩定性，因此本敘述錯誤。

C. 正確

Merge sort 的遞迴式為：

T(n)=2T(n2)+Θ(n)T(n)=2T\left(\frac n2\right)+\Theta(n)

其中：

  • 2T(n/2)2T(n/2)：分別排序左右兩半；
  • Θ(n)\Theta(n)：合併兩個已排序序列。

由 Master Theorem：

T(n)=Θ(nlog⁡n)T(n)=\Theta(n\log n)

疊代版本雖然沒有遞迴呼叫，但每一層合併仍需 Θ(n)\Theta(n)，且共有 Θ(log⁡n)\Theta(\log n) 層，因此同樣為：

Θ(nlog⁡n)\Theta(n\log n)

D. 錯誤

標準 Merge sort 需要額外陣列儲存合併結果，因此額外空間通常為：

Θ(n)\Theta(n)

所以標準 Merge sort 不是 in-place algorithm。

雖然存在特殊的原地合併技巧，但實作複雜，且一般資料結構課程所指的 Merge sort 並不視為原地演算法。

小結

A：T,B：F,C：T,D：F\boxed{\text{A：T,\quad B：F,\quad C：T,\quad D：F}}

c. Tree

A. 錯誤

若題目所稱 binary tree 是一般二元樹，插入一個鍵值前可能必須搜尋整棵樹，因此最壞時間複雜度為：

O(n)O(n)

只有在「高度為 O(log⁡n)O(\log n) 的平衡二元搜尋樹」中，插入才是：

O(log⁡n)O(\log n)

題目沒有說明樹必定平衡，因此不能直接判定為 O(log⁡n)O(\log n)。

B. 正確

在 Max-Heap 中，若提高某個節點的值，該節點可能大於其父節點，因此需要不斷向上調整（sift-up）。

Heap 的高度為：

O(log⁡n)O(\log n)

每次向上移動一層，因此時間複雜度為：

O(log⁡n)O(\log n)

C. 正確

有 nn 個節點的樹共有 n−1n-1 條邊，因此實際子節點指標數為：

n−1n-1

若每個節點固定配置 kk 個欄位，總欄位數為：

nknk

其中未使用的欄位數為：

nk−(n−1)=nk−n+1=n(k−1)+1nk-(n-1)=nk-n+1=n(k-1)+1

所以本敘述正確。

D. 錯誤

Loser tree 的內部節點記錄比賽中的 loser，另外保存整體 winner。因此它確實需要額外位置記錄最終勝者。

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 2 題10 分

  1. (10 pts) Biconnected components
    a. (2 pts) Please give the definition of a back edge (u, v) in an undirected graph.
    b. (6 pts) Describe the two rules to find the articulation points and explain why they are correct.
    c. (2 pts) Show all biconnected components in the right graph.
    🖼️【此處有附圖，請對照原卷】

登入後即可作答並保存紀錄。

這一題的完整詳解

a. Back edge（回邊）之定義
在無向圖的 DFS 探索中，若從節點 uu 探索到已被 訪問（已在 DFS 樹上）且 非父節點 vv 的邊 (u,v)(u,v)，則此邊稱為 back edge。其特性為 vv 在 DFS 樹中位於 uu 的祖先層次上。

b. 找尋割點（articulation point）之兩條規則與正當性

規則內容為何正確
1. 根節點規則若 DFS 樹的根節點 rr 有 兩條或以上的子樹，則 rr 為割點。根的每條子樹若被移除，必須經過根才能與其他子樹相連；若根只有一條子樹，則移除根不會斷開圖。
2. 非根節點規則對於非根節點 uu，若存在子節點 vv 使得 vv 子樹中所有節點均無 back edge 能回到 uu 的祖先（即 low[v]≥disc[u]low[v] \ge \text{disc}[u]），則 uu 為割點。low[v]≥disc[u]low[v] \ge \text{disc}[u] 表示從 vv 之子樹無法繞過 uu 直接連至更高層的祖先，若移除 uu，該子樹將與其餘圖斷開，故 uu 為割點。
🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 3 題10 分

  1. (10 pts) Tree
    a. (5 pts) Consider the following Huffman coding table: A: 11, B:10, C:001, D: 000, E:01
    Please decode the string "10001110111000" into the source string (note that you have to draw your Huffman code tree first).
    b. (5 pts) Draw the threaded representation of the resulting binary tree in (a) if you want to traverse the graph in pre-order traverse? Note that you need use solid line to point to the predecessor of a node and a dash line to point to the successor of a node.

登入後即可作答並保存紀錄。

這一題的完整詳解

a. 解碼

Huffman 編碼表

A:11,  B:10,  C:001,  D:000,  E:01A:11,\; B:10,\; C:001,\; D:000,\; E:01

逐位讀取 “10001110111000”：

讀取位元配對碼對應字元
10B
000D
11A
10B
11A
10B
000D

得到的來源字串為 BDABABD。

b. 線索二元樹（pre‑order 內線）

Huffman 樹（* 為內部節點）：

        I0
      /    \
    I1      I3
   /  \    /  \
 I2   E   B    A
/  \
D   C
🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 4 題25 分

  1. (25 pts) Shortest path algorithm
    Bellman and Ford algorithm and Floyd-Warshall algorithm both apply the dynamic
    programming to find shortest paths.
    Let DkD^k denote the matrix constructed in the k-th iteration, which is constructed from the
    previous matrix Dk−1D^{k-1}. Let wijw_{ij} denote the weight of an edge ei,je_{i,j}.
    a. (3 pts) Let dikd^k_i denote the shortest path of a node ii from source in the k-th iteration in
    Bellman and Ford algorithm. Please list the equation to estimate an entry dikd^k_i in DkD^k and
    explain the equation shortly.
    b. (3 pts) Let dijkd^k_{ij} denote the shortest path between node ii and node jj in the k-th iteration
    in the Floyd-Warshall Algorithm. Please list the equation to estimate an entry dijkd^k_{ij} in DkD^k
    and explain the equation shortly.
    c. (2 pts) How can you know the graph has a negative cycle in the Bellman and Ford
    Algorithm? Why?
    Johnson's Algorithm finds the shortest paths between all pairs by
    transforming an original graph G to a new graph G' by adding an
    additional node 0 and connecting node 0 to each node in G.
    d. (10 pts) Please show the value of h(v)h(v) of each node vv in G′G'
    which is the shortest path from node 0 (you have to show the
    value of each node in G' in each iteration).
    e. (5 pts) Please show the equation to estimate the new weight
    wij′w'_{ij} of each edge eije_{ij} in G' according h(v)h(v).
    f. (2 pts) In which condition that the Johnson's algorithm can
    perform faster than Floyd- Warshall's algorithm?

登入後即可作答並保存紀錄。

這一題的完整詳解

a. Bellman‑Ford 第 k 次迭代的 dikd_i^{k}

dik=min⁡{dik−1,  min⁡(u,i)∈E(duk−1+wui)}d_i^{k}= \min \left\{ d_i^{k-1},\; \min_{(u,i)\in E}\bigl(d_u^{k-1}+w_{ui}\bigr)\right\}

說明：dikd_i^{k} 為考慮至多 kk 條邊的最短路。若不經過第 kk 條邊則保留 dik−1d_i^{k-1}，否則取所有入邊 (u,i)(u,i) 的前一次距離加上該邊權重的最小值。

b. Floyd‑Warshall 第 k 次迭代的 dijkd_{ij}^{k}

dijk=min⁡(dijk−1,  dikk−1+dkjk−1)d_{ij}^{k}= \min \bigl( d_{ij}^{k-1},\; d_{i k}^{k-1}+d_{k j}^{k-1} \bigr)

說明：在第 kk 次迭代允許路徑經過節點 kk。若不經過 kk，保持 dijk−1d_{ij}^{k-1}；若經過 kk，則使用從 ii 到 kk 再到 jj 的最短子路徑。

c. 判斷負權回路

在第 ∣V∣−1|V|-1 次迭代結束後，若仍有任一邊 (u,v)(u,v) 使

dv∣V∣−1>du∣V∣−1+wuvd_v^{|V|-1}>d_u^{|V|-1}+w_{uv}

則圖中含負權回路。原因：若不存在負環，所有最短路徑最多使用 ∣V∣−1|V|-1 條邊；若仍可改進，表示存在可無限降低成本的回路（負環）。

d. Johnson’s algorithm 中 h(v)h(v) 的求法

在加入虛擬節點 00 並連接至所有原節點後，執行 Bellman‑Ford 從 00 計算最短距離 h(v)=δ0vh(v)=\delta_{0v}。第 kk 次迭代（k=1…∣V∣−1k=1\ldots|V|-1）更新如下（以 VV 為原圖節點集合）：

iteration kk更新的距離 h(v)h(v)（僅列出變化）
k=1k=1h(v)=min⁡{w0v,  w0u+wuv∣(u,v)∈E}h(v)=\min\{w_{0v},\; w_{0u}+w_{uv}\mid (u,v)\in E\}
🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 5 題10 分

  1. (10 pts) Given an input array L={61, 127, 15, 7, 11, 10, 5, 51, 3}, where left and right denote the
    indexes of the first and last elements in the array (i.e., left=0 and right =8).
    a. (5 pts) Quick sort algorithm uses the divide an conquer strategy to sort number. To
    avoid imbalanced partition, we find the pivot in the location estimated by the function
    f() and swap it with the first element in the sub-array in each iteration, where the f()
    function is shown as follows:
    f(right)= 4* right mod N,
    where N is the number of elements in a sub-array (i.e., N=9 in the beginning)
    Please show the resulting arrays after the first and the second iterations in the recursive
    procedure.
    b. (5 pts) Use a 4-basd radix sort to rearrange numbers in the array. Please show the result
    in a bucket list and the resulting array in each iteration.

登入後即可作答並保存紀錄。

這一題的完整詳解

a. Quick‑sort (pivot = f(right)=4⋅right mod Nf(\text{right})=4\cdot\text{right}\bmod N)

  • 初始子陣列 L=[61,127,15,7,11,10,5,51,3]L=[61,127,15,7,11,10,5,51,3], N=9N=9, right=8\text{right}=8
    f(8)=4×8 mod 9=32 mod 9=5f(8)=4\times8\bmod9=32\bmod9=5
    取第 55 個元素 1010 為樞紐，與首元素交換 →

    L=[10‾,127,15,7,11,61,5,51,3]L=[\underline{10},127,15,7,11,61,5,51,3]

    以首元素為樞紐執行 Lomuto 分割，得到

    L(1)=[3,7,5,10‾,11,61,15,51,127]L^{(1)}=[3,7,5,\underline{10},11,61,15,51,127]

    （樞紐 1010 最終位置 p=3p=3，左子陣列 0 ⁣− ⁣20\!-\!2, 右子陣列 4 ⁣− ⁣84\!-\!8）

  • 第二次遞迴：對左子陣列 [3,7,5][3,7,5]（N=3N=3, right=2\text{right}=2）
    f(2)=4×2 mod 3=8 mod 3=2f(2)=4\times2\bmod3=8\bmod3=2
    第 22 個元素 55 為樞紐，與首元素交換 →

    L=[5‾,7,3,10,11,61,15,51,127]L=[\underline{5},7,3,10,11,61,15,51,127]

    分割後得到

    L(2)=[3,5‾,7,10,11,61,15,51,127]L^{(2)}=[3,\underline{5},7,10,11,61,15,51,127]

    （樞紐 55 位置 p=1p=1，子陣列已完成）

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 6 題20 分

  1. (20 pts) 簡答題:
    a. (5 pts) For any nonempty binary tree, T, if no is the number of leaf nodes and n₂ is the
    number of nodes of degree 2. Please show the relation between no and n₂ and prove
    it.
    b. (5 pts) Given the following Keys 62, 104, 67, 22, 103 and a hash table with 10 buckets,
    where each bucket has one slot. Please write down the result using the hash function
    F(x) = (x mod 10). It adopts open addressing when a collision happens according to the
    quadratic residue as follows:
    i = (F(x)+(n+1)²) mod 10 , if n is odd
    i = (F(x)-(n+1)²) mod 10 , if n is even
    where io = F(x) and n denotes the collision number.
    The following figure describes a flow assignment in a flow network G(V, E). The a/b
    notation in each edge respectively denotes the current flow a and capacity b of the edge.
    c. (5 pts) Please show the residual network of the graph. Which algorithm can be used
    to find an augmenting path in the residual network and what is its time complexity?
    d. (5 pts) Please find the minimum cut of a network of the graph and what is the
    maximum flow from S to T?
    🖼️【此處有附圖，請對照原卷】

登入後即可作答並保存紀錄。

這一題的完整詳解

a.
對任意非空二元樹 TT，設

  • n0n_0 為葉節點數（度 0）
  • n1n_1 為度 1 的節點數
  • n2n_2 為度 2 的節點數

樹有 N=n0+n1+n2N=n_0+n_1+n_2 個節點，且邊數為 N−1N-1，故

∑deg⁡(v)=2(N−1)=2n0+2n1+2n2−2.\sum\deg(v)=2(N-1)=2n_0+2n_1+2n_2-2 .

另一方面

∑deg⁡(v)=0⋅n0+1⋅n1+2⋅n2=n1+2n2.\sum\deg(v)=0\cdot n_0+1\cdot n_1+2\cdot n_2=n_1+2n_2 .

兩式相等並整理得

n1+2n2=2n0+2n1+2n2−2⟹n0=n2+1.n_1+2n_2=2n_0+2n_1+2n_2-2\quad\Longrightarrow\quad n_0=n_2+1 .

【答案】 n0=n2+1n_0=n_2+1。

b.
雜湊函數 F(x)=x mod 10F(x)=x\bmod 10，桶數 10，使用二次探測：

鍵 xxF(x)F(x)第 1 次衝突 ii (odd nn)第 2 次衝突 ii (even nn)最終插入位置
622––2
1044––4
677––7
222 → n=1n=1 → (2+(1+1)2)=6(2+(1+1)^2)=66–6
🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 7 題5 分

An available list can be used to recycle unused nodes in a linked list to speed up runtime. Please complete the procedure to recycle a circular list into an available list, pointed by avav, where the circular list has only one pointer, lastlast, pointing to its last node.

void CircularList<T>::~CircularList()
{
// Delete the whole circular list
if (last) {
ChainNode<T>* first = ____;
____ = ____;
____ = ____;
last = 0;
}
}

🖼️【此處有附圖，請對照原卷】

🖼️ 本題含圖表，以下為原卷對應頁面：
原卷第 5 頁

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

這題考循環單向鏈結串列與可用串列的接合。last 指向循環串列的最後一個節點，而 last->link 指向第一個節點；av 指向可用串列的第一個節點。

解題方法

圖中未使用的循環串列由 last 指向尾節點，尾節點的連結回到首節點；可用串列由 av 指向首節點，尾端連結為空。先記住循環串列的首節點，再把循環串列尾端接到原可用串列，最後更新 av 為原循環串列首節點：

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

其他考古題

其他學校的工程科學與其他考古題

臺灣大學130清華大學46政治大學63中央大學4中正大學14臺北大學39