115 年 國立成功大學電機工程學系碩士班戊組《資料結構》

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

第 Problem 1 題20 分

A hospital emergency department treats patients based on urgency (severity score).

(a) [4 pts] In terms of Time Complexity, state the primary advantage of using a Priority Queue over a standard FIFO Queue for finding the next patient to treat.

(b) [4 pts] Assume a Max-Heap. Insert the following patients in this order (Severity Scores): P1(3), P2(5), P3(2), P4(4).
Draw the final heap structure (tree view) below.

(c) [2 pts] Starting from the result in (b), show the array representation of the heap after two extract-max operations have been performed.

(d) [6 pts] The time complexity of Heap operations is determined by the tree structure. Answer the following:

  1. What is the height of a binary heap with nn nodes?
  2. In a worst-case Insert, how many swaps occur relative to the height?
  3. If we used a Sorted Array instead, what would be the complexity of Insert?

(e) [4 pts] To prevent "starvation" of low-severity patients, the system increases a patient's priority based on wait time. Name or briefly describe one mechanism to implement this efficiently.

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

這一題的完整詳解

核心觀念

本題考查：

  • Priority Queue 與 FIFO Queue 的差異
  • Max-Heap 的插入與上浮（sift-up）
  • Extract-Max 與下沉（sift-down）
  • Binary Heap 的高度與時間複雜度
  • Sorted Array 的插入成本
  • 透過 Aging 機制避免低優先權元素 starvation

Max-Heap 必須滿足：

  1. 完全二元樹：除最後一層外，每層皆填滿，最後一層由左至右排列。
  2. Heap-order property：每個父節點的鍵值皆大於或等於其子節點。

因此，最大值永遠位於根節點。

解題方法

(a) Priority Queue 的主要優勢

若要找出下一位應接受治療的最高嚴重度患者：

  • 使用一般 FIFO Queue，只能按照進入順序取出患者；若要找最高嚴重度，必須掃描所有患者，時間複雜度為
O(n)O(n)
  • 使用以 Max-Heap 實作的 Priority Queue，最高嚴重度患者位於根節點，可直接取得，時間複雜度為
O(1)O(1)

若要將患者正式移除，執行 Extract-Max，時間複雜度為

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

因此，Priority Queue 能將「尋找最高優先權患者」由 O(n)O(n) 降至 O(1)O(1)；若包含取出操作，則為 O(log⁡n)O(\log n)。

(b) 依序插入患者並建立 Max-Heap

插入順序為：

P1(3), P2(5), P3(2), P4(4)P1(3),\ P2(5),\ P3(2),\ P4(4)

插入 P1(3)P1(3)

[P1(3)][ P1(3) ]

插入 P2(5)P2(5)

先放入下一個可用位置，再與父節點比較：

[P1(3), P2(5)][ P1(3),\ P2(5) ]

因為 5>35>3，兩者交換：

[P2(5), P1(3)][ P2(5),\ P1(3) ]

插入 P3(2)P3(2)

[P2(5), P1(3), P3(2)][ P2(5),\ P1(3),\ P3(2) ]

P3(2)P3(2) 小於父節點 P2(5)P2(5)，不需交換。

插入 P4(4)P4(4)

先放在 P1(3)P1(3) 的左子節點：

[P2(5), P1(3), P3(2), P4(4)][ P2(5),\ P1(3),\ P3(2),\ P4(4) ]

因為 4>34>3，交換 P4P4 與 P1P1：

[P2(5), P4(4), P3(2), P1(3)][ P2(5),\ P4(4),\ P3(2),\ P1(3) ]

最終樹狀結構為：

          P2(5)
         /     \
      P4(4)   P3(2)
      /
   P1(3)

(c) 執行兩次 Extract-Max 後的陣列

初始 Heap 陣列為：

[P2(5), P4(4), P3(2), P1(3)][ P2(5),\ P4(4),\ P3(2),\ P1(3) ]

第一次 Extract-Max

移除根節點 P2(5)P2(5)，將最後一個節點 P1(3)P1(3) 移至根部：

[P1(3), P4(4), P3(2)][ P1(3),\ P4(4),\ P3(2) ]

此時 P1(3)P1(3) 小於子節點 P4(4)P4(4)，因此下沉交換：

[P4(4), P1(3), P3(2)][ P4(4),\ P1(3),\ P3(2) ]

第二次 Extract-Max

