加載中. ..
PDF
113年公務人員高等考試三級考試試題
類 科
：
資訊處理
科 目
：
資料結構
考試時間
：
2
小時
座號
：
※注意：禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
代號：
37450
頁次：
1
－
1
一、若有 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(n2)，請說明是在何種情況下造成？（10 分）
請列出其最壞的時間複雜度為 O(n2)的推導過程。（15 分）
三、請使用虛擬碼（Pseudo Code）或任何程式語言，完成下列問題：
撰寫二元搜尋（Binary Search）的遞迴及非遞迴程式。（20 分）
推導二元搜尋的時間複雜度（Time Complexity）。（5分）
四、堆疊（Stack）與佇列（Queue）是常見的資料結構，請回答下列問題：
利用雙向佇列（Deque）循序輸入 1, 2, 3, 4, 5, 6, 7，請問能否得到
5174236 的輸出排列？並說明其過程或理由。（10 分）
若有 1, 2, 3, 4 四個數字要依序 Push 進堆疊，再於任意時間點 Pop 出
堆疊，請列出可能的輸出組合。（15 分）