加載中. ..
PDF
102
年公務人員特種考試關務人員考試、
102
年公務人員特種考試稅
務人員考試、
102
年公務人員特種考試海岸巡防人員考試、
102
年公
務人員特種考試移民行政人員考試、
102
年特種考試退除役軍人轉
任公務人員考試及
102
年國軍上校以上軍官轉任公務人員考試試題
代號：13560
等 別： 三等關務人員考試
類(科)別： 資訊處理
科 目： 資料結構
考試時間： 2小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
全一頁
一、關於時間複雜度（time complexity）：
下列那兩個敘述是錯的？（10 分）
(A) 0.5n2+100n=O(n2) (B) 1000=O(1) (C) 0.5n+5logn=O(n2)
(D) 2n2+5n=O(2n) (E) n7+1.5n=O(n7) (F) 3n2+nlog4n=O(nlog4n)
承上，請把上題錯的敘述改正並且寫下。（20 分）
二、已知一棵二元樹（binary tree）的前序走訪（preorder traversal）與中序走訪（inorder
traversal）之結果分別如下：（每小題 10 分，共 20 分）
前序－A B D E G H C F I
中序－D B G E H A C I F
請繪出這棵二元樹。
這棵二元樹的後序走訪（postorder traversal）結果為何？
三、請找出並且從小到大依序列出下列有向圖（directed graph）中，從頂點 A到所有其
他頂點的最短路徑（path）與路徑長度。（20 分）
四、考慮排序（sort）的問題：（每小題 10 分，共 30 分）
如果要排序的資料很少，例如只有十幾筆資料，那麼你將採用快速排序法（quick
sort）？合併排序法（merge sort）？還是氣泡排序法（bubble sort）？為什麼？
如果要排序的資料很多，例如多到超過主記憶體容量許多，那麼你將採用快速排
序法？合併排序法？還是氣泡排序法？為什麼？
快速排序法、合併排序法以及氣泡排序法這三個排序法當中，那一（些）排序法
是穩定的（stable）？或者都不穩定？