移除根節點 P4(4)P4(4)，將最後一個節點 P3(2)P3(2) 移至根部：

[P3(2), P1(3)][ P3(2),\ P1(3) ]

因為 P3(2)<P1(3)P3(2)<P1(3)，下沉交換：

[P1(3), P3(2)][ P1(3),\ P3(2) ]

因此，兩次 Extract-Max 後的陣列表示為：

[P1(3), P3(2)]\boxed{[P1(3),\ P3(2)]}
🔒

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

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

免費註冊

第 Problem 2 題20 分

A text editor supports Undo/Redo operations.

(a) [6 pts] Complexity Analysis:
Suppose the text cursor is positioned in the middle of a large document (n characters). The user types a character and then immediately presses Undo.

  1. State the Time Complexity of this Undo for an Array List.
  2. State the Time Complexity of this Undo for a Linked List.
  3. Briefly explain why the Array List has this complexity:

(b) [4 pts] Draw the logical structure of the list after the following sequence. Clearly indicate where the "Current" pointer is located.
Sequence: Type A → Type B → Type C → Undo → Undo → Type D

(c) [4 pts] A user performs an Undo, and then immediately types a new character. What happens to the "Redo" history? (Answer in 1 sentence).

(d) [6 pts] Compare the Time Complexity in the table below:

OperationLinked ListArray List
Insert at Current Pointer
Access i-th element

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

這一題的完整詳解

核心觀念

本題考查兩類線性串列的操作成本，以及文字編輯器 Undo／Redo 的狀態管理：

  • Array List：元素連續存放於陣列中；在中間插入或刪除時，必須搬移後方元素。
  • Linked List：元素以節點串接；若已持有目前位置的節點指標，插入或刪除只需修改少數連結。
  • Undo：撤銷最近一次操作。
  • Redo：保存已被 Undo、且尚未被新操作取代的操作。

以下假設「Current pointer」直接指向目前游標位置的節點或陣列索引。

(a) Complexity Analysis

1. Array List 的 Undo

O(n)O(n)

2. Linked List 的 Undo

O(1)O(1)

此答案建立在 Linked List 已持有目前位置節點指標的前提下。

3. Array List 為何是 O(n)O(n)？

游標位於長度為 nn 的文件中間。輸入一個字元時，Array List 必須在中間位置插入元素，為維持陣列的連續排列，後方約有一半元素需要向右搬移：

插入成本=O(n)\text{插入成本} = O(n)

接著執行 Undo，必須刪除剛才插入的字元。刪除中間元素後，後方元素需要向左搬移：

撤銷成本=O(n)\text{撤銷成本} = O(n)

因此整個「輸入字元後立即 Undo」的成本為：

O(n)+O(n)=O(n)O(n) + O(n) = O(n)

注意，兩個線性成本相加後仍是 O(n)O(n)，不是 O(n2)O(n^2)。

若使用 Linked List，已知要撤銷的節點位置，只需調整前後節點的連結，因此刪除該節點為：

O(1)O(1)

(b) 操作後的邏輯結構

依序執行：

  1. Type A：A
  2. Type B：A → B
  3. Type C：A → B → C
  4. Undo：撤銷 C，剩下 A → B
  5. Undo：撤銷 B，剩下 A
  6. Type D：在目前位置輸入 D

最後的串列為：

Head
  ↓
[A] → [D] → NULL
              ↑
           Current

因此：

  • 串列內容為 A → D
  • Current pointer 位於 D 節點，也就是目前游標位於字元 D 之後
  • 第二次 Undo 後，原本的 B 已進入 Redo 歷史；但輸入 D 後，該 Redo 歷史會被清除，詳見 (c)

(c) Undo 後輸入新字元

執行 Undo 後若立即輸入新字元，原本的 Redo 歷史會被清除，因為編輯器已經建立新的操作分支。

(d) 時間複雜度比較

🔒

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

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

免費註冊

第 Problem 3 題20 分

A Decision Tree is a flowchart used to make decisions. It has three main parts:
Decision Nodes: Boxes that ask a question about the data (e.g., "Is Income High?").
Branches: Arrows that connect nodes, representing the answer (e.g., "Yes" or "No").
Leaf Nodes: The final endpoints that give the prediction (e.g., "Approve" or "Deny").
You are using a Decision Tree to automate loan approvals. Start at the top (Root). Answer the question, follow the matching branch, and repeat until you reach a Leaf.

(a) [4 pts] Which specific part of the tree contains the final answer/prediction?

