113年 - 113 高等考試_三級_資訊處理：資料結構#121217

科目：公職◆資料結構 | 年份：113年 | 選擇題數：0 | 申論題數：8

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (8)

一、(一)若有 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

二、(一)快速排序法（Quick Sort）最壞的情況下所需的時間複雜度（Time Complexity）為 O(n²)，請說明是在何種情況下造成？（10 分）

(二)請列出其最壞的時間複雜度為 O(n²)的推導過程。（15 分）

(一)撰寫二元搜尋（Binary Search）的遞迴及非遞迴程式。（20 分）

(二)推導二元搜尋的時間複雜度（Time Complexity）。（5 分）

(一)利用雙向佇列（Deque）循序輸入 1, 2, 3, 4, 5, 6, 7，請問能否得到 5174236 的輸出排列？並說明其過程或理由。（10 分）

(二)若有 1, 2, 3, 4 四個數字要依序 Push 進堆疊，再於任意時間點 Pop 出堆疊，請列出可能的輸出組合。（15 分）