高考申論題
114年
[統計] 資料處理
第 一 題
📖 題組：
BOM 表為一棵樹的結構，描述一產品 P 的製作過程，其每一節點 N 描述 P 之某一零組件 C 的製程；而其所連結之子樹，描述組合該零組件 C，所需的所有零組件之製程。如圖範例所示，零組件Ｃ0是由零組件 C11、C12 及 C13 所組合製作而成；零組件C12是由零組件 C21 及 C22 所組合製作而成。而零組件 C21 及 C22 何者先製作完成是無所謂；同樣地零組件 C11、C12 及 C13 何者先製作完成也是無所謂。但在製作過程中，需先製作完成零組件 C21 及 C22 後，才能製作零組件 C12 ；且需先製作完成零組件 C11、C12 及 C13 後，才能製作零組件Ｃ0。（每小題 10 分，共 20 分） 圖 BOM 之範例 C0 C11 C12 C13 C21 C22
BOM 表為一棵樹的結構，描述一產品 P 的製作過程，其每一節點 N 描述 P 之某一零組件 C 的製程；而其所連結之子樹，描述組合該零組件 C，所需的所有零組件之製程。如圖範例所示，零組件Ｃ0是由零組件 C11、C12 及 C13 所組合製作而成；零組件C12是由零組件 C21 及 C22 所組合製作而成。而零組件 C21 及 C22 何者先製作完成是無所謂；同樣地零組件 C11、C12 及 C13 何者先製作完成也是無所謂。但在製作過程中，需先製作完成零組件 C21 及 C22 後，才能製作零組件 C12 ；且需先製作完成零組件 C11、C12 及 C13 後，才能製作零組件Ｃ0。（每小題 10 分，共 20 分） 圖 BOM 之範例 C0 C11 C12 C13 C21 C22
📝 此題為申論題，共 2 小題
小題 (一)
試寫一最快速演算法，列印出某一 BOM 表所對應之產品 P 之零組件製程的製作順序。列印之順序為需先被生產之零組件的製程，需先被列印出來。例如對範例圖所示，零組件 C11、C12 及 C13，皆需比零組件Ｃ0早被列印出來；而零組件 C21 及 C22，皆需比零組件 C12 早被列印出來。
思路引導 VIP
這題測驗樹狀結構（Tree）的遍歷演算法實務應用。看到「必須先完成子節點才能完成父節點」且「先生產的先列印」，應立即聯想到樹的「後序遍歷（Post-order Traversal）」。利用遞迴先遍歷所有子節點再處理父節點，即可達成 O(n) 的最佳時間複雜度。
小題 (二)
若每一節點 N，都有紀錄欲生產一件產品 P 時，所需該節點之零組件的製程時間 Tc。且假設有充足機器及原物料，可供其隨時生產該節點之零組件；即可忽略等待機器及原物料的準備時間。請寫一最快速演算法，以計算當欲生產完一件產品 P 之最快生產時間。
思路引導 VIP
本題核心在於理解「平行生產」與「相依性」，子零組件可同時製作，因此父節點的等待時間取決於耗時最長的子節點。解題時應聯想到樹的「後序走訪（Post-order Traversal）」與遞迴（Recursion），由樹葉向樹根計算，推導出：節點總時間 = 本身製程時間 + MAX(子節點總時間)。