(b) [5 pts] Consider the following simple logic tree:
• Root Question: "Is Income High?"
If No: Go to Result → [Deny Loan]
If Yes: Go to Next Question → "Has Criminal Record?"
* If Yes: Go to Result → [Deny Loan]
* If No: Go to Result → [Approve Loan]
Task: A new customer arrives with High Income but has a Criminal Record. Trace their path. What is the final decision?

(c) [5 pts] The algorithm must choose the best question to ask. Compare these two questions for a group of 4 people (2 Good Credit, 2 Bad Credit):
• Question A: Splits group into {2 Good Credit} and {2 Bad Credit}.
• Question B: Splits group into {1 Good, 1 Bad} and {1 Good, 1 Bad}.
Which question is better? Briefly explain why using the word "separate" or "mix".

(d) [4 pts] Why is a "short" tree generally preferred over a very "deep" tree for a simple problem?

(e) [2 pts] If a tree is too complex and memorizes the training data perfectly but fails on new customers, what is this error called?

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

這一題的完整詳解

核心觀念

本題考查決策樹（Decision Tree）的基本結構、路徑判讀、資料分割品質，以及過度複雜模型造成的過度擬合（Overfitting）。

決策樹包含三種主要節點：

  • 決策節點（Decision Node）：提出判斷問題。
  • 分支（Branch）：代表問題的不同答案，連接各個節點。
  • 葉節點（Leaf Node）：路徑終點，提供最終分類或預測結果。

(a) 最終答案位於哪個部分？

解題方法

判斷一筆資料時，從根節點開始，依序回答問題並沿著對應分支前進。當抵達無法再往下分割的終點時，該處所提供的分類結果就是最終答案。

答案

最終答案或預測結果位於：

葉節點（Leaf Node）\boxed{\text{葉節點（Leaf Node）}}

(b) 追蹤貸款審核路徑

解題方法

依照客戶資料逐層回答決策樹中的問題：

  1. 根問題是「收入是否高？」
  2. 客戶收入高，因此選擇 Yes 分支。
  3. 進入下一個問題：「是否有犯罪紀錄？」
  4. 客戶有犯罪紀錄，因此選擇 Yes 分支。
  5. 沿著該分支抵達「拒絕貸款」葉節點。

路徑可表示為：

Root→Income High? = Yes→Criminal Record? = Yes→Deny Loan\text{Root} \rightarrow \text{Income High? = Yes} \rightarrow \text{Criminal Record? = Yes} \rightarrow \text{Deny Loan}

答案

最終決策為：

拒絕貸款（Deny Loan）\boxed{\text{拒絕貸款（Deny Loan）}}

高收入只會使客戶進入第二個判斷，並不會直接保證核准貸款。

(c) 比較 Question A 與 Question B

核心觀念

決策樹希望每次分割後，各子群組的類別越單純越好，也就是：

  • 同一群組中的資料盡量屬於相同類別。
  • 不同群組之間的類別盡量被分開。
  • 群組內若 Good Credit 與 Bad Credit 混合，代表分割效果較差。

Question A

原始資料為：

{2 Good Credit, 2 Bad Credit}\{2\text{ Good Credit},\ 2\text{ Bad Credit}\}

Question A 分割為：

  • 第一群：{2 Good Credit}\{2\text{ Good Credit}\}
  • 第二群：{2 Bad Credit}\{2\text{ Bad Credit}\}

兩個子群組都完全純化，Good Credit 與 Bad Credit 被清楚分開，沒有混合。

Question B

Question B 分割為：

  • 第一群：{1 Good, 1 Bad}\{1\text{ Good},\ 1\text{ Bad}\}
  • 第二群：{1 Good, 1 Bad}\{1\text{ Good},\ 1\text{ Bad}\}

兩個子群組都同時包含 Good Credit 與 Bad Credit，類別完全混合，無法有效區分信用好壞。

答案

🔒

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

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

免費註冊

第 Problem 4 題20 分

(a) [4 pts] To minimize maximum lateness in Package delivery logistics, packages are sorted by deadline. What is the name of this scheduling strategy?

(b) [4 pts] You are running Insertion Sort on the array: [45, 10, 30, 25, 60].
Show the state of the array after the element 10 has been processed and inserted into the sorted portion.

(c) [5 pts] Select the most appropriate sorting algorithm for the following scenarios:

  1. The data is already nearly sorted.
  2. The dataset is huge (cannot fit in RAM).

