102年 - 關務#18033

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

試卷資訊

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

選擇題 (0)

申論題 (4)

一、關於時間複雜度（time complexity）： (一)下列那兩個敘述是錯的？（10分）

(A) 0.5n2+100n=O(n2)

(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）？或者都不穩定？