高考申論題
113年
[資訊處理] 資料結構
第 一 題
📖 題組：
一、(一)若有 200 人，其中一個人開始打電話給兩個人。隨後，每個接到電話的人都會打電話給另外兩個尚沒有接到電話的人。請問總共會撥打多少通電話？有多少人不會打電話？（無推導過程不給分）（10 分） (二)若一個二元樹其前序追蹤順序（Preorder Traversal）及後序追蹤順序（Postorder Traversal）分別如下，請問此樹是否唯一？並請列出此二元樹的中序追蹤順序（Inorder Traversal）。（無推導過程不給分）（15 分） 前序追蹤順序：T, S, R, F, D, I, H, E, Z, G, M, L, J, N, Q 後序追蹤順序：F, I, H, D, R, Z, G, E, S, J, N, L, Q, M, T
一、(一)若有 200 人，其中一個人開始打電話給兩個人。隨後，每個接到電話的人都會打電話給另外兩個尚沒有接到電話的人。請問總共會撥打多少通電話？有多少人不會打電話？（無推導過程不給分）（10 分） (二)若一個二元樹其前序追蹤順序（Preorder Traversal）及後序追蹤順序（Postorder Traversal）分別如下，請問此樹是否唯一？並請列出此二元樹的中序追蹤順序（Inorder Traversal）。（無推導過程不給分）（15 分） 前序追蹤順序：T, S, R, F, D, I, H, E, Z, G, M, L, J, N, Q 後序追蹤順序：F, I, H, D, R, Z, G, E, S, J, N, L, Q, M, T
📝 此題為申論題，共 2 小題
小題 (一)
若有 200 人，其中一個人開始打電話給兩個人。隨後，每個接到電話的人都會打電話給另外兩個尚沒有接到電話的人。請問總共會撥打多少通電話？有多少人不會打電話？（無推導過程不給分）（10 分）
思路引導 VIP
看到這題，首先要將題目描述的情境轉化為「二元樹（Binary Tree）」的結構。撥電話的人是父節點，接電話的人是子節點。問題中的「總共撥打多少通電話」等同於求「樹的邊數（Edges）」，而「有多少人不會打電話」等同於求「葉節點（Leaf nodes）的數量加上尚未接到電話的人」。關鍵點在於：二元樹中節點數 N、邊數 E 與度數（Degree）之間的關係。此外，要注意 200 人中是否所有人都會接到電話？這取決於樹的成長停止條件（當沒有多餘的人可以接電話時）。
小題 (二)
若一個二元樹其前序追蹤順序（Preorder Traversal）及後序追蹤順序（Postorder Traversal）分別如下，請問此樹是否唯一？並請列出此二元樹的中序追蹤順序（Inorder Traversal）。（無推導過程不給分）（15 分）
前序追蹤順序：T, S, R, F, D, I, H, E, Z, G, M, L, J, N, Q
後序追蹤順序：F, I, H, D, R, Z, G, E, S, J, N, L, Q, M, T
思路引導 VIP
解題關鍵在於理解「前序+後序」能否唯一確定二元樹。理論上，只有「中序+前序」或「中序+後序」能唯一確定。當二元樹中存在「度數為 1（只有一個子節點）」的節點時，前序與後序無法判斷該子節點是左子樹還是右子樹。因此，第一步應嘗試構建樹狀結構，觀察是否有分支選擇的歧義。接著，根據構建出的樹寫出中序走訪。