(d) [4 pts] The road network has non-negative travel times. Name the standard shortest-
path algorithm used here.

(e) [3 pts] If the road network has negative edge weights (e.g., time gains/discounts), which
algorithm must be used instead?

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

這一題的完整詳解

(a) 依截止期限排序的排程策略

核心觀念

若工作依截止期限由早到晚執行，排程規則稱為「最早截止期限優先」：

Earliest Deadline First（EDF）

對每個工作 ii，其完成時間為 CiC_i，截止期限為 did_i，延遲時間定義為：

Li=Ci−diL_i=C_i-d_i

目標是最小化最大延遲：

Lmax⁡=max⁡iLiL_{\max}=\max_i L_i

在所有工作同時可執行、單一處理器、沒有其他特殊限制的條件下，依截止期限遞增排序可使 Lmax⁡L_{\max} 最小。

解題技巧

看到「minimize maximum lateness」與「sort by deadline」，直接聯想到 EDF，也常寫成 Earliest Deadline First scheduling。

【答案】Earliest Deadline First（EDF，最早截止期限優先）

(b) Insertion Sort 處理元素 10 後的陣列

核心觀念

Insertion Sort 將陣列分成兩部分：

  • 左側：已排序部分
  • 右側：尚未處理部分

初始陣列為：

[45, 10, 30, 25, 60][45,\ 10,\ 30,\ 25,\ 60]

開始時，第一個元素 4545 視為已排序。接著處理元素 1010。

解題方法

將 1010 與已排序部分中的元素比較：

  1. 10<4510<45，因此將 4545 向右移動一格。
  2. 將 1010 插入原本 4545 所在的位置。

陣列變化如下：

[45, 10, 30, 25, 60][45,\ 10,\ 30,\ 25,\ 60] [_, 45, 30, 25, 60][\_,\ 45,\ 30,\ 25,\ 60] [10, 45, 30, 25, 60][10,\ 45,\ 30,\ 25,\ 60]

此時已排序部分為 [10,45][10,45]。

解題技巧

Insertion Sort 每處理一個元素後，左側部分必須維持遞增排序。處理 1010 後，只需檢查 [10,45][10,45] 是否有序即可。

【答案】[10, 45, 30, 25, 60][10,\ 45,\ 30,\ 25,\ 60]

(c) 依情境選擇排序演算法

1. 資料已經接近排序完成

【最適合】Insertion Sort

核心觀念

Insertion Sort 對每個元素向左尋找正確位置。若資料大致已排序，每個元素需要移動的距離很小，因此實際執行時間接近線性。

其時間複雜度為：

  • 最佳情況：O(n)O(n)
  • 平均情況：O(n2)O(n^2)
  • 最壞情況：O(n2)O(n^2)

其中最佳情況就是資料已經排序或接近排序的情況。

選項分析

  • Insertion Sort：正確。 對接近排序的資料具有高度效率，且可在線性時間內完成已排序資料的掃描。
  • Selection Sort：不適合。 不論資料原本是否接近排序，都必須反覆尋找最小值，時間複雜度固定為 O(n2)O(n^2)。
  • Bubble Sort：通常不如 Insertion Sort。 加入提前停止機制後，已排序資料可達到 O(n)O(n)；但對一般「接近排序」資料，Insertion Sort 通常移動更直接、效率更穩定。
  • Merge Sort：可用但非最佳選擇。 時間複雜度為 O(nlog⁡n)O(n\log n)，不會充分利用資料已接近排序的特性。
  • Quick Sort：可用但非最佳選擇。 平均為 O(nlog⁡n)O(n\log n)，且樞紐選擇不佳時可能退化成 O(n2)O(n^2)。

【答案】Insertion Sort

2. 資料量極大，無法全部放入 RAM

【最適合】External Merge Sort

核心觀念

當資料無法全部載入主記憶體時，必須使用外部排序。External Merge Sort 的流程為：

  1. 分批讀取能放入 RAM 的資料。
  2. 對每一批資料在記憶體內排序。
  3. 將各批已排序資料寫回磁碟，形成多個 sorted runs。
🔒

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

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

免費註冊

第 Problem 5 題20 分

You are analyzing an algorithm called "Iterative Centroid Clustering" (commonly known as K-Means). The algorithm takes a set of data points and k starting points called "Centroids." It groups the data by repeating these two steps:

  1. Assignment Step: For every data point, calculate its distance to each Centroid. Assign the point to the logical group of the closest Centroid.
  2. Update Step: For each logical group, calculate the average (mean) position of all points assigned to that group. Move the Centroid to this new average position.
    Termination Rule: The algorithm stops repeating these steps when the Centroid positions no longer change (i.e., the new position is identical to the old position).

Data Provided for Analysis:
• Data Points: A(1, 1), B(2, 1), C(10, 10), D(11,11).
• Initial Centroids: Centroid 1 is at C1 (1,0). Centroid 2 is at C2(10, 11).

Questions:
(a) [4 pts] Based on the algorithm description above, is this a supervised learning method (where the user tells the algorithm the correct answer beforehand) or an unsupervised method (where the algorithm discovers the structure on its own)? Explain your answer in one sentence.

(b) [4 pts] Execution (Assignment Step): Calculate the squared Euclidean distance from Point A(1, 1) to C₁ and from Point A(1, 1) to C₂. Based on these distances, which Centroid is Point A assigned to?
Hint: Squared Distance = (x1−x2)2+(y1−y2)2(x_1-x_2)^2 + (y_1-y_2)^2

(c) [5 pts] Execution (Update Step): Assume the Assignment Step resulted in the following groups:
• Group 1 contains points {A(1, 1), B(2, 1)}.
• Group 2 contains points {C(10, 10), D(11, 11)}.
Calculate the (x, y) coordinates of the New Centroids using the "Update Step" rule.

(d) [4 pts] According to the "Termination Rule" in the text, how will the computer know when to stop running the loop?

(e) [3 pts] Look at the mathematical definition of the Update Step (calculating an average). What mathematical error would occur if a Centroid ends up with zero points assigned to it?

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

這一題的完整詳解

核心觀念

本題考查 K-Means（K 平均）分群法的基本流程：

  1. Assignment Step：將每個資料點分配給距離最近的 Centroid。
  2. Update Step：將每個群組內所有資料點的座標平均值，作為新的 Centroid。
  3. 重複上述步驟，直到所有 Centroid 的位置不再改變。

K-Means 屬於非監督式學習，因為資料沒有預先提供正確分類標籤，而是由演算法依據距離自行形成群組。

解題方法

本題依序按照 K-Means 的兩個步驟處理：

  • 距離計算使用平方歐氏距離：

    d2=(x1−x2)2+(y1−y2)2d^2=(x_1-x_2)^2+(y_1-y_2)^2

  • Centroid 更新使用群組內資料點的座標平均值：

New Centroid=(∑xin,∑yin)\text{New Centroid}= \left( \frac{\sum x_i}{n}, \frac{\sum y_i}{n} \right)

其中 nn 為該群組所包含的資料點數量。

(a) 學習方法判斷

K-Means 是非監督式學習（unsupervised learning），因為資料未提供每個點的正確群組標籤，而是由演算法根據距離自行發現資料的分群結構。

(b) Point A 的平方歐氏距離與分群

已知：

  • A=(1,1)A=(1,1)
  • C1=(1,0)C_1=(1,0)
  • C2=(10,11)C_2=(10,11)

A 到 C1C_1 的平方距離

d2(A,C1)=(1−1)2+(1−0)2d^2(A,C_1) =(1-1)^2+(1-0)^2 =02+12=1=0^2+1^2=1

A 到 C2C_2 的平方距離

d2(A,C2)=(1−10)2+(1−11)2d^2(A,C_2) =(1-10)^2+(1-11)^2 =(−9)2+(−10)2=81+100=181=(-9)^2+(-10)^2 =81+100=181

因為

1<1811<181

所以 Point A 應分配給距離較近的 Centroid 1。

(c) Update Step：計算新的 Centroids

Group 1：{A(1,1),B(2,1)}\{A(1,1),B(2,1)\}

xx 座標平均值：

x1′=1+22=32=1.5x_1'=\frac{1+2}{2}=\frac{3}{2}=1.5

yy 座標平均值：

y1′=1+12=1y_1'=\frac{1+1}{2}=1

因此新的 Centroid 1 為：

C1′=(1.5,1)\boxed{C_1'=(1.5,1)}
🔒

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

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

免費註冊

其他考古題

其他學校的電機系考古題

臺灣大學50臺灣聯合大學系統110中央大學13中正大學83中山大學96暨南國際大學8臺灣科技大學4聯合大學4嘉義